使用hoarepartition的QuickSort产生不正确的输出

Question

我的作业要求我实现与教科书中的伪代码完全相同的QuickSort算法： 它指定使用hoarepartition进行分区。

pivot <- A[leftMost]
i <- leftMost; j <- rightMost+1

这是我的代码：

import java.util.Arrays;
public class Main{
   public static void main(String args[]){
      int[] array1 = {10, 4, 2, 8, 7, 3, 5, 9, 6, 1};
      int n1 = array1.length;
      System.out.print("Before sorting is: ");
      System.out.println(Arrays.toString(array1));
      System.out.printf("After sorting is: ");
      Quicksort(array1, 0, n1 -1);
      System.out.println(Arrays.toString(array1));
   } //end main

   public static void Quicksort(int[]array, int start, int end){
      if(start<end){
         int pivot = HoarePartition(array, start, end);
         Quicksort(array, start, pivot-1);
         Quicksort(array, pivot+1, end);
      }
   } //end Quicksort()

   public static int HoarePartition(int[] array, int start, int end){
      int pivot = array[start];
      int i = start;
      int j = end +1;
      while(true){
      while(array[i] < pivot)
         i++;
      do{j--}while(array[j] > pivot)

      if(i <= j)
         return j;
      int temp = array[i];
      array[i] = array[j];
      array[j] = temp;
      } //end while
   } //end HoarePartition()

输出是：

Before sorting is: [10, 4, 2, 8, 7, 3, 5, 9, 6, 1]
After sorting is: [1, 3, 2, 5, 7, 4, 8, 9, 6, 10]

显然，它没有正确排序，我一遍又一遍地考虑，但仍然不知道我的算法的哪一部分是错误的...

Answer 1

两个递归电话应该是：

         Quicksort(array, start, pivot);   // (not pivot-1)
         Quicksort(array, pivot+1, end);

---

经典的Hoare分区

      // ...
      int i = start-1;
      int j = end +1;
      while(true){
          while(array[++i] < pivot);
          while(array[--j] > pivot);
      // ...

Answer 2

您编写的代码有一些问题。

• 在您的第一个递归调用QuickSort中，应包括枢轴绑定而不是传递pivot-1。

• 在您的中


• 返回条件不仅应检查两个索引i和j已经满足，而且是否相互交叉，如果（I＆gt; =（i＆gt; =） j）返回j;

• 最内向的循环应写为两个，而循环而不是，而和 do- do-while < /p>

public static void Quicksort(int[] array, int start, int end) {
    if (start < end) {
        int pivot = HoarePartition(array, start, end);
        Quicksort(array, start, pivot);
        Quicksort(array, pivot + 1, end);
    }
}

public static int HoarePartition(int[] array, int start, int end) {
    int pivot = array[start];
    int i = start;
    int j = end;

    //Iterating until the left index crosses the right index
    while (true) {

        //Looking for an element on the left side greater than the pivot
        while (array[i] < pivot) i++;
        
        //Looking for an element on the right side lower than the pivot
        while (array[j] > pivot) j--;

        //If the left index passed the right index, then there is no element on the left side greater then the pivot or a lower element on the right side
        if (i >= j) return j;

        //Swapping the elements greater than the pivot (left) and lower than the pivot (right) (the index haven't met yet)
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;

        i++;
        j--;
    }
}

输出

Before sorting is: [10, 4, 2, 8, 7, 3, 5, 9, 6, 1]
After sorting is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Answer 3

谢谢！我发现了我犯的错误：
我在hoarepartition（）中设置了最初的值，在调整i，j和键入的循环后，它可以正常工作！

    public static int HoarePartition(int[] array, int start, int end){
    int pivot = array[start];
    int i = start -1 ;
    int j = end + 1;

    while(true){
        do{i++;}while(array[i] < pivot);
        do{j--;}while(array[j] > pivot);
        
        if(i>=j)
            return j;
        /*swap(array[i], array[j])*/
        swapIJ(array, i, j);
    } //end while
} //end HoarePartition()