I've written a C programm to compare the runtime of insertion sort and count sort, but it can't pass the valgrind test because this programm will read from non-initialized memory. Here is my code, which could probably be false, and I want to know why I have this problem:
void count_sort_write_output_array(int output_array[], int len, int count_array[], int* befehle) {
int k=0;
//use count array to output result
for (int j=0;j<=MAX_VALUE;j++) {
//add befehle
//(j++)
(*befehle)++;
for (int i=0; i<count_array[j]; i++) {
output_array[k] = j;
k++;
//add befehle
//(i++, output_array[k] = j, k++)
(*befehle)+=3;
}
}
}
void count_sort(int array[], int len, int* befehle) {
int* count_array = malloc(sizeof(int) * MAX_VALUE);
//fill count_array with 0
for(int i=0;i<MAX_VALUE;i++){
count_array[i] = 0;
}
count_sort_calculate_counts(array, len, count_array, befehle);
//use output array to save result
count_sort_write_output_array(array, len, count_array, befehle);
free(count_array);
}
and here is the result of valgrind:
==6694== Memcheck, a memory error detector
==6694== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==6694== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==6694== Command: ./aaaad
==6694==
==6694== Invalid read of size 4
==6694== at 0x4009ED: count_sort_write_output_array (in /afs/tu-berlin.de/home/r/ryoine/irb-ubuntu/introprog-wise1718/Tutorien/t24/Studierende/ryoine/Abgaben/Blatt03/aaaad)
==6694== by 0x400A8D: count_sort (in /afs/tu-berlin.de/home/r/ryoine/irb-ubuntu/introprog-wise1718/Tutorien/t24/Studierende/ryoine/Abgaben/Blatt03/aaaad)
==6694== by 0x400FD5: main (in /afs/tu-berlin.de/home/r/ryoine/irb-ubuntu/introprog-wise1718/Tutorien/t24/Studierende/ryoine/Abgaben/Blatt03/aaaad)
==6694== Address 0x6916d40 is 0 bytes after a block of size 20,000,000 alloc'd
==6694== at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==6694== by 0x400A2A: count_sort (in /afs/tu-berlin.de/home/r/ryoine/irb-ubuntu/introprog-wise1718/Tutorien/t24/Studierende/ryoine/Abgaben/Blatt03/aaaad)
==6694== by 0x400FD5: main (in /afs/tu-berlin.de/home/r/ryoine/irb-ubuntu/introprog-wise1718/Tutorien/t24/Studierende/ryoine/Abgaben/Blatt03/aaaad)
==6694==
Parameter MAX_VALUE hat den Wert 5000000
Countsort Insertionsort
n Befehle Laufzeit Befehle Laufzeit
10000 5050001 425.5080 50215642 1929.5740
20000 5100001 423.1040 200387176 7655.5280
30000 5150001 427.7080 453403054 16763.7200
40000 5200001 363.3830 797737482 28034.7020
50000 5250001 392.9350 1245274822 44438.0240
==6694==
==6694== HEAP SUMMARY:
==6694== in use at exit: 0 bytes in 0 blocks
==6694== total heap usage: 26 allocs, 26 frees, 101,224,264 bytes allocated
==6694==
==6694== All heap blocks were freed -- no leaks are possible
==6694==
==6694== For counts of detected and suppressed errors, rerun with: -v
==6694== ERROR SUMMARY: 5 errors from 1 contexts (suppressed: 0 from 0)
Here's your problem:
for (int j=0;j<=MAX_VALUE;j++) {
You allocate space for an array of MAX_VALUE int's. So the indexes of this array range from 0 to MAX_VALUE - 1. Your loop however allows j to range up to MAX_VALUE, so when that happens count_array[j] is reading one element past the end of the array.
Fix your loop condition to not include MAX_VALUE:
for (int j=0;j<MAX_VALUE;j++) {