0

I have written a code for quick sort in c++ but it's giving an error for few inputs. For example : On Entering No. of elements = 5 with the inputs as 5 4 3 2 1 , it shows incorrect output for one iteration. It gives wrong output only on entering consecutive numbers in decreasing order.

#define MAX 100
class quicksort
{
  public:
    int arr[MAX], n;
    void getdata();
    void quick(int, int);
    void display();
};
void quicksort::getdata()
{
    int i;
    cout << "\nEnter Array Size : ";
    cin >> n;
    cout << "\nEnter Array Elements : ";
    for (i = 0; i < n; i++)
    {
        cout << "\nEnter Element [" << i << "] : ";
        cin >> arr[i];
    }
}
void quicksort::quick(int start, int end)
{
    int pivot = start, i = pivot + 1, j = end, temp;
    while (i <= j)
    {
        while (arr[i] < arr[pivot])
        {
            if (i == end - 1 || j <= i)
                break;
            i++;
        }
        while (arr[j] >= arr[pivot])
        {
            j--;
            if (j < i)
                break;
        }
        if (i < j)
        {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        else
        {
            temp = arr[j];
            arr[j] = arr[pivot];
            arr[pivot] = temp;
        }

        if (j != start)
            quick(start, j - 1);
        if (j != end)
            quick(j + 1, end);
    }
}

int main()
{
    quicksort s;
    s.getdata();
    s.quick(0, (s.n - 1));
    s.display();
    return 0;
}
Vishaal Shankar
  • 1,648
  • 14
  • 26
Dev0395
  • 9
  • 1
  • 1
    Quicksort is a very well known algorithm with a few good implementations. Yours doesn't look like any of them. I recommend looking up a reference implementation and comparing yours with it. – user4581301 Feb 09 '18 at 04:25
  • 1
    You should try debugging it with a debugger before asking it here. Also, try to create a [minimal, complete, and verifiable example](https://stackoverflow.com/help/mcve). – eesiraed Feb 09 '18 at 04:58
  • Is it a requirement that the algorithm is quick sort? Have you considered using std::sort instead of just writing your own sort algorithm? [http://en.cppreference.com/w/cpp/algorithm/sort](http://en.cppreference.com/w/cpp/algorithm/sort) – Dave Feb 09 '18 at 05:46
  • 1
    I haven't read the whole code but the recursion indices `j - 1` and `j + 1` look strange to me. The element at index `j` is omitted. – clemens Feb 09 '18 at 07:09

0 Answers0