进程以 return 值 3221225725 退出 - quicksort worstcase with malloc crashing，如何解决？ - C

Question

我制作了一个程序来测量 int 的 n 个数据数组的排序时间。不幸的是，在最坏的情况下，我的快速排序在数组崩溃程序中大约有 30000 个数字，return 值为 3221225725。对于平均情况，即使对于 500000 个数字（这是我测试的最大值）它也能正常工作。

这是快速排序的代码：

int part(int *tab, int left, int n)
{
    int first = tab[left], i = left, j = n;
    while (0 != 1)
    {
        while (tab[j] > first)
        {
            j--;
        }   
        while (tab[i] < first)
        {
            i++;
        }
        if (i < j)
        {
            swap(&tab[i], &tab[j]);
            i++;
            j--;
        }
        else 
            return j;
    }
}

void quick_sort(int *tab, int left, int n)
{
    int pivot;
    if (left < n)
    {
        pivot = part(tab, left, n);
        quick_sort(tab, left, pivot);
        quick_sort(tab, pivot + 1, n);
    }
}

下面是数据案例的 for 循环代码：

#include <stdio.h>
#include <stdlib.h>
#include "algorytmy.h"
#include <time.h>

int main(int argc, char *argv[]) {
    srand(time(NULL));
    int n;
    clock_t czas1, czas2, czas3;
    FILE *fw;
    if (!(fw = fopen("danedowykresu_odwrotnie_zestaw2cd.txt", "w")))
    {
        printf("Blad otwarcia zbioru\n");
        exit(2);
    }
    fprintf(fw,"Liczba danych;quicksort;shellsort;heapsort\n");
    printf("Liczba danych;quicksort;shellsort;heapsort\n");
    for(n = 25000; n < 500000; n += 1000)
    {
        int tab[n], i;
        int *ptr = (int *)malloc(n * sizeof(int));
        for (i = 0; i < n; i++) 
            ptr[i] = n - i;
        
        czas1 = clock();
        quick_sort(ptr, 0, n);
        czas1 = clock() - czas1;
        free(ptr);
        
        for (i = 0; i < n; i++) 
            tab[i] = n - i;
        czas2 = clock();
        shell_sort(tab, n);
        czas2 = clock() - czas2;
        
        for (i = 0; i < n; i++) 
            tab[i] = n - i;
        czas3 = clock();
        heap_sort(tab, n);
        czas3 = clock() - czas3;
        
        fprintf(fw,"%d;%f;%f;%f\n", n, ((float)czas1) / CLOCKS_PER_SEC, ((float)czas2) / CLOCKS_PER_SEC, ((float)czas3) / CLOCKS_PER_SEC);
        printf("%d;%f;%f;%f\n", n, ((float)czas1)/CLOCKS_PER_SEC, ((float)czas2) / CLOCKS_PER_SEC, ((float)czas3) / CLOCKS_PER_SEC);  
    }
    fclose(fw);
    return 0;
}

console screen

Answer 1

您的实施不正确：不清楚您使用 if (pocz < n) 测试的内容。纯实现将测试 if (n - left > 1)。 part() 函数也有问题：i 和 j 没有正确初始化。在尝试衡量性能之前验证正确性始终是一个好主意。

快速排序最坏情况的问题是递归太深，最终会遇到堆栈溢出。

这是一个修改版本，使用一种简单的方法来防止深度递归：只在较小的一半上递归并在较大的一半上迭代：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "algorytmy.h"

void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int part(int *tab, int left, int n) {
    int pivot = tab[left];
    int i = left;
    int j = n - 1;
    for (;;) {
        while (tab[i] < pivot)
            i++;
        while (tab[j] > pivot)
            j--;
        if (i < j) {
            swap(&tab[i], &tab[j]);
            i++;
            j--;
        } else {
            return j + 1;
        }
    }
}

void quick_sort(int *tab, int left, int n) {
    while (left + 1 < n) {
        int p = part(tab, left, n);
        if (p - left < n - p) {
            quick_sort(tab, left, p);
            left = p;
        } else {
            quick_sort(tab, p, n);
            n = p;
        }
    }
}

int check_sorted(const int *ptr, int n, const char *name) {
    for (int i = 1; i < n; i++) {
        if (ptr[i - 1] > ptr[i]) {
            printf("%s failed: ptr[%d] = %d > ptr[%d] = %d\n",
                   name, i - 1, ptr[i - 1], i, ptr[i]);
            return 1;
        }
    }
    return 0;
}

int main(int argc, char *argv[]) {
    double czas1, czas2, czas3;
    FILE *fw;

    srand(time(NULL));

    if (!(fw = fopen("danedowykresu_odwrotnie_zestaw2cd.txt", "w"))) {
        printf("Blad otwarcia zbioru\n");
        exit(2);
    }
    fprintf(fw,"Liczba danych;quicksort;shellsort;heapsort\n");
    printf("Liczba danych;quicksort;shellsort;heapsort\n");

    for (int n = 25000; n < 500000; n += 1000) {
        int *ptr = malloc(n * sizeof(*ptr));

        for (int i = 0; i < n; i++)
            ptr[i] = n - i;
        czas1 = clock();
        quick_sort(ptr, 0, n);
        czas1 = clock() - czas1;
        check_sorted(ptr, n, "check_sorted");

        for (int i = 0; i < n; i++)
            ptr[i] = n - i;
        czas2 = clock();
        shell_sort(ptr, n);
        czas2 = clock() - czas2;
        check_sorted(ptr, n, "shell_sorted");

        for (int i = 0; i < n; i++)
            ptr[i] = n - i;
        czas3 = clock();
        heap_sort(ptr, n);
        czas3 = clock() - czas3;
        check_sorted(ptr, n, "heap_sorted");

        fprintf(fw,"%d;%f;%f;%f\n",
                n, czas1 / CLOCKS_PER_SEC, czas2 / CLOCKS_PER_SEC, czas3 / CLOCKS_PER_SEC);
        printf("%d;%f;%f;%f\n",
                n, czas1 / CLOCKS_PER_SEC, czas2 / CLOCKS_PER_SEC, czas3 / CLOCKS_PER_SEC);
        free(ptr);
    }
    fclose(fw);
    return 0;
}

进程以 return 值 3221225725 退出 - quicksort worstcase with malloc crashing，如何解决？ - C

Process exited with return value 3221225725 - quicksort worstcase with malloc crashing, how to solve? – C

c

quicksort