CODEWITHSUNDEEP
javaalgorithmsortingquicksort
Programmer Shelley
Programmer Shelley

Reputation: 3

What is wrong with my Java quicksort implementation?

I'm pretty sure I understand how quicksort works, but I can't find the bug that's causing my attempt at implementing it to not work. I've looked through this for hours and can't figure out what's wrong. Please help me! Here is the entire file (It's just quicksort - nothing extra. The array is just random numbers for testing the quicksort.) 

public class Quicksort{ 

    public static void main(String args[]){
        int[] arr = {5,1,4,3,7,0,9,2,6,8};
        quicksort(arr, 0, arr.length-1);
        for(int x : arr)
          System.out.print(x+" ");
    }

    public static void quicksort(int[] arr, int start, int end){
        if(end-start<2)
            return; 
        int pivot = (end-start)/2;
        int i = start; 
        int k = end;
        while(k>i){
            while(arr[i]<arr[pivot]&&k>i&&i<=end)
                i++; 
            while(arr[k]>arr[pivot]&&k>=i)
                k--; 
            if(k>i){
                swap(arr, i, k); 
            }
        }
        swap(arr, pivot, i);

        quicksort(arr, 0, i);
        quicksort(arr, k, arr.length-1);
     }

     public static void swap(int[] a, int x, int y){
         int temp = a[x]; 
         a[x] = a[y]; 
         a[y] = temp; 
     }
}

As it is right now, the loop never terminates... it's a forever infinite loop! Please help me figure out what's wrong.

Upvotes: 0

Views: 533

Answers (4)

user207421
user207421

Reputation: 311050

while(arr[i]<arr[pivot]&&k>i&&i<=end)

Clearly you have had array index problems. All these tests aren't required in a working Quicksort, and the ones that are are in the wrong order.

Upvotes: 0

tskuzzy
tskuzzy

Reputation: 36476

Your base case should be if(end-start<1) - You only want to stop sorting when the number of elements is 1 (i.e. if start and end are equal)

Your while loops should just be while(arr[i]<arr[pivot]) and while(arr[k]>arr[pivot])

This

if(k>i){
    swap(arr, i, k); 
}

should be 

if(k>=i){
    swap(arr, i, k);
    i++;
    k--;
}

swap(arr, pivot, i); is unnecessary.

Your recursive call should be quicksort(arr, start, k); and quicksort(arr, i, end);

Upvotes: 1

Kal
Kal

Reputation: 24910

Couple of things that stand out --

  1. Your end condition seems incorrect. If your array has just 2 elements, it won't sort them.

  2. Also, after you do the swap, you need to increment and i and decrement k.

Upvotes: 1

Michael Borgwardt
Michael Borgwardt

Reputation: 346526

Do yourself a favor and learn how to use a debugger. It makes solving this kind of problems very easy.

Upvotes: 5

Related Questions