Quicksort Depends on Choosing Pivot

Question

This is my quicksort algorithm, including partition and swap. Works well, when I'm choosing as a pivot the last element of the array (in function quicksort: int r = partition(a, n, n);), but fails when taking the first: int r = partition(a, n, s);

void Swap(int a[], int l, int r){
int tmp = a[l];
a[l] = a[r];
a[r] = tmp;
}

int partition(int a[], int n, int p) {
Swap(a, p, n);
int l = 0;
for (int i = 1; i <= n - 1; i++) {
    if (a[i] <= a[n]) {
        l += 1;
        Swap(a, l, i);
        }
    }
Swap(a, p, l + 1);
return l + 1;
}

void quicksort(int a[], int s, int n) {
if (s < n) {
    int r = partition(a, n, n);
    quicksort(a, s, r - 1);
    quicksort(a, r + 1, n);
    }
}

It seems that you never do anything with the first element of the array (a[0]) — Yksisarvinen
Yes, it indexes from one, I'm trying to work out 0 indexed version. @Bartek Banachewicz: That's what I'm trying to figure it out, should work well for any pivot (apart of effeciency). — Tom
You have several problems with this code, but the key one as far as this question is concerned is that having swapped the pivot element from index p to index n at the beginning of partition(), you need to swap it from n into its final position at the end. Instead, you swap whatever element then happens to be at index p into the pivot position, which is correct only if n == p. — John Bollinger
The code uses a variation of Lomuto partition scheme, which chooses the left or right element as a partition element, then swaps as the final step of each partition step. Variations of Hoare partition scheme can choose any element as the pivot, and are usually faster. — rcgldr

Tom Tom · Accepted Answer · 2019-01-27T13:02:22

Yes, the problem was with the partition procedure, this one is correct:

int partition(int a[], int p, int r) {
int t = a[r];
int i = p - 1;
for (int j = p; j < r;j++){
    if (a[j] <= t) {
        i += 1;
        std::swap(a[i], a[j]);
    }
}
std::swap(a[i + 1], a[r]);
return i + 1;

}

Quicksort Depends on Choosing Pivot

1 Answers