глубина стека для быстрой сортировки

Question

я использую хвостовую рекурсивную версию быстрой сортировки, вот мой код

  #include <iostream>
using namespace std;

int partition(int a[],int l,int r){
    int pivot=a[l];
     std::swap(a[pivot],a[r]);
      int store=l;
       for (int i=l;i<r;i++){
           if (a[i]<=pivot){
               std::swap(a[i],a[store]);
           store=store+1;
           std::swap(a[store],a[r]);
           }

       }
        return store;
}
void tail_quick(int a[],int p,int r){

    while(p<r){

    int  q=partition(a,p,r);
     tail_quick(a,p,q-1);
     p=q+1;
    }
}
int main(){
    int a[]={21,10,13,8,56,9,34,11,22,44};
    int n=sizeof(a)/sizeof(int);
    tail_quick(a,0,n-1);
     for (int i=0;i<n;i++)
         cout<<a[i]<<"  ";



     return 0;
}

но вывод неверный не отсортирован, а также выводятся случайные числа, помогите

Answer 1

У вас есть несколько проблем.

Во-первых, в partition () вы перепутали опорный индекс INDEX с опорным значением VALUE. VALUE - это то, что следует использовать для сравнений, а для свопа следует использовать начальный индекс INDEX. Так как вы используете первый элемент в качестве вашего стержня (не лучший для производительности), вы должны изменить первый своп, чтобы использовать «l» вместо «сводного». Обратите внимание, что вы используете первое значение массива в качестве индекса.

Далее, "последний" обмен должен выполняться вне цикла for, а не на каждой итерации. Таким образом, ваша функция partition () должна выглядеть так:

int partition(int a[],int l,int r){
    int pivot=a[l];
    std::swap(a[l],a[r]);
    int store=l;
    for (int i=l;i<r;i++){
      if (a[i]<=pivot){
        std::swap(a[i],a[store]);
        store=store+1;
      }
    }
    std::swap(a[store],a[r]);
    return store;
}

Ваша функция tail_quick () работает, но будет лучше, если просто сделать два рекурсивных вызова, например ...

void tail_quick(int a[],int p,int r){
    if (p < r){
      int  q=partition(a,p,r);
      tail_quick(a,p,q-1);
      tail_quick(a,q+1,r);
    }
}

Однако вы ДОЛЖНЫ использовать для этого стандартную библиотеку, поскольку она даст вам правильный ответ и обеспечит наилучшую производительность.

Answer 2

Вы используете неинициализированную переменную при вызове partition ниже. Вы уверены, что это не должно быть что-то еще?

void tail_quick(int a[],int p,int r){

    while(p<r){

    int  q=partition(a,p,q); // <--- uninitialized variable "q"
     tail_quick(a,p,q-1); 
     p=q+1;
    }
}