-1

My code is working for arrays such as {11,6,8,23,9,1,5,15} which does not have multiple duplicate values but for array values such as {11,6,8,23,9,1,5,15,7,7,7,7} where I have duplicate values, my code is giving a wrong output. But if I only have two duplicate values, for example 7,7 I am still getting the correct o/p. The real issue begins when I have duplicate values more than 2. I tried debugging in Xcode but since I am a beginner and it's only recently that I started using xcode and started debugging too. I was not able to figure out what the issue was. Also if I make any changes to my code specifically the last if block, somehow my code turns into an infinite loop! Which is very weird. Any help or guidance would be highly appreciated.

Expected o/p: 1,5,6,7,7,7,7,8,9,11,23

o/p that I am getting: 1 5 6 7 7 9 7 7 8 11 15 23


int quicksort(int arr[], int s, int e)
{

    int pivot = arr[s];
    int count_smaller_than_pivot=0;

    //creating a counter to count the elements smaller or equal to the pivot

    for(int i =s+1 ; i<=e; i++) {
        if (arr[i] <= pivot) {
            count_smaller_than_pivot++;

        }
    }

    //to place the pivot at it's correct posiition.

    int pivot_index= s+count_smaller_than_pivot;

    //swapping the values

    int temp = arr[s];
    arr[s] = arr[pivot_index];
    arr[pivot_index]= temp;

    int i=s;
    int j=e;

    while(i<pivot_index && j>pivot_index) {

        while (arr[i] < pivot) {
            i++;
        }

        while  (arr[j] > pivot) {
            j--;
        }

        // if we find some value which is greater than pivot_index on the left or smaller than pivot_index in the right then we would need to swap
        if(i<pivot_index && j>pivot_index) {
            int temp2= arr[i];
            arr[i] = arr[j];
            arr[j] = temp2;
            i++;
            j--;
            

        }

    }



    return pivot_index;
}

void recursive_func(int arr[], int s, int e)
{
    if (s>=e)
        return;
    int p = quicksort(arr,s,e);
    //sorting the left part
    recursive_func(arr,s ,p-1);
    //sorting the right part
    recursive_func(arr,p+1, e);

}

#include <iostream>
using namespace std;

int main()
{

    int n=12;
    int arr[12]= {11,6,8,23,9,1,5,15,7,7,7,7};

    quicksort(arr, 0, n-1);
    recursive_func(arr,0,n-1);

    for(int i=0; i<n; i++) {
        cout<<arr[i]<<" ";
    }

    return 0;
}
Coding_templar
  • 41
  • 2
  • 8
  • Don't use JavaScript snippets for a C++ code. – 273K Jul 08 '23 at 01:10
  • Why do you post the code with the working input? Why don't you post a [mcve] with data that you code can't work with? – 273K Jul 08 '23 at 01:12
  • 2
    When you used a debugger, which statement is giving you issues? Please indicate in your code that statement. Also show the actual versus expected values of all variables involved. – Thomas Matthews Jul 08 '23 at 01:18
  • 3
    [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – Evg Jul 08 '23 at 01:25
  • Debugging tip: smaller examples are easier to figure out than large ones. Try it with an array of two or three values to begin with; if you can't get it to fail, go a bit bigger. Tracing through recursive calls with an array of 12 elements is tedious and confusing. – Pete Becker Jul 08 '23 at 12:05

1 Answers1

3

The code is using a variation of Hoare Partition scheme, where the pivot or values equal to the pivot can end up anywhere. In order to avoid having to check for scanning out of bounds, Hoare relies on stopping the two inner while loops if a value == pivot is encountered:

while(a[i] < pivot)
...
while(a[j] > pivot)

Problem cases: a[i] == pivot and a[j] == pivot; a[i] > pivot and a[j] == pivot; a[i] == pivot and a[j] < pivot. This is why the pivot or values equal to the pivot can end up anywhere.

Although the question code attempts to deal with this using count_smaller_than_pivot, it won't work because values equal to pivot can end up to the left or right of pivot_index.

To deal with this, the index returned by Hoare partition is just a separator for values <= pivot and values >= pivot, and the returned index needs to be included in one of the next partition steps.

The alternative is to use Lomotu partition scheme, but that is generally slower.

https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme

rcgldr
  • 27,407
  • 3
  • 36
  • 61