C中的Hoare分区快速排序算法

uurity8g  于 12个月前  发布在  其他
关注(0)|答案(3)|浏览(104)

我对这个快速排序算法有一个问题:

void swap(int *x, int *y) {
    int tmp;

    tmp = *x;
    *x = *y;
    *y = tmp;
}

int partition (int *arr, int min, int max) {
    int x = arr[min];
    int i = min - 1;
    int j = max + 1;

    while (1) {
        do {
            j--;
        } while (i < j && arr[j] < x);
        do {
            i++;
        } while (arr[i] > x);
        if  (i < j)
            swap(&arr[i], &arr[j]);
        else
            return j + 1;
    }
}

void quickSort(int *arr, int inf, int sup) {
    if (arr) {
        if (inf < sup) {
            int pivot = partition(arr, inf, sup);
            //printf("pivot = %d", pivot);
            quickSort(arr, inf, pivot - 1);
            quickSort(arr, pivot + 1, sup);
        }
    }
}

int main() {
    int array[] = { 151, 153, 134, 137, -1, -1, -1, -1, -1, 158, 158, -1, -1, 133, 127, 158, 158 };

    int dim = sizeof(array) / sizeof(int);
    quickSort(array, 0, dim - 1);

    for (int i = 0; i < dim; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

它应该返回一个降序排序的数组,但由于某些原因,它没有。
输入:(512个元素长度的数组的其余部分由-1组成)

151 153 134 137 -1 -1 -1 -1 -1 158 158 -1 -1 133 127 158 158

输出:

158 158 158 153 158 -1 151 134 137 133 127 -1 -1 -1 -1 -1 -1

预期输出:

158 158 158 158 153 151 137 134 133 127 -1 -1 -1 -1 -1 -1 -1

我期望算法返回一个降序排序的数组。我试着切换输入,但似乎没有什么工作。

pvcm50d1

pvcm50d11#

首先,你需要仔细调试你的分区函数。返回值应为j

int partition (int *arr,int min, int max){
    int x=arr[min];
    int i=min-1;
    int j=max+1;

    while (1) {
        do {
            j--;
        } while (i < j && arr[j] < x);
        do {
            i++;
        } while (arr[i] > x);
        if  (i < j)
            swap(&arr[i],&arr[j]);
        else
            return j;
    }
}

你可以使用gdb或任何ide调试主流程,你可以得到逻辑。对于quickSort函数,应该使用inf->pivot,pivot + 1 -> sup;而不是忽略数组透视索引。

void quickSort(int *arr, int inf, int sup){
    if(arr){
        if(inf < sup){
            int pivot = partition(arr, inf, sup);
            //printf("pivot = %d", pivot);
            quickSort(arr, inf, pivot);
            quickSort(arr, pivot+1, sup);
        }
    }
}

希望能有所帮助。谢谢

mspsb9vt

mspsb9vt2#

https://en.wikipedia.org/wiki/Quicksort表示Hoare分区方案使用中间的元素作为枢轴元素。所以int x=arr[min];应该是int x=arr[(min+max)/2];
partition应该是return j;,而不是j+1;
第一个quicksort调用应该包含pivot元素。
quicksort函数中的if也不完整。
下面是工作代码(至少使用您的示例数据):

#include <stdio.h>

void swap(int *x, int *y){
    int tmp;

    tmp = *x;
    *x = *y;
    *y = tmp;
}

int partition (int *arr,int min, int max){
    int x=arr[(min+max)/2];
    int i=min-1;
    int j=max+1;

    while (1) {
        while (arr[++i] > x);
        while (arr[--j] < x);

        if  (i >= j)
            return j;
        swap(&arr[i],&arr[j]);
    }
}

void quickSort(int *arr, int inf, int sup){

    if(arr){
        if(inf >= 0 && sup >= 0 && inf < sup){
            int pivot = partition(arr, inf, sup);
            //printf("pivot = %d\n", pivot);
            quickSort(arr, inf, pivot);
            quickSort(arr, pivot+1, sup);
        }
    }
}

int main() {
    int array[] = {151, 153, 134, 137, -1, -1, -1, -1, -1, 158, 158, -1, -1, 133, 127, 158, 158};

    int dim = sizeof(array)/ sizeof(int);
    quickSort(array, 0, dim-1);

    for (int i = 0; i < dim; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    return 0;
}

https://godbolt.org/z/54W6j145e

xzabzqsa

xzabzqsa3#

从维基百科页面关于霍尔分区方案的快速排序(强调我的):
Tony Hoare描述的原始分区方案使用两个指针(范围内的索引),它们从被分区数组的两端开始,然后彼此移动,直到它们检测到反转:一对元素,一个大于第一指针处的界限(枢轴值的霍尔项),一个小于第二指针处的界限;如果此时第一指针仍在第二指针之前,则这些元素相对于彼此的顺序错误,然后交换它们。在此之后,指针向内移动,并且重复对反转的搜索;当指针最终交叉时(第一个指针在第二个指针之后),不执行交换;找到有效的分区**,其具有交叉指针之间的划分点**(可能严格地在交叉指针之间的任何条目等于主元,并且可以从形成的两个子范围中排除)。利用该公式,一个子范围可能变成整个原始范围,这将阻止算法前进。因此,Hoare规定,在结束时,在(如果必要的话)将其与最接近分隔的子范围元素交换之后,通过排除该枢轴**,可以减小包含枢轴元素(其仍然处于其原始位置)的子范围的大小;从而确保快速排序的终止。
同一页显示了一个伪代码实现:

// Sorts a (portion of an) array, divides it into partitions, then sorts those  
algorithm quicksort(A, lo, hi) is  
  if lo >= 0 && hi >= 0 && lo < hi then  
    p := partition(A, lo, hi)

    quicksort(A, lo, p)        // Note: the pivot is now included  
    quicksort(A, p + 1, hi)

// Divides array into two partitions
algorithm partition(A, lo, hi) is 
  // Pivot value
  pivot := A[ floor((hi - lo)/2) + lo ] // The value in the middle of the array

  // Left index
  i := lo - 1 

  // Right index
  j := hi + 1

  loop forever 
    // Move the left index to the right at least once and while the element at
    // the left index is less than the pivot
    do i := i + 1 while A[i] < pivot
    
    // Move the right index to the left at least once and while the element at
    // the right index is greater than the pivot
    do j := j - 1 while A[j] > pivot

    // If the indices crossed, return
    if i >= j then return j
    
    // Swap the elements at the left and right indices
    swap A[i] with A[j]

与OP的代码不同,对quicksort * 的第一次递归调用包括 * pivot,partition返回j而不是j + 1

相关问题