Быстрая сортировка зависит от выбора точки разворота

Question

Это мой алгоритм быстрой сортировки, включая раздел и своп. Хорошо работает, когда я выбираю в качестве точки разворота последний элемент массива (в функции quicksort: int r = partition(a, n, n);), но не получается при взятии первого: 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);
    }
}

Answer 1

Да, проблема была в процедуре partition, это правильно:

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;

}