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

Question

I made program that measure time of sorting n data arrays of int. Unfortunately my quicksort in worst case around 30000 numbers in array crashing program with return value 3221225725. For average case it works fine even for 500000 numbers (that is my max for testing).

Here is code for quicksort:

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);
    }
}

And here is code in for loop for data cases:

#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

Your implementation is incorrect: it is unclear what you are testing with if (pocz < n). A pure implementation would test if (n - left > 1). The part() function has problems too: i and j are not properly initialized. It is always a good idea to verify correctness before even trying to measure performance.

The problem with quicksort worst case is you recurse too deep and eventually encounter a stack overflow.

Here is a modified version using a simple way to prevent deep recursion: only recurse on the smaller half and iterate on the larger one:

#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;
}