How does the quicksort function work in a quicksort algorithm?

Question

I've understood how the partitioning part is done in the quicksort algorithm, but I'm having trouble understanding the quicksort recursive function. Could someone please explain to me step by step how it works? I'm pasting here the C++ code.

using namespace std;

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int myArray[], int low, int high) {
    int i = (low - 1);
    int pivot = myArray[high];

    for (int j = low; j <= high - 1; j++) {
        if (myArray[j] < pivot) {
            i++;
            swap(&myArray[i], &myArray[j]);
        }
    }
    swap(&myArray[i + 1], &myArray[high]);
    return (i + 1);
}

void quickSort(int myArray[], int low, int high) {

    if (low < high) {
        int pi = partition(myArray, low, high);

        quickSort(myArray, low, pi - 1);
        quickSort(myArray, pi + 1, high);
    }
}

void cinArray(int myArray[], int n) {
    for (int p = 0; p < n; p++) {
        cin >> myArray[p];
    }
}

void print(int myArray[], int n) {
    for (int z = 0; z < n; z++) {
        cout << myArray[z] << "	";
    }
}

int main() {
    int myArray[10];
    int size = sizeof(myArray) / sizeof(myArray[0]);
    cout << "Write 10 numbers: ";
    cinArray(myArray, size);
    quickSort(myArray, 0, size - 1);
    print(myArray, size);
    return 0;
}

My logic by far (step by step) is the following:

if (low < high) will always be true. The first time, the low (0) and high (9) values are taken from the int main.
Pi will be equal to the returned value of the partition funcion (i+1), and I suppose that in order to return that value the function has to run first.
We call the quicksort function giving new arguments for the function twice. Once for the values before and once for the values after i+1 from the original partitioning. I want to focus on what happens on the first one, the one that has the values before i+1.
Function starts again, the if statement is true (always is), pi calls the function partition and returns i+1, pi is equal to i+1. And what if at this point the values are still not sorted? I suppose the quicksort function restarts again (It feels like a loop). But since the IF statement will always be true, when will this loop situation stop?
Also, assuming my logic at point 4 is correct, how is the code run the first time? Does it start with the first quickSort(myArray, low, pi - 1); function call and loops until something stops it and then does the same for the second call quickSort(myArray, pi + 1, high);? Or does it partition before i+1 then after i+1 and restarts the function?

I know it's a basic question, but I'm really having a hard time wraping my head around this algorithm.

500 - Internal Server Error · Accepted Answer

if (low < high) will always be true.

Not correct. It will be true on the first call, but QuickSort calls itself recursive with progressively smaller intervals between low and high. This if is why the algorithm eventually terminates - you ask about that below.

Pi will be equal to the returned value of the partition funcion (i+1)

Right. pi is short for pivot index, i.e. the location where the chosen pivot ended up after partitioning.

And what if at this point the values are still not sorted?

After partitioning, you know that no value in the left partition is greater than the pivot value and that no value in the right partition is less than the pivot value. That's all you know, and all the algorithm needs to know in order to eventually succeed. Each partition is recursively partitioned until it only has one element in it.

when will this loop situation stop?

See my first point.

How does the quicksort function work in a quicksort algorithm?

Answers (2)

Related Questions