Ошибка быстрой сортировки: стек вокруг переменной поврежден?

Question

Ошибка быстрой сортировки: стек вокруг переменной поврежден?

Я реализую функцию быстрой сортировки для класса. Мы должны сделать это так же, как она учила нас в классе со своим псевдокодом, иначе мы не получим кредит.

Я получаю ошибка выполнения что говорит «Стек вокруг переменной ‘quickArray’ поврежден«

Я играл с отладчиком, и до сих пор не могу понять, в чем проблема. Я думаю, что это как-то связано с моей функцией Partition (), но я не уверен. Кто-нибудь может помочь? Iv опубликовал функции main (), QuickSort () и Partition () ниже.

int main()
{int quickArray[10] = { 5 ,99, 32, 4, 1, 12, 15 , 8, 13, 55};
int P = quickArray[0];
int R =quickArray[9];

QuickSort(quickArray,P,R);
return 0;

}

………………………………………………………………………………

void QuickSort(int ar2[],int P, int R)
{
int Q;

if( P < R )
{
Q =  Partition(ar2,P,R);
QuickSort(ar2,P,Q-1);
QuickSort(ar2,Q+1,R);
}

}

……………………………………………………………………………….

int Partition(int ar2[],int P, int R)
{
int x = ar2[R];
int i = P-1;
int temp;

for(int j = P; j <= R-1; j++)
{
if( ar2[j] < x  )
{
i = i +1;
temp = ar2[i];
ar2[i] = ar2[j];
ar2[j] = temp;
}

temp = ar2[R];
ar2[R] = ar2[i+1];
ar2[i+1] = temp;
}

return (i+1);
}

1

c++corruption quicksort

Решение

Другие решения

Вы передаете неправильные индексы в функцию быстрой сортировки:

int P = quickArray[0];
int R =quickArray[9];

P и R являются индексами массива, в этом случае они должны быть 0 и 9, однако вы передавали первый элемент и последний элемент как индекс в QuickSort, 55 (quickArray [9]) выходит за пределы индекса quickArray, поэтому вы получили Ошибка.

Кстати: лучше использовать описательные имена переменных, P и R не очень хорошо выражены, что они означают в этом случае. Вы можете использовать left, right и pivot для замены R, R и Q соответственно, как описано в алгоритме быстрой сортировки.

2

это

int P = quickArray[0];
int R = quickArray[9];

QuickSort(quickArray,P,R);

Должно быть так:

int arrStartIndex = 0;
int arrEndIndex   = 9;

QuickSort(quickArray, arrStartIndex , arrEndIndex);

Как отмечают другие, ваш код должен использовать более описательные имена.

0

Источник

Accepted Answer

Вы передаете фактические элементы массива, а не индексы, быстрый способ отладки это будет cout на вершине QuickSort вот так:

void QuickSort(int ar2[],int P, int R)
{
std::cout << "P: " << P << " R: " << R << std::endl ;
...

а также cout после Partition вызов:

  Q =  Partition(ar2,P,R);

std::cout << "QS: Q= " << Q << std::endl ;

исправить будет позвонить QuickSort от main вот так:

 QuickSort(quickArray,0,9);

Проведение некоторого времени с отладчиком в долгосрочной перспективе поможет вам обнаружить эти ошибки намного быстрее.

2