Сложность выполнения в C

Question

У меня есть задача подсчитать шаги сортировки и сортировки.Я реализовал переменную подсчета как z, и она хранится в указателе * befehle.

Моя проблема в том, что я просто не могу понять, как правильно вызывать функции.И программа всегда говорит мне, что результат сортировки счетчиков и сортировки вставок различен.

Выходные данные представляют собой диаграмму с указанием количества шагов, которые потребовались для каждого n и сколько времени на это ушло.

Я не совсем понимаю, сколько вам нужно увидеть, чтобы помочь мне, поэтому я просто публикую полный код.

Меня беспокоит в основном функция void count_sort.

#include <stdio.h>
#include <stdlib.h>
#include "introprog_complexity_steps_input.h"

const int MAX_VALUE = 5000000;

void count_sort_calculate_counts(int input_array[], int len, int count_array[], int* befehle) {
       //muss implementiert werden
                                            int z = 0;
                                            z=z+1; //für x
                                            z=z+1; //für j

    for (int x=0;x<=MAX_VALUE;x++){
        count_array[x] = 0;
                                            z=z+1; //Vergleich d. Schleife
                                            z=z+1; //Inkrementierung der Schleife

    }

    for (int j = 0; j<len; j++){
                                            z=z+1; // Vergleich
                                            z=z+1; // Inkrementierung d. Schleife
        count_array[input_array[j]]++;
                                            z=z+1; //Inkrementierung
    }
                                            *befehle = z;
}

void count_sort_write_output_array(int output_array[], int len, int count_array[], int* befehle) {
    //muss implementiert werden
                                            int z = 0;
                                            z=z+1; //Allozierung v. Speicher in Count_Sort
                                            z=z+1; //Für k
                                            z=z+1; //Zuweisung v. j
                                            z=z+1; //Zuweisung v. i

    int k = 0;
    for (int j = 0;j <=len;j++){
                                            z=z+1; //Vergleich d. Schleife
                                            z=z+1; //Inkrementierung d. Schleife
        for(int i = 0; i<count_array[j]; i++){
                                            z=z+1; // Vergleich d. Schleife
                                            z=z+1; //Inkrementierung d. Schleife

            output_array[k] = j;

                                            z=z+1; // Zuweisung
                                            z=z+1; // Inkrementierung v. k

            k=k+1;
        }
    }
                                            *befehle=z;
}


void count_sort(int array[], int len, int* befehle) {

    int* count_array = malloc(sizeof(int) * MAX_VALUE);

    int input_array[len];
    int output_array[len];



    count_sort_calculate_counts(input_array, len, count_array, befehle);
    count_sort_write_output_array(output_array, len, count_array, befehle);
    free(count_array);
}


void insertion_sort(int array[], int len, int* befehle) {
    //muss implementiert werden
    int z=0;
    int j, i, key;
                                            z=z+1; // j Zuweisung
    for (j=1; j<len; j++) {
                                            z=z+1; // Vergleich
                                            z=z+1; // Inkrementierung v. j
        key = array[j];
                                            z=z+1; // Zuweisung
        i=j-1;
                                            z=z+1; //Inkrementierung

        while (i>=0 && array[i] > key) {
                                            z=z+1; //Vergleich 1
                                            //z=z+1; //Vergleich 2
            array[i+1] = array[i];
                                            z=z+1; //Zuweisung
            i = i-1;
                                            z=z+1; //Inkrementierung
        }
        array[i+1] = key;
                                            z=z+1; //Zuweisung
    }
                                            *befehle=z;
}


int main(int argc, char *argv[]) {

    const int WERTE[] = {1000,2000,3000,4000,5000};
    const int LEN_WERTE = 5;
    const int LEN_ALGORITHMEN = 2;

    int rc = 0;
    long befehle_array[LEN_ALGORITHMEN][LEN_WERTE];
    double laufzeit_array[LEN_ALGORITHMEN][LEN_WERTE];

    for(int j = 0; j < LEN_WERTE; ++j)
    {
        int n = WERTE[j];

        //reserviere Speicher für  Arrays der Länge n
        int* array_countsort = malloc(sizeof(int) * n);
        int* array_insertionsort = malloc(sizeof(int) * n);

        //fülle array_countsort mit Zufallswerten ..
        fill_array_randomly(array_countsort, n, MAX_VALUE);
        //.. und kopiere die erzeugten Werte in das Array array_insertionsort
        copy_array_elements(array_insertionsort, array_countsort, n);

        //teste ob beide Arrays auch wirklich die gleichen Werte enthalten
        if(!check_equality_of_arrays(array_countsort, array_insertionsort, n))
        {
            printf("Die Eingaben für beide Algorithmen müssen für die Vergleichbarkeit gleich sein!\n");
            return -1;
        }

        for(int i = 0; i < LEN_ALGORITHMEN; ++i)
        {
            int anzahl_befehle = 0;

            start_timer();

            //Aufruf der entsprechenden Sortieralgorithmen
            if(i==0)
            {
                    count_sort(array_countsort, n, &anzahl_befehle);
            }
            else if(i==1)
            {
                    insertion_sort(array_insertionsort, n, &anzahl_befehle);
            }

            //speichere die Laufzeit sowie die Anzahl benötigter Befehle
            laufzeit_array[i][j] = end_timer();
            befehle_array[i][j] = anzahl_befehle;
        }

        //teste ob die Ausgabe beider Algorithmen gleich ist
        if(!check_equality_of_arrays(array_countsort, array_insertionsort, n))
        {
            printf("Die Arrays sind nicht gleich. Eines muss (falsch) sortiert worden sein!\n");
            rc = -1;
        }

        //gib den Speicherplatz wieder frei
        free(array_countsort);
        free(array_insertionsort);
    }

    //Ausgabe der Anzahl ausgeführter Befehle sowie der gemessenen Laufzeiten (in Millisekunden)
    printf("Parameter MAX_VALUE hat den Wert %d\n", MAX_VALUE);
    printf("\t %32s           %32s \n", "Countsort","Insertionsort");
    printf("%8s \t %16s %16s \t %16s %16s \n", "n","Befehle", "Laufzeit","Befehle","Laufzeit");

    for(int j = 0; j < LEN_WERTE; ++j)
    {
        printf("%8d \t ",WERTE[j]);
        for(int i = 0; i < LEN_ALGORITHMEN; ++i)
        {
            printf("%16ld %16.4f \t ",  befehle_array[i][j], laufzeit_array[i][j]);
        }
        printf("\n");
    }

    return rc;
}