csortingclocktimingtime.h

Program to time sort algorithms keeps crashing


I have some code that was meant to time sort algorithms (for school) but it keeps crashing whenever array size is bigger than just 20k.

This is the main file I have:

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

#include "sorting.h"

#define ARG_COUNT 1

int main(int argc, char *argv[]) {
    
    if (argc != ARG_COUNT + 1) {
        printf("Too few or too many arguments passed.\n");
        exit(1);
    }

    if (atoi(argv[1]) < 10000) {
        printf("Array lenght should be at least 10 000.");
        exit(2);
    }

    int arr_lenght = atoi(argv[1]);
    srand(time(0));

    int *arr1 = (int *)calloc(arr_lenght, arr_lenght * sizeof(int));
    for (int i = 0; i < arr_lenght; i++) {
        arr1[i] = rand() % 20;
    }

    int *arr2 = (int *)calloc(arr_lenght, arr_lenght * sizeof(int));
    for (int i = 0; i < arr_lenght; i++) {
        arr2[i] = rand() % 20;
    }

    //INSERTION SORT TIMER
    int ticks_start = clock();
    insertion_sort(arr1, arr_lenght);
    int ticks_finish = clock();

    float net_ticks = ticks_finish - ticks_start;
    printf("insertion sort time:");
    printf("%fl\n", (double)net_ticks / CLOCKS_PER_SEC);
    
    //MERGE SORT TIMER
    ticks_start = clock();
    merge_sort(arr2, 0, arr_lenght - 1);
    ticks_finish = clock();

    net_ticks = ticks_finish - ticks_start;
    printf("merge sort time:");
    printf("%fl\n", (double)net_ticks / CLOCKS_PER_SEC);

    //free
    free(arr1);
    free(arr2);

    return 0;
}

The main function is meant to accept the array size as a command line argument and fill 2 arrays of that size with pseudo random values, then sort one with merge sort and one with insertion sort and compare the times.


Solution

  • You are allocating an excess of memory.

    calloc(length, length * sizeof (int)) allocates length * length * sizeof (int) bytes. You are likely confusing this with the typical malloc pattern of malloc(length * sizeof (int)).

    Assuming a 4-byte int and a length of 20000, each allocation takes 1.6GB of memory.

    In the event that calloc fails to allocate memory, it will return NULL. Some implementations (e.g., POSIX) will set errno to ENOMEM when this happens.

    You should always test the return value of library functions that can fail.

    int *arr1 = calloc(length, sizeof *arr1);
    
    if (!arr1) {
        perror("calloc");
        exit(EXIT_FAILURE);
    }