Btukfyl

I have the task to count the steps of count sort and insertion sort. I implemented the counting variable as z and it is stored in the *befehle pointer.

My problem is, that I just can't figure out how to call the functions properly. And the program always tells me, that the result of count sort and insertion sort is different.

The output is a chart with how many steps it took for each n and how long it took.

I don't quite know how much you need to see to help me, so I just post the complete code.

It is mainly the void count_sort function that troubles me.

#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 %dn", 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;

}