Unknown Test cases failed with Quick sort

Question

I've written a partition function for quick sort for an exam online, it passed 6/10 test cases, I dont know which test cases It failed. I'm sharing my code if any one can help me know if there is any problem with my logic.

This is the whole code: https://codebeautify.org/alleditor/cb320209

This is the code for the partition function:

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;

just a note: when I've changed my partition function with a partition function from geeksforgeeks it passed all the test cases. I'll share that partition function code also(which passed all the test cases).

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);
}

Again! I'm sorry but I really dont know in which test cases it failed I just want to know if my logic is right. or i've not done any silly mistake.

`int pivot = arr[si];` is not valid C++, but i think ok in C. Nevertheless I believe this is C++ code (`swap` ?). Please only tag the language you are actually using. (And read: [Why aren't variable-length arrays part of the C++ standard?](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard)) — 463035818_is_not_an_ai, Sep 27 '21 at 09:23
dont rely on an online judge to test your code only. What test cases did you run? Did they all pass? If yes you need to try harder to find one that fails — 463035818_is_not_an_ai, Sep 27 '21 at 09:25
you are using closed intervals, ie `low` and `high` both are elements in the array. Thats very suspicious, because usually half open intervals are used, ie `low` included, `high` would be one past the last element. — 463035818_is_not_an_ai, Sep 27 '21 at 09:29
How is the function called? Where is the description of the taks? Please read about [mcve] — 463035818_is_not_an_ai, Sep 27 '21 at 09:29
okay in that case like the code in GFG, they've taken the startIndex as low-1.......and at last they've returned i+1.....from the partition function......I've included low and high both...and so, returned just the startIndex. — pifigi, Sep 27 '21 at 09:32
https://codebeautify.org/alleditor/cb320209 I've shared the code link — pifigi, Sep 27 '21 at 09:33
you can [edit](https://stackoverflow.com/posts/69344201/edit) the question to add missing information — 463035818_is_not_an_ai, Sep 27 '21 at 09:33

rcgldr · Answer 1 · 2021-09-27T21:47:57.163

Your partition function is a variation of Hoare partition scheme. There is no need to swap the pivot before doing the partition, and after a Hoare partition step, the pivot and elements equal to the pivot can end up anywhere, so returning newI is causing a problem. Example of a post increment and decrement variation Hoare partition scheme where the partition code is included with the main quicksort code:

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);
}

Classic Hoare scheme:

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);
    }
}

Unknown Test cases failed with Quick sort

1 Answers1