时间戳

首页 > 解决方案 > 进程退出并返回值 3221225725 - 快速排序最坏情况，malloc 崩溃，如何解决？- C

c - 进程退出并返回值 3221225725 - 快速排序最坏情况，malloc 崩溃，如何解决？- C

问题描述

我制作了一个程序来测量排序的 n 个数据数组的时间int。不幸的是，在最坏的情况下，我的快速排序在数组崩溃程序中大约 30000 个数字，返回值为 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;
}

控制台屏幕

标签： cquicksort

解决方案

您的实现不正确：目前尚不清楚您使用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;
}

推荐阅读