Partition in quick sort logical error

Question

int partition(int A[], int low, int high){
    int mid = (low+high)/2;
    int pivot = A[mid];
    while(low <= high) {
        while(low <= high && A[high] >= pivot) {
            high--;
        }
        while (low <= high && A[low] <= pivot) {
            low ++;
        }
        if(low <= high) {
            int tmp = A[low];
            A[low] = A[high]; 
            A[high] = tmp;
            high--;
           low++;
        }
    }
    return mid;
}

void quickSort(int A[], int low, int high) {
    if (low >= high) {
      return;
    }
    int ppos = partition(A, low, high);//does the swapping and returns the pivot
    quickSort(A, low, ppos-1);
    quickSort(A, ppos+1, high);
}

This is my quicksort function with a partition to do the swapping and return the pivot so that quicksort recalls itself with a different midpoint. I'm not too familiar with quicksort but this is what i came up with.

The problem is that it compiles fine but when it runs it always crashes. Is there a logical flaw with my functions? Any advice on how to fix my functions so that it'll do quicksort on a random array?

-edit- fixed the crashing error, but partition won't do the sorting properly, any suggestions to change the function so that it does quicksort on the array?

Answer 1

Your partition function is incorrect. There are two primary methods for partitioning a sequence during quicksort: the squeeze and the sweep. The former of these is the one you're attempting and has a high likelihood of fewer swaps than the latter method at the price of a more complicated algorithm.

---

The Sweep

I'll show you what the simpler sweep method looks like first, as it is honestly the simplest to understand. In general, the algorithm does the following:

1. Exit early if the sequence length is less than two. There is nothing to partition for a sequence of length-one.
2. Choose a pivot value in the sequence. Choosing a pivot value that reduces the chances of a O(N^2) degenerate condition is the holy-grail of quicksort partitioning, and I'll not cover it here, but there are plenty of writs on the subject available online.
3. Swap the pivot value with the last value in the sequence.
4. Walk the sequence with two index values; the reader index and the writer index. as you march up the sequence any reader-indexed value that is "less than" the pivot value is swapped into the lower sequence at the writer-index, and the writer index is incremented.
5. When finished, the writer index is the point where the pivot value is swapped into final position and the partition is complete. The resulting partition point returned is the writer index position.

This algorithm is actually easier to understand with code:

size_t partition(int A[], size_t len)
{
    if (len < 2) // 1.
        return 0;

    std::iter_swap(A+len/2, A+len-1); // 2. 3.
    size_t pvt = 0;

    for (size_t i=0; i<len-1; ++i) // 4.
    {
        if (A[i] < A[len-1])
            std::iter_swap(A + pvt++, A+i);
    }
    std::iter_swap(A + pvt, A+len-1); // 5.

    return pvt;
}

Note it is entirely conceivable values larger than the pivot value may well be swapped multiple times as the lower partition is filled during the march. Eventually it all settles out, but these additional swaps are ideally avoided. That is the purpose of the squeeze method, shown next.

---

The Squeeze

While the sweep has its advantages (most notable being simplicity), minimizing swaps is not among them. Ideally you only perform a swap when you have determined two values are out of place on opposite sides of the eventual landing home of the pivot value. To do this requires you perform a low-to-high sweep simultaneously with a high-to-low sweep, and as soon as each finds an element in the incorrect location, swap those. Eventually the low index and high index meet, and upon doing so you've found the pivot final resting place.

size_t partition(int A[], size_t len)
{
    if (len < 2)
        return 0;

    std::iter_swap(A + len/2, A+len-1);
    size_t low = 0, high = len;

    while (1)
    {
        while (low < high && (A[low] < A[len-1]))
            ++low;

        if (low == high--)
            break;

        while (low < high && !(A[high] < A[len-1]))
            --high;

        if (low == high)
            break;

        std::iter_swap(A+low++, A+high);
    }
    std::iter_swap(A+low, A+len-1);

    return low;
}

There a several things going on here that may seem odd. Note the boolean logic for the second inner-while loop that reduces high. I could have written (A[high] >= A[len-1]) but I wanted to drive home a common mistake. It is critical the condition which reduces high be logically inverse to that which promotes low. If low is promoted because its element is strictly less than the pivot value as we have it here, then high can only be reduced if its element is not (strictly less than the pivot value). The is no doubt we have it right when shown as coded above, and I simply cannot do justice to the number of times that specific requirement is glossed over and resulted in mysteriously broken partitioning algorithms.

---

Sample partitions with QuickSort

Either of the above will work. A few slight modifications to the functions to produce output when a swap happens and sorting a randomly shuffled array of values demonstrates the swap-count reduction. The following implements both algorithms in two partition functions, appropriately labeled sweep and squeeze. They are both turned loose on identical random sequences, then again on fully-sorted sequences to demonstrate the swap-count differences.

#include <iostream>
#include <algorithm>
#include <random>
#include <numeric>

size_t sweep(int A[], size_t len)
{
    if (len < 2)
        return 0;

    std::iter_swap(A+len/2, A+len-1);
    size_t pvt = 0;

    for (size_t i=0; i<len-1; ++i)
    {
        if (A[i] < A[len-1])
        {
            std::cout << "swap: " << A[pvt] << ',' << A[i] << '\n';
            std::iter_swap(A + pvt++, A+i);
        }
    }
    std::iter_swap(A + pvt, A+len-1);

    return pvt;
}

