Why is this Quick Sort implementation giving a weird output

Question

My Quick Sort is giving a weird output.Some sections of the output are sorted while some some sections are just random.I am using pivot element to partition the array recursively using partition function into 2 halves with the left half elements less than the pivot element and right half elements greater than the pivot element.

#include <iostream>
using namespace std;

int partition(int *arr, int start, int end)
{
    int pivot = start;
    int temp;
    int temp2;

    while (start < end)
    {
        while (arr[start] <= arr[pivot])
            start++;
        while (arr[end] > arr[pivot])
            end--;

        if (start < end)
        {
            temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
    }
    temp2 = arr[pivot];
    arr[pivot] = arr[end];
    arr[end] = temp2;
    return end;
}

void quickSort(int input[], int size)
{
    int lb = 0;
    int ub = size - 1;
    int loc;
    if (lb < ub)
    {
        loc = partition(input, lb, ub);
        quickSort(input, loc - 1);
        quickSort(input + loc + 1, ub - loc);
    }
    else
        return;
}

int main()
{
    int n;
    cin >> n;

    int *input = new int[n];

    for (int i = 0; i < n; i++)
    {
        cin >> input[i];
    }

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

    delete[] input;
}

This seems like a good time to learn how to use a debugger to step through you code statement by statement, while monitoring variables and their values. That way you can easily seem when and where something unexpected is happening, like for example out-of-bounds indexing or similar. — Some programmer dude, Dec 18 '19 at 16:40
[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5910058) — Jesper Juhl, Dec 18 '19 at 16:44

score 0 · Accepted Answer · answered Dec 18 '19 at 16:55

in this part when you try to sort the array from the location start to pivot you have

quickSort(input, loc - 1);    
quickSort(input + loc + 1, ub - loc);

which means input[loc] is never treated since you go from 0 to loc -1 and loc +1 to end

which is corrected here

if (lb < ub)
{
    loc = partition(input, lb, ub);
    quickSort(input, loc );
    quickSort(input + loc + 1, ub - loc);
}

Why is this Quick Sort implementation giving a weird output

1 Answers1