I'm working on a programm that compares the runtime and steps of insertion- and countsort. Everything works except one thing, for countsort I have to initialize an extra array with malloc.
My problem is that I can't figure out how or where to free the allocated memory for my
count_array. (I'm fairly new to the C language) The malloc command is in line 47, in the "count_sort" function.
programm code:
#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[], unsigned int* befehle) {
// Muss implementiert werden
int s = 0;
*befehle = *befehle 1; //1 Befehl für Zuweisung von s
*befehle = *befehle 1; //1 Befehl für Zuweisung von i
for(int i = 0; i < len; i ){
*befehle = *befehle 1; //1 Befehl für die Überprüfung von (i < len) = true
*befehle = *befehle 1; //1 Befehl für i
s = input_array[i];
*befehle = *befehle 1; //1 Befehl für Zuweisung von s = input_array[i]
count_array[s] = count_array[s] 1;
*befehle = *befehle 1; //1 Befehl für die Rechnung count_array[s] = count_array[s] 1
}
*befehle = *befehle 1; //1 Befehl für die Überprüfung von (i < len) = false
}
void count_sort_write_output_array(int output_array[], int len, int count_array[], unsigned int* befehle) {
// Muss implementiert werden
int k = 0;
*befehle = *befehle 1; //1 Befehl für Zuweisung von k
*befehle = *befehle 1; //1 Befehl für Zuweisung von j
*befehle = *befehle 1; //1 Befehl für Zuweisung von i
for(int j = 0; j <= MAX_VALUE; j ){
*befehle = *befehle 1; //1 Befehl für die Überprüfung von (j <= MAX_VALUE) = true
*befehle = *befehle 1; //1 Befehl für j
for(int i = 0; i < count_array[j]; i ){
*befehle = *befehle 1; //1 Befehl für die Überprüfung von (i < count_array[j]) = true
*befehle = *befehle 1; //1 Befehl für i
output_array[k] = j;
*befehle = *befehle 1; //1 Befehl für Zuweisung von output_array[k] = j
k = k 1;
*befehle = *befehle 1; //1 Befehl für die Rechnung k = k 1
}
*befehle = *befehle 1; //1 Befehl für die Überprüfung von (i < count_array[j]) = false
}
*befehle = *befehle 1; //1 Befehl für die Überprüfung von (j <= MAX_VALUE) = false
}
void count_sort(int array[], int len, unsigned int* befehle) {
// Muss implementiert werden
int* count_array = malloc(sizeof(int) * MAX_VALUE);
count_sort_calculate_counts(array, len, count_array, befehle);
count_sort_write_output_array(array, len, count_array, befehle);
}
void insertion_sort(int array[], int len, unsigned int* befehle) {
// Muss implementiert werden
int key;
int i;
*befehle = *befehle 1; //1 Befehl für Zuweisung von key
*befehle = *befehle 1; //1 Befehl für Zuweisung von i
*befehle = *befehle 1; //1 Befehl für Zuweisung von j
for (int j = 1; j <len; j ){
*befehle = *befehle 1; //1 Befehl für die Überprüfung von (j <len) = true
*befehle = *befehle 1; //1 Befehl für j
i = j;
*befehle = *befehle 1; //1 Befehl für die zuweisung i = j;
key = array[j];
*befehle = *befehle 1; //1 Befehl für die zuweisung key = array[j]
i = j - 1;
*befehle = *befehle 1; //1 Befehl für die Rechnung i = j - 1
while (i >= 0 && array[i] > key){
*befehle = *befehle 2; //2 Befehle für die Bedingungen (i >= 0 = true) und (array[i] > key) = true
array[i 1] = array[i];
*befehle = *befehle 1; //1 Befehl für die zuweisung array[i 1] = array[i]
i = i - 1;
*befehle = *befehle 1; //1 Befehl für die Rechnung i = i - 1;
}
*befehle = *befehle 2; //2 Befehle für die Bedingung (i >= 0 = false) und (array[i] > key) = false
array[i 1] = key;
*befehle = *befehle 1; //1 Befehl für die zuweisung array[i 1] = key
}
*befehle = *befehle 1; //1 Befehl für die Überprüfung von (j <len) = false
}
int main(int argc, char *argv[]) {
const int WERTE[] = {10000,20000,30000,40000,50000};
const int LEN_WERTE = 5;
const int LEN_ALGORITHMEN = 2;
int rc = 0;
unsigned int 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) {
unsigned 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 sind
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 2s 2s \n", "Countsort","Insertionsort");
printf("%8s \t s s \t s s \n", "n","Befehle", "Laufzeit","Befehle","Laufzeit");
for(int j = 0; j < LEN_WERTE; j) {
printf("