时间戳

首页 > 解决方案 > 未知测试用例因快速排序而失败

c++ - 未知测试用例因快速排序而失败

问题描述

我为在线考试编写了一个快速排序的分区函数，它通过了 6/10 个测试用例，我不知道哪些测试用例失败了。如果有人可以帮助我知道我的逻辑是否有任何问题，我将分享我的代码。

这是整个代码：https ://codebeautify.org/alleditor/cb320209

这是分区函数的代码：

int partition(int arr[], int si, int ei) {
    // selecting pivot
    int pivot = arr[si];
    // finding the pos of the pivot by
    // selecting the no of elms lesser to pivot 
    int newI=si;  

    for (int i = si; i <= ei; i++) {
        if (arr[i] < pivot) {
            newI++;
        }
    }

    // swapping pivot with the element which is in its right pos
    swap(arr, si, newI);
    
    // making all the elms on right bigger and left smaller
    int i = si, j = ei;
    while (i < j) { 
        if (arr[i] < pivot) {
            i++;
        }
        else if (arr[j] > pivot) {
            j--;
        }  
        else {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
    
    return newI;

请注意：当我使用 geeksforgeeks 的分区函数更改分区函数时，它通过了所有测试用例。我也会分享那个分区函数代码（它通过了所有的测试用例）。

int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int i = (low - 1);  // Index of smaller element
 
    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

再次！很抱歉，但我真的不知道在哪些测试用例中失败了 我只想知道我的逻辑是否正确。或者我没有犯任何愚蠢的错误。

标签： c++quicksort

解决方案

您的分区函数是 Hoare 分区方案的变体。在进行分区之前不需要交换枢轴，并且在 Hoare 分区步骤之后，枢轴和等于枢轴的元素可以在任何地方结束，因此返回 newI 会导致问题。后递增和递减变化 Hoare 分区方案的示例，其中分区代码包含在主快速排序代码中：

void QuickSort(int *a, int lo, int hi)
{
int i, j;
int p, t;
    if(lo >= hi)
        return;
    p = a[lo + (hi-lo)/2];
    i = lo;
    j = hi;
    while (i <= j){
        while (a[i] < p)i++;
        while (a[j] > p)j--;
            if (i > j)
                break;
            t = a[i];
            a[i] = a[j];
            a[j] = t;
            i++;
            j--;
    }
    QuickSort(a, lo, j);
    QuickSort(a, i, hi);
}

经典霍尔方案：

int Partition(int a[], int lo, int hi)
{
    int pivot = a[lo+(hi-lo)/2];
    int i = lo - 1;
    int j = hi + 1;
    int t;
    while(1)
    {
        while(a[++i] < pivot);
        while(a[--j] > pivot);
        if(i >= j)
            return j;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

void QuickSort(int a[], int lo, int hi)
{
    int index;
    if (lo < hi)
    {
        index = Partition(a, lo, hi);
        QuickSort(a, lo, index);
        QuickSort(a, index + 1, hi);
    }
}

推荐阅读