size_t squeeze(int A[], size_t len)
{
    if (len <= 1)
        return 0;

    std::iter_swap(A + len/2, A+len-1);
    size_t low = 0, high = len;

    while (1)
    {
        while (low < high && A[low] < A[len-1])
            ++low;

        if (low == high--)
            break;

        while (low < high && !(A[high] < A[len-1]))
            --high;

        if (low == high)
            break;

        std::cout << "swap: " << A[low] << ',' << A[high] << '\n';
        std::iter_swap(A+low++, A+high);
    }
    std::iter_swap(A+low, A+len-1);

    return low;
}

void quicksort(int A[], size_t len, size_t (*part)(int[], size_t))
{
    if (len < 2)
        return;

    size_t pvt = part(A, len);
    quicksort(A, pvt++, part);
    quicksort(A+pvt, len-pvt, part);
}

int main()
{
    std::random_device rd;
    std::mt19937 rng(rd());

    int ar[31] = {0}, ar2[31];
    std::iota(std::begin(ar), std::end(ar), 1);
    std::shuffle(std::begin(ar), std::end(ar), rng);
    std::copy(std::begin(ar), std::end(ar), std::begin(ar2));

    for (auto x : ar)
        std::cout << x << ' ';
    std::cout << '\n';

    std::cout << "Sweep Algorithm\n";
    quicksort(ar, sizeof(ar)/sizeof(*ar), sweep);

    for (auto x : ar)
        std::cout << x << ' ';
    std::cout << '\n';

    std::cout << "Squeeze Algorithm\n";
    quicksort(ar2, sizeof(ar2)/sizeof(*ar2), squeeze);

    for (auto x : ar2)
        std::cout << x << ' ';
    std::cout << '\n';

    std::cout << "Sweep Algorithm (sorted)\n";
    quicksort(ar, sizeof(ar)/sizeof(*ar), sweep);

    for (auto x : ar)
        std::cout << x << ' ';
    std::cout << '\n';

    std::cout << "Squeeze Algorithm (sorted)\n";
    quicksort(ar2, sizeof(ar2)/sizeof(*ar2), squeeze);

    for (auto x : ar2)
        std::cout << x << ' ';
    std::cout << '\n';
}

Output (random)

8 28 21 26 10 12 17 1 11 20 30 3 18 5 24 15 9 6 13 27 31 4 16 7 19 22 14 25 29 2 23 
Sweep Algorithm
swap: 8,8
swap: 28,10
swap: 21,12
swap: 26,1
swap: 28,11
swap: 21,3
swap: 17,5
swap: 26,9
swap: 28,6
swap: 20,13
swap: 30,4
swap: 21,7
swap: 18,14
swap: 17,2
swap: 8,8
swap: 10,1
swap: 12,3
swap: 10,5
swap: 11,2
swap: 12,6
swap: 10,4
swap: 11,7
swap: 8,1
swap: 3,3
swap: 5,5
swap: 7,4
swap: 3,3
swap: 4,4
swap: 3,3
swap: 7,7
swap: 13,10
swap: 12,12
swap: 13,13
swap: 12,12
swap: 23,20
swap: 26,16
swap: 28,19
swap: 23,18
swap: 27,17
swap: 20,16
swap: 20,17
swap: 20,18
swap: 16,16
swap: 30,22
swap: 24,24
swap: 30,26
swap: 31,28
swap: 30,27
swap: 26,26
swap: 27,27
swap: 26,26
swap: 30,30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 
Squeeze Algorithm
swap: 28,2
swap: 21,14
swap: 26,7
swap: 17,4
swap: 20,13
swap: 30,6
swap: 18,9
swap: 14,3
swap: 7,4
swap: 14,9
swap: 12,6
swap: 30,25
swap: 27,21
swap: 31,22
swap: 23,16
swap: 25,17
swap: 30,28
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 
Sweep Algorithm (sorted)
swap: 1,1
swap: 2,2
swap: 3,3
swap: 4,4
swap: 5,5
swap: 6,6
swap: 7,7
swap: 8,8
swap: 9,9
swap: 10,10
swap: 11,11
swap: 12,12
swap: 13,13
swap: 14,14
swap: 15,15
swap: 1,1
swap: 2,2
swap: 3,3
swap: 4,4
swap: 5,5
swap: 6,6
swap: 7,7
swap: 1,1
swap: 2,2
swap: 3,3
swap: 1,1
swap: 5,5
swap: 9,9
swap: 10,10
swap: 11,11
swap: 9,9
swap: 13,13
swap: 17,17
swap: 18,18
swap: 19,19
swap: 20,20
swap: 21,21
swap: 22,22
swap: 23,23
swap: 17,17
swap: 18,18
swap: 19,19
swap: 17,17
swap: 21,21
swap: 25,25
swap: 26,26
swap: 27,27
swap: 25,25
swap: 29,29
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 
Squeeze Algorithm (sorted)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 

Best of luck.

Answer 2

Here is is an implementation using a partition index:

void swap(int A[], int i1, int i2){
    int temp=A[i1];
    A[i1]=A[i2];
    A[i2]=temp;
}

int partition(int A[], int low, int high){
    int partitionIndex, i, pivot;

    pivot = A[high];
    partitionIndex=low;

    for(i=low; i < high; i++){
        if(A[i]<=pivot){
            swap(A,i,partitionIndex);
            partitionIndex++;
        }
    }
    swap(A,high,partitionIndex);
    return partitionIndex;
}

void quickSort(int A[], int low, int high) {
    if (low < high){
        int ppos = partition(A, low, high);//does the swapping and returns the pivot
        quickSort(A, low, ppos-1);
        quickSort(A, ppos+1, high);
    }
}

I could not figure out what was wrong with your code. In the middle of debugging i noticed that you edited the code in the question. Hope the above code helps you in root causing the issue.

Answer 3

It seems that you're returning the value of the pivot instead of its position in the partition function.