Сортировка qsort - Stack overflow, нарушение прав доступа при записи по адресу - C (СИ)
Формулировка задачи:
Найдите, пожалуйста, ошибку в коде. Программа завершается с ошиибкой Stack overflow, и нарушение прав доступа при записи по адрессу.
#include <stdio.h>
#include <stdlib.h>
void qsrt(int a[], int low, int hig)
{
int i=low,j=hig,p=((low+hig)/2);
int tmp;
while(i<j)
{
while(a[i]<=a[p]) i++;
while(a[j]>=a[p]) j--;
if(i<=j)
{
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
i++; j--;
}
}
if(low<j) qsrt(a,low,j);
if(hig>i) qsrt(a,i,hig);
}
int main()
{
int t[100];
int i;
srand(time(NULL));
for (i=0;i<100;i++) t[i]=rand()%300;
qsrt(t,0,99);
for (i=0; i<100;i++) printf("%d\n",t[i]);
getchar();
return 0;
}Решение задачи: «Сортировка qsort - Stack overflow, нарушение прав доступа при записи по адресу»
textual
Листинг программы
void qsrt(int a[], int low, int hig)
{
int i=low,j=hig,p=a[(low+hig)/2];
int tmp;
while(i<j)
{
while(a[i]<p) i++;
while(a[j]>p) j--;
if(i<=j)
{
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
i++; j--;
}
}
if(low<j) qsrt(a,low,j);
if(hig>i) qsrt(a,i,hig);
}
Объяснение кода листинга программы
В данном коде реализована сортировка массива методом Quick Sort.
- В первой строке определяется начальный индекс (low), конечный индекс (hig) и средний элемент массива (p).
- Затем, в цикле while(i<j), происходит сравнение элементов массива a[i] и p. Если a[i] меньше p, то i увеличивается на единицу, иначе, если a[i] больше p, то i уменьшается на единицу.
- В следующей итерации цикла, в while(a[i]<p), происходит смещение элемента p влево, путем увеличения индекса i до тех пор, пока не будет найден элемент, меньший p.
- Аналогично, в while(a[j]>p), происходит смещение элемента p вправо, путем уменьшения индекса j до тех пор, пока не будет найден элемент, больший p.
- Если в процессе выполнения циклов были произведены перемещения элементов, то значения i и j сдвигаются на единицу вперед и назад соответственно.
- Если i меньше или равно j, то происходит обмен элементов a[i] и a[j].
- Если i больше j, то выполнение функции завершается.
- Если в процессе выполнения функции были найдены элементы, меньшие или большие p, то рекурсивно вызывается функция qsrt для соответствующих диапазонов массива. Поскольку в коде отсутствует вызов функции qsrt, то предполагается, что данная функция вызывается для всего массива в начале кода. Примечание: Данный код может вызвать переполнение стека при больших значениях low и hig, поскольку функция qsrt рекурсивно вызывается для все более узких диапазонов массива, пока не будет найден элемент, меньший или больший p.