Implementing Quicksort

问题:

i am trying to implement quicksort but i am not getting correct results. Here is my code:

public static void quickSort(Comparable[] a, int start, int stop) {
    if (start < stop) {
        int pivot = partition(a, start ,stop);
        System.out.print("Pivot: "+a[pivot]+" Array: ");
        printArray(a);
        quickSort(a,start,pivot-1);
        quickSort(a,pivot+1, stop);
    }       
}

public static int partition(Comparable[] a, int start, int stop) {
    Comparable pivot = a[stop];
    int i = start;
    int j = stop-1;


     while (i < j) {
            while( (isLess(a[i], pivot)|| isEqual(a[i], pivot)))
                i++;
            while((isGreater(a[j], pivot)|| isEqual(a[j], pivot)))
                j--;
            if(i < j)
                swap(a, i,j);
        } 

    swap(a,i, stop);

    return i;

}

For input: {51,17,82,10,97,6,23,45,6,73}, i am getting result: 6 6 10 17 23 45 51 73 97 82 For input: {12,9,4,99,120,1,3,10}, i am getting an index out of bounds error. Would appreciate some help in where i am going wrong.

回答1:

Your two problems are unrelated.

The problem with {51,17,82,10,97,6,23,45,6,73} is — what happens when stop == start + 1? Then i == start == stop - 1 == j, so you never enter the while-loop, so you unconditionally swap(a, i, stop) — even if a[i] was already less than a[stop].

The problem with {12,9,4,99,120,1,3,10} is seemingly that you didn't read the stacktrace. ;-)   Assuming you have a decent Java compiler and JVM, it should have given you the exact line-number and problematic index, so you would have seen that the problem is in this line:

            while((isGreater(a[j], pivot)|| isEqual(a[j], pivot)))

once j gets to -1. (This will happen if pivot is the very least value in the range of interest.) You just need to add a check for that:

            while(j > start && (isGreater(a[j], pivot)|| isEqual(a[j], pivot)))

(and, for that matter, for the corresponding case of i:

            while(i < stop && (isLess(a[i], pivot)|| isEqual(a[i], pivot)))

)

. . . and you need to learn how to debug your code. :-)

回答2:

I recommend you Algorithms: Design and Analysis, very good internet course from Stanford. After this course you will write such codes more easily. It is a bit enhanced version, pivot is chosen as a median of three. Note that you don't have to write your own printArray() function. In Java you can do it with System.out.println(Arrays.toString(numbers)). Also you can observe how to call quickSort() in more elegant way, with only one argument, using method overloading.

public class QuickSort
{

public static void main(String[] args)
{
    int numbers[] =
    { 51, 17, 82, 10, 97, 6, 23, 45, 6, 73 };
    quickSort(numbers);
    System.out.println(Arrays.toString(numbers));
}

public static void quickSort(int[] array)
{
    quickSort(array, 0, array.length - 1);
}

private static void quickSort(int[] array, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int pivot = choosePivot(array, left, right);
    pivot = partition(array, pivot, left, right);
    quickSort(array, left, pivot - 1);
    quickSort(array, pivot + 1, right);
}

private static int partition(int[] array, int pivot, int left, int right)
{
    swap(array, pivot, left);
    pivot = left;
    int i = left + 1;
    for (int j = left + 1; j <= right; j++)
    {
        if (array[j] < array[pivot])
        {
            swap(array, j, i);
            i++;
        }
    }
    swap(array, pivot, i - 1);
    return i - 1;
}

private static void swap(int[] array, int j, int i)
{
    int temp = array[j];
    array[j] = array[i];
    array[i] = temp;
}

private static int choosePivot(int[] array, int left, int right)
{
    return medianOfThree(array, left, (left + right) / 2, right);
    // return right;
}

private static int medianOfThree(int[] array, int aIndex, int bIndex, int cIndex)
{
    int a = array[aIndex];
    int b = array[bIndex];
    int c = array[cIndex];
    int largeIndex, smallIndex;
    if (a > b)
    {
        largeIndex = aIndex;
        smallIndex = bIndex;
    }
    else
    {
        largeIndex = bIndex;
        smallIndex = aIndex;
    }
    if (c > array[largeIndex])
    {
        return largeIndex;
    }
    else
    {
        if (c < array[smallIndex])
        {
            return smallIndex;
        }
        else
        {
            return cIndex;
        }
    }
}

}

回答3:

Well, here's the code on implementing quicksort,

public class QuickSort 
{
   int partition(int arrNum[], int low, int high)
   {
      int pivot = arrNum[high]; 
      int a = (low - 1); // smaller element index
      for(int b = low; b < high; b++)
      {
         // condition to check current element is smaller than or equal to pivot
         if(arrNum[b] <= pivot)
         {
            a++;
            // swapping arrNum[a] and arrNum[b]
            int temp = arrNum[a];
            arrNum[a] = arrNum[b];
            arrNum[b] = temp;
         }
      }

      // swapping arrNum[a + 1] and arrNum[high]
      int temp = arrNum[a + 1];
      arrNum[a + 1] = arrNum[high];
      arrNum[high] = temp;

      return a + 1;
   }

   void sortNumber(int arr[], int low, int high)
   {
      if(low < high)
      { 
         int part = partition(arr, low, high);
         // Recursive function sort elements before partition and after partition
         sortNumber(arr, low, part - 1);
         sortNumber(arr, part + 1, high);
      }
   }

   // printing utility function
   static void printingArray(int arr[])
   {
      int num = arr.length;
      for(int a = 0; a < num; ++a)
         System.out.print(arr[a] + " ");
      System.out.println();
   }

   public static void main(String[] args) 
   {
      int arr[] = {33, 36, 63, 34, 45, 78};
      int n = arr.length;

      QuickSort qs = new QuickSort();
      qs.sortNumber(arr, 0, n - 1);

      System.out.println("Quicksort sorted array : ");
      printingArray(arr);
   }
}