Hoare的分区不能正常工作（quicksort） [英] Hoare's partition not working correctly (quicksort)

问题描述

因此，在遵循Cormen的快速排序和分类算法之后，这是我能够生成的代码。该数组出来的部分排序与未初始化的元素/垃圾元素，我不能为我的生活找出为什么...我认为我遵循的算法完全与书写它。

这是直接从书中的伪代码：

  HOARE- PARTITION（A，p，r）
 1 x = A [p] 
 2 i = p  -  1 
 3 j = r + 1 
 4 TRUE TRUE 
 5重复
 6 j = j-1 
 7直到A [j] <= x 
 8重复
 9 i = i + 1 
 10直到A [ i]> = x 
 11如果i < j 
 12交换A [i]与A [j] 
 13 else return j 
  

这里是C ++代码我翻译成：

  void quickSort（int arr []，int p，int r）{
 if（p  int q = hoare_partition（arr，p，r）; 
 quickSort（arr，p，q-1）; 
 quickSort（arr，q + 1，r）; 
} 
} 
 
 int hoare_partition（int arr []，int p，int r）{
 int x = arr [p] 
 int i = p  -  1; 
 int j = r + 1; 
 while（true）{
 do {
 j--; 
} while（arr [j]> x）; 
 do {
 i ++; 
} while（arr [i]< x）; 
 if（i< j）{
 int temp = arr [i]; 
 arr [i] = arr [j]; 
 arr [j] = temp; 
} 
 else 
 return j; 
} 
} 
  

Im使用以下方法测试

  cout< endl endl 测试快速排序< endl 
 int tarr [10] = {2，30，1，99，46，33，48，67，23，76}; 
 quickSort（tarr，0，10）; 
 cout<< arr after quicksort：; 
 for（int i = 0; i <10; i ++）{
 cout< tarr [i] ; 
} 
 cout<< endl 
  

输出

 快速排序后的arr：-2146162183 1 2 23 30 33 46 48 67 76 
  

帮助提前感谢...感谢

编辑

将测试用例调用更改为quickSort ，0，9）修复了这种情况。

但是，使用反向排序数组作为输入，这是输出：

  arr2是：
 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
 arr2快速排序后：
 1 3 5 7 9 11 13 15 17 19 20 21 18 22 16 23 14 24 12 25 10 26 8 27 6 28 4 29 2 30 
  
 
 
 
使用此测试代码：
  int arr2 [30]; 
 fillArrayReverse（arr2，30）; 
 cout<< arr2是：< endl 
 for（int i = 0; i <30; i ++）{
 cout< arr2 [i]<< ; 
} 
 cout<< endl 
 quickSort（arr2，0，29）; 
 cout<< 快速排序后的arr2：< endl 
 for（int i = 0; i <30; i ++）{
 cout< arr2 [i]<< ; 
} 
 cout<< endl 
  
 
 
解决方案
这是测试代码的问题。第三个参数应该是最后一个元素的索引，而不是元素的数量：
  quickSort（tarr， ; 
  
您正在阅读超过数组末尾。
 
 
 
有关Hoare分区，Quicksort和Cormen等的详细信息，请参见此问题 。
 
 
 
对其他问题的简单修复是将hoare_partition（）更改为 return i 的j。有关详情，请参阅相应链接（这是该书中的错误）。
 
So after following the quicksort and hoares partition algorithm from Cormen, this is the code that I was able to produce.  The array comes out partly sorted with uninitialized elements/garbage elements and I can't for the life of me figure out why... I thought I followed the algorithm exactly as the book writes it. 

Here is the pseudocode straight from the book:
HOARE-PARTITION(A, p, r)
1 x = A[p]
2 i = p - 1
3 j = r + 1
4 while TRUE
5     repeat
6        j = j - 1
7     until A[j] <= x
8     repeat
9        i = i + 1
10    until A[i] >= x
11    if i < j
12        exchange A[i] with A[j]
13    else return j
And here is the C++ code I translated it into:
void quickSort(int arr[], int p, int r){
    if(p < r){
        int q = hoare_partition(arr, p, r);
        quickSort(arr, p, q-1);
        quickSort(arr, q+1, r);
    }
}

int hoare_partition(int arr[], int p, int r){
    int x = arr[p];
    int i = p - 1;
    int j = r + 1;
    while(true){
        do{
            j--;
        }while(arr[j] > x);
        do{
            i++;
        }while(arr[i] < x);
        if(i < j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        else 
            return j;
    }
}
Im using the following to test it
cout << endl << endl << "Testing quicksort" << endl;
int tarr[10] = {2, 30, 1, 99, 46, 33, 48, 67, 23, 76};
quickSort(tarr, 0, 10);
cout << "arr after quicksort: ";
for(int i = 0; i < 10; i++){
    cout <<  tarr[i] << " ";
}
cout << endl;
The output
arr after quicksort: -2146162183 1 2 23 30 33 46 48 67 76
Any help is appreciated ahead of time...thanks

EDIT

Changing the test case call to quickSort(arr, 0, 9) fixed it for this situation.

However, with a reverse sorted array as the input this is the output:
arr2 is:
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
arr2 after quicksort :
1 3 5 7 9 11 13 15 17 19 20 21 18 22 16 23 14 24 12 25 10 26 8 27 6 28 4 29 2 30
using this test code:
int arr2[30];
fillArrayReverse(arr2, 30);
cout << "arr2 is :" << endl;
for(int i = 0; i < 30; i++){
    cout << arr2[i] << " ";
}
cout << endl;
quickSort(arr2, 0, 29);
cout << "arr2 after quicksort: " << endl;
for(int i = 0; i < 30; i++){
    cout << arr2[i] << " ";
}
cout << endl;

解决方案
It's a problem with your test code. The third parameter should be the index of the last element, not the number of elements:
quickSort(tarr, 0, 9);
You're reading past the end of the array.

For more information about Hoare partitioning, Quicksort and Cormen etc, see this question.

The simple fix for the other problems you're having is to change hoare_partition() to return i instead of j. See the link for more details (it's an error in the book reportedly).

                        
这篇关于Hoare的分区不能正常工作（quicksort）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！