Ошибка программы сортировки (HEAP CORRUPTION DETECTED)
Эта программа о времени пузырьковой сортировки, вставки и сортировки.
Я запустил свою программу и получил ошибку отладки,
HEAP CORRUPTION DETECTED:after Normal block(#152)at 0x006613C0 CRT Detected
чтобы приложение записывало в память после завершения буфера кучи.
Затем я удаляю последние 3 строки кода (delete [] a; delete [] b; delete [] c) в void part_1(int n) чтобы это работало. И мой профессор сказал мне: «Ваша программа должна иметь другие ошибки, эти ошибки вызывают
ошибки в операторах удаления. «и я не должен удалять последние 3 строки кода. Я не могу найти его. Пожалуйста, помогите.
// Part-1 : --------------------------- sorting algorithms
void bubbleSort(double *x, int n)
{
// Implement the sorting function using the bubble sort algorithm.
double temp;
for (int j = 0;j < n;j++) {
for (int i = 0;i < n;i++) {
if (x[i] > x[i + 1]) {
temp = x[i];
x[i + 1] = x[i];
x[i + 1] = temp;
}
}
}
}void insertionSort(double *x, int n)
{
// Implement the sorting function using the insertion sort algorithm.
for (int i = 1;i < n;i++) {
double temp = x[i];
int j = 0;
for (j = i - 1;j >= 0 && x[j]>temp;j--) {
x[j + 1] = x[j];
}
x[j + 1] = temp;
}
}int compare_1(const void *a, const void *b) {
double *X = (double *)a;
double *Y = (double *)b;
if (*X > *Y) {
return 1;
}
else if (*X < *Y)
return -1;
return 0;
}
void part_1(int n)
{
srand((unsigned)time(NULL)); // set the seed of the random number generator
double *a = new double[n]; // create 3 arrays with identical contents
double *b = new double[n];
double *c = new double[n];
for (int i = 0; i < n; i++)
a[i] = b[i] = c[i] = rand() / 10000.0;
clock_t begin, end;
double elapsedTime;
cout << "Bubble sort: sorting an array of size " << n << endl;
begin = clock();
bubbleSort(a, n);
end = clock();
elapsedTime = (double)(end - begin) / CLOCKS_PER_SEC;
cout << "Elapsed time = " << elapsedTime << " seconds" << endl << endl;
for (int i = 0; i < n - 1; i++)
if (a[i] > a[i + 1])
{
cout << "Bubble sort : Incorrect results\n\n";
break;
}
cout << "Insertion sort: sorting an array of size " << n << endl;
begin = clock();
insertionSort(b, n);
end = clock();
elapsedTime = (double)(end - begin) / CLOCKS_PER_SEC;
cout << "Elapsed time = " << elapsedTime << " seconds" << endl << endl;
for (int i = 0; i < n - 1; i++)
if (b[i] > b[i + 1])
{
cout << "Insertion sort : Incorrect results\n\n";
break;
}
cout << "Write your statements to sort array c[] using qsort()\n";
cout << "qsort: sorting an array of size " << n << endl;
begin = clock();
// #### write your statements to sort array c[] using qsort().
// Define your own compare function.
qsort(c, n, sizeof(double), compare_1);
end = clock();
elapsedTime = (double)(end - begin) / CLOCKS_PER_SEC;
cout << "Elapsed time = " << elapsedTime << " seconds" << endl << endl;
for (int i = 0; i < n - 1; i++)
if (c[i] > c[i + 1])
{
cout << "qsort : Incorrect results\n\n";
break;
}
delete[] a;
delete[] b;
delete[] c;
}
int main()
{
part_1(50000);
system("pause");
return 0;
}
Решение
Эта ошибка возникает из-за повреждения памяти. Повреждение памяти произошло из-за того, что вы записали за предел массива.
Например: если есть массив из 5 целых чисел, например
int array[5];
Вы не должны делать такие вещи, как
int n=4;
array[n+1] = 10; //array out of bound memory write operation
C / C ++ не проверяет массив вне связанной операции. Это разрешает такую операцию без ошибки компиляции. В результате, когда вы запускаете программу, может произойти все что угодно. Поэтому ответственность за проверку таких ошибок лежит на программисте.
Один такой экземпляр найден в вашем коде.
void bubbleSort(double *x, int n)
{
// Implement the sorting function using the bubble sort algorithm.
double temp;
for (int j = 0;j < n;j++) {
for (int i = 0;i < n;i++) {
if (x[i] > x[i + 1]) {
temp = x[i];
x[i + 1] = x[i]; // out of bound write when i=n-1.
x[i + 1] = temp;
}
}
}
}
Другие решения
В bubbleSort Ваш индекс массива выходит за пределы диапазона. Измените функцию, как показано ниже, и вы увидите, что происходит:
void bubbleSort(double *x, int n)
{
// Implement the sorting function using the bubble sort algorithm.
double temp;
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
if (i + 1 >= n)
{ // index is out of range
cout << "Bummer\n";
exit(1);
}
if (x[i] > x[i + 1]) {
temp = x[i];
x[i + 1] = x[i];
x[i + 1] = temp;
}
}
}
}
Там, скорее всего, аналогичные проблемы в других ваших функций сортировки.