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 %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("%16u %16.4f \t ", befehle_array[i][j], laufzeit_array[i][j]);
}
printf("\n");
}
return rc;
}
I have tried to free the memory of the count array at several points of the programm. Compiling works but if I run the programm it spits out a segmentation fault.
Also I have tried to not use the malloc command and just use
int count_array[MAX_VALUE];
which also gives a segmentation fault.
count_array[MAX_VALUE], whereas the last element legally accessable is MAX_VALUE-1.fill_array_randomly function only fills non-negative integers to the array, cause in the function count_sort_calculate_counts, in the statement count_array[s] = count_array[s] + 1;, you are accessing input_array[i]th element of count_array, and if input_array[i] is negative, then it may issue this error.