-2

I have written this quick sort algorithm but it doesn't work properly for some reason, I need some help to find out the error.

I tried not to use built-in swap function however it didn't work out.

FindPivot function returns the median of three elements (start, half, end) of the array after swapping them so that the smallest one is at the start, the greatest at the middle and the median at the end of the array

#include <bits/stdc++.h>

using namespace std;

int pivotIdx, pivot, n;

int partitn(int* arr, int first, int last)
{
    pivot = FindPivot(arr,first,last-1);
//    pivot = arr[last-1];
    cout << "Pivot: " << pivot << endl;
    int L = first;
    int R = last-2;

    while(L<R)
    {
        while(arr[L]<=pivot)
            L++;
        while(arr[R]>=pivot)
            R--;
        swap(arr[L++],arr[R--]);
    }
    swap(arr[L],arr[last-1]);
    return L;
}

void QuickSort(int* arr,int first,int last)
{
    if(last-first < 6){
        InsertionSort(arr,first,last);
    }else{
        pivotIdx = partitn(arr, first, last);
        QuickSort(arr, first, pivotIdx);
        QuickSort(arr, pivotIdx+1, last);
    }
}

int main()
{
    cin >> n;
    int arr[100];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    QuickSort(arr,0,n);
    for(int i=0;i<n;i++){
        cout << arr[i] << " ";
    }
    return 0;
}

Input:

8

5 1 6 2 7 3 8 4

Output:

Pivot: 4

1 2 3 5 4 6 7 8

Zeyad Elsayed
  • 1
  • 3
  • 4
    The most helpful tool for finding the error is your debugger. Step through your program's execution and examine your data. That will lead you to discover any parts of your program that do not behave the way you expect. – paddy Jul 15 '19 at 23:42
  • 5
    I highly encourage you to learn how to use a *debugger*. With a good debugger, you can step through your code line by line and inspect values of variables to easily catch logic flaws. Also, I recommend you reading [how to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). – Fureeish Jul 15 '19 at 23:43
  • It looks like you are trying to implement Hoare Partitioning. When implementing a widely known algorithm, I always find it helpful to compare against [a canonical implementation](https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme) and focus my attention on the differences. – user4581301 Jul 15 '19 at 23:45
  • 1
    You should never `#include `. It is not proper C++. It ruins portability and fosters terrible habits. See [https://stackoverflow.com/q/31816095](https://stackoverflow.com/q/31816095). – L. F. Jul 16 '19 at 00:14
  • 1
    Also, please avoid `using namespace std;`. It is considered bad practice. See [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/q/1452721) – L. F. Jul 16 '19 at 00:14

2 Answers2

1

There may be other issues, but the current partition code could scan past the boundaries of the sub-array. Assuming the pivot is not at either end of the sub-array, the code can < instead of <= and > instead of >= and the scans will not run past the boundaries.

        while(arr[L]<pivot)    // not <=
            L++;
        while(arr[R]>pivot)    // not >=
            R--;
rcgldr
  • 27,407
  • 3
  • 36
  • 61
-1

Input:

5 1 6 2 7 3 8 4

This becomes:

QuickSort([5 1 6 2 7 3 8 4], 0, 8)
partitn([5 1 6 2 7 3 8 4], 0, 8)

   pivot = 4
   L = 0 R = 6       [5 1 6 2 7 3 8 4]

   // Enter Loop
   L = 0 R = 5 swap  [3 1 6 2 7 5 8 4]
   L = 2 R = 3 swap  [3 1 2 6 7 5 8 4]
   L = 3 R = 2 swap  [3 1 6 2 7 5 8 4]
   // Exit Loop
   L = 3       swap  [3 1 6 4 7 5 8 2]    This looks wrong.
                                          The 2 and 6 are in the wrong place.
Martin York
  • 257,169
  • 86
  • 333
  • 562
  • I'm not sure how this answers the question. –  Jul 16 '19 at 03:06
  • @Chipster: Quick sort splits the array into partition based on a pivot value. Everything to the left of the pivot value should be smaller than it everything to the right should be greater. Since the 6 is on the left of the pivot (4) and 2 is on the right of the pivot there is a bug in the loop. I am simply pointing out that the OP could solve this using a pencil and piece of paper since they have such a simple input that shows a wrong output. Also teaching somebody to fish rather than giving them a fish way be more useful. – Martin York Jul 16 '19 at 06:41
  • but it feels like this answer neither gives the OP a fish, nor teaches them to fish. It merely gives input and cryptic output with little or no explanation as to what it is. –  Jul 16 '19 at 17:25
  • @Chipster Your new to this site. You should read more answers. https://stackoverflow.com/help/how-to-answer – Martin York Jul 17 '19 at 17:18