This is my code (sorry, it's long, but there is a lot of repeating code).
{Description} Sorting algortihm testing program using pseudo randomly generated number array. User can specify array length, its min and max elements, the least number of repeating values. User can also choose how many arrays to be tested.
1 /*=============================================================================
2 |
3 | Assignment: Program 12
4 |
8 | Class: Programming Basics
9 | Date: December 13th, 2017
10 |
11 | Language: GNU C (using gcc on Lenovo Y50-70, OS: Arch Linux x86_64)
12 | Version: 0.0
13 | To Compile: gcc -Wall -g -std=c11 pratybos12.c -o pratybos12
14 |
15 +-----------------------------------------------------------------------------
16 |
17 | Description: Sorting algortihm testing program using pseudo randomly
18 | generated number array. User can specify array length,
19 | its min and max elements, the least number of repeating
20 | values. User can also choose how many arrays to be tested.
21 |
22 | Input: Command line input by user
23 |
24 | Output: Prompt messages, validation errors and final results
25 | are displayed one per line to the standard output.
26 | The output is each algorithm's each iteration, with
27 | comparison and assignment counts, and also processor
28 | clock times and average completion time, in seconds.
29 | Finally, the average data of each algorithm is presented.
30 | At the end, the algorithms are sorted from best to worst
31 | by their average time.
32 |
33 | Version
34 | updates: Currently this is the intial version
35 |
36 +===========================================================================*/
37
38 #include <stdio.h>
39 #include <stdlib.h>
40 #include <time.h>
41
42 #include "dbg.h"
43
44 #include "helpers.h"
45 #include "test_algorithm.h"
46
47 #include "bubble_sort_a.h"
48 #include "bubble_sort_b.h"
49 #include "bubble_sort_c.h"
50 #include "bubble_sort_d.h"
51 #include "bubble_sort_e.h"
52 #include "bubble_sort_e_and_f.h"
53 #include "bubble_sort_f.h"
54 #include "bubble_sort_b_and_c.h"
55 #include "bubble_sort_b_and_e.h"
56 #include "bubble_sort_b_and_f.h"
57 #include "bubble_sort_c_and_e.h"
58 #include "bubble_sort_c_and_f.h"
59 #include "bubble_sort_b_and_e_and_f.h"
60 #include "bubble_sort_b_and_c_and_e_and_f.h"
61 #include "insertion_sort.h"
62 #include "quicksort_pivot_first.h"
63 #include "selection_sort.h"
64 #include "top_down_merge_sort.h"
65
66 #define MAX_ITER 100
67 #define MAX_ALGO 100
68
69
70 typedef struct {
71 char* pointerName;
72 int pointerMemory;
73 } PointerStats;
74
75 typedef struct {
76 PointerStats* memJournal;
77 int JournalPointerCount;
78 int memUsed;
79 int memUsedByJournal;
80 } MemoryStats;
81
82
83 typedef struct {
84 int no;
85 int is_sorted;
86 int comp_count;
87 int assign_count;
88 double clocks_total;
89 double time_spent;
90 } Iteration;
91
92 typedef struct {
93 char* type;
94 char* complexity;
95 int iter_count;
96 int rank;
97 int avg_comp;
98 int avg_assign;
99 double avg_clocks;
100 double avg_time;
101 Iteration* iterations[MAX_ITER];
102 } Algorithm;
103
104 typedef struct {
105 char* date;
106 char* arch;
107 char* compiler;
108 Algorithm* algorithms[MAX_ALGO];
109 } Results;
110
111 // a typedef creates a fake type, in this
112 // case for a sort function pointer
113 typedef int* (*sort_pointer)(int* target, int size);
114
115 // function pointer to a quicksort function
116 typedef int* (*quicksort_pointer)(int* target, int first, int last);
117
118 // function pointer to a mergesort function
119 typedef void (*mergesort_pointer)(int* target, int* working_array, int size);
120
121
122 void filldata(int* data, int size, int min, int max, int repeat);
123 void test_sort( int* data, int size, sort_pointer func, Algorithm* Algo, int no);
124 void test_quicksort( int* data, int size, quicksort_pointer func, Algorithm* Algo, int no);
125 void test_mergesort( int* data, int size, mergesort_pointer func, Algorithm* Algo, int no);
126 void print_algo(Algorithm* Algo);
127 void calculate_average(Algorithm* Algo);
128 Algorithm** rank_algorithms(Algorithm** target, int first, int last);
129
130 MemoryStats memoryStats;
131
132 int array_count;
133
134 int main(int argc, char* argv[])
135 {
136 srand(time(NULL));
137
138 Results* Res = malloc(sizeof(Results));
139
140 Res->date = "2017-12-16";
141 Res->arch = "Arch Linux x86_64";
142 Res->compiler = "gcc";
143
144 // creating algorithm structures
145 Algorithm* Algo1 = malloc(sizeof(Algorithm));
146 Algo1->type = "bubble_sort_a";
147 Algo1->complexity = "O (n^2)";
148
149 Algorithm* Algo2 = malloc(sizeof(Algorithm));
150 Algo2->type = "bubble_sort_b";
151 Algo2->complexity = "O (n^2)";
152
153 Algorithm* Algo3 = malloc(sizeof(Algorithm));
154 Algo3->type = "bubble_sort_c";
155 Algo3->complexity = "O (n^2)";
156
157 Algorithm* Algo4 = malloc(sizeof(Algorithm));
158 Algo4->type = "bubble_sort_d";
159 Algo4->complexity = "O (n^2)";
160
161 Algorithm* Algo5 = malloc(sizeof(Algorithm));
162 Algo5->type = "bubble_sort_e";
163 Algo5->complexity = "O (n^2)";
164
165 Algorithm* Algo6 = malloc(sizeof(Algorithm));
166 Algo6->type = "bubble_sort_f";
167 Algo6->complexity = "O (n^2)";
168
169 Algorithm* Algo7 = malloc(sizeof(Algorithm));
170 Algo7->type = "bubble_sort_b_and_c";
171 Algo7->complexity = "O (n^2)";
172
173 Algorithm* Algo8 = malloc(sizeof(Algorithm));
174 Algo8->type = "bubble_sort_b_and_e";
175 Algo8->complexity = "O (n^2)";
176
177 Algorithm* Algo9 = malloc(sizeof(Algorithm));
178 Algo9->type = "bubble_sort_b_and_f";
179 Algo9->complexity = "O (n^2)";
180
181 Algorithm* Algo10 = malloc(sizeof(Algorithm));
182 Algo10->type = "bubble_sort_c_and_e";
183 Algo10->complexity = "O (n^2)";
184
185 Algorithm* Algo11 = malloc(sizeof(Algorithm));
186 Algo11->type = "bubble_sort_c_and_f";
187 Algo11->complexity = "O (n^2)";
188
189 Algorithm* Algo12 = malloc(sizeof(Algorithm));
190 Algo12->type = "bubble_sort_e_and_f";
191 Algo12->complexity = "O (n^2)";
192
193 Algorithm* Algo13 = malloc(sizeof(Algorithm));
194 Algo13->type = "bubble_sort_b_and_e_and_f";
195 Algo13->complexity = "O (n^2)";
196
197 Algorithm* Algo14 = malloc(sizeof(Algorithm));
198 Algo14->type = "bubble_sort_b_and_c_and_e_and_f";
199 Algo14->complexity = "O (n^2)";
200
201 Algorithm* Algo15 = malloc(sizeof(Algorithm));
202 Algo15->type = "quicksort";
203 Algo15->complexity = "O (n logn n)";
204
205 Algorithm* Algo16 = malloc(sizeof(Algorithm));
206 Algo16->type = "insertion_sort";
207 Algo16->complexity = "O (2n)";
208
209 Algorithm* Algo17 = malloc(sizeof(Algorithm));
210 Algo17->type = "selection_sort";
211 Algo17->complexity = "O (2n)";
212
213 Algorithm* Algo18 = malloc(sizeof(Algorithm));
214 Algo18->type = "top down merge sort";
215 Algo18->complexity = "O (n log n)";
216
217 Res->algorithms[0] = Algo1;
218 Res->algorithms[1] = Algo2;
219 Res->algorithms[2] = Algo3;
220 Res->algorithms[3] = Algo4;
221 Res->algorithms[4] = Algo5;
222 Res->algorithms[5] = Algo6;
223 Res->algorithms[6] = Algo7;
224 Res->algorithms[7] = Algo8;
225 Res->algorithms[8] = Algo9;
226 Res->algorithms[9] = Algo10;
227 Res->algorithms[10] = Algo11;
228 Res->algorithms[11] = Algo12;
229 Res->algorithms[12] = Algo13;
230 Res->algorithms[13] = Algo14;
231 Res->algorithms[14] = Algo15;
232 Res->algorithms[15] = Algo16;
233 Res->algorithms[16] = Algo17;
234 Res->algorithms[17] = Algo18;
235
236 memoryStats.memJournal = malloc(10 * sizeof(int));
237
238 memoryStats.memUsedByJournal = 10;
239
240 memoryStats.JournalPointerCount = 0;
241
242 printf("Mem used total: %d\n", memoryStats.memUsed);
243
244 int size;
245 int min;
246 int max;
247 int repeat;
248
249 array_count = get_pos_num("How many arrays would you like to test? > ", 0);
250 size = get_pos_num("What is the size of each array? > ", 0);
251 min = get_pos_num("What is the minimum number in each array? > ", 0);
252 max = get_pos_num("What is the maximum number in each array? > ", 0);
253
254 while (1) {
255 printf("How many repeating values there will be AT LEAST? > ");
256 if (scanf("%d", &repeat) == 1 && repeat >= 0
257 && repeat <= (max - min + 1) && getchar() == '\n') {
258 break;
259 } else {
260 while (getchar() != '\n')
261 ;
262 printf("Please enter a positive integer or zero, which is not "
263 "greater than the "
264 "size of the array\n");
265 }
266 }
267
268 for (int i = 0; i < array_count; i++) {
269 int* data = malloc(size * sizeof(int));
270
271 filldata(data, size, min, max, repeat);
272 if (data == NULL)
273 die("Atminties problema");
274
275 printf("i: %d", i);
276 print_array(data, size, "Your generated numbers:");
277 //---------------------------USING FUNCTION POINTERS-----------------//
278
279 test_sort(data, size, &bubble_sort_a, Algo1, i + 1);
280 test_sort(data, size, &bubble_sort_b, Algo2, i + 1);
281 test_sort(data, size, &bubble_sort_c, Algo3, i + 1);
282 test_sort(data, size, &bubble_sort_d, Algo4, i + 1);
283 test_sort(data, size, &bubble_sort_e, Algo5, i + 1);
284 test_sort(data, size, &bubble_sort_f, Algo6, i + 1);
285 test_sort(data, size, &bubble_sort_b_and_c, Algo7, i + 1);
286 test_sort(data, size, &bubble_sort_b_and_e, Algo8, i + 1);
287 test_sort(data, size, &bubble_sort_b_and_f, Algo9, i + 1);
288 test_sort(data, size, &bubble_sort_c_and_e, Algo10, i + 1);
289 test_sort(data, size, &bubble_sort_c_and_f, Algo11, i + 1);
290 test_sort(data, size, &bubble_sort_e_and_f, Algo12, i + 1);
291 test_sort(data, size, &bubble_sort_b_and_e_and_f, Algo13, i + 1);
292 test_sort(data, size, &bubble_sort_b_and_c_and_e_and_f, Algo14, i + 1);
293
294 test_sort(data, size, &bubble_sort_c_and_f, Algo15, i + 1);
295 test_sort(data, size, &bubble_sort_e_and_f, Algo16, i + 1);
296 test_sort(data, size, &bubble_sort_b_and_e_and_f, Algo17, i + 1);
297 test_sort(data, size, &bubble_sort_b_and_c_and_e_and_f, Algo18, i + 1);
298
299
300 free(data);
301 }
302
303 calculate_average(Algo1);
304 calculate_average(Algo2);
305 calculate_average(Algo3);
306 calculate_average(Algo4);
307 calculate_average(Algo5);
308 calculate_average(Algo6);
309 calculate_average(Algo7);
310 calculate_average(Algo8);
311 calculate_average(Algo9);
312 calculate_average(Algo10);
313 calculate_average(Algo11);
314 calculate_average(Algo12);
315 calculate_average(Algo13);
316 calculate_average(Algo14);
317 calculate_average(Algo15);
318 calculate_average(Algo16);
319 calculate_average(Algo17);
320 calculate_average(Algo18);
321
322
323 for (int i = 0; i < 18; i++) {
324 print_algo(Res->algorithms[i]);
325 }
326
327
328 Algorithm** target = malloc(18 * sizeof(Algorithm));
329
330 target[0] = Algo1;
331 target[1] = Algo2;
332 target[2] = Algo3;
333 target[3] = Algo4;
334 target[4] = Algo5;
335 target[5] = Algo6;
336 target[6] = Algo7;
337 target[7] = Algo8;
338 target[8] = Algo9;
339 target[9] = Algo10;
340 target[10] = Algo11;
341 target[11] = Algo12;
342 target[12] = Algo13;
343 target[13] = Algo14;
344 target[14] = Algo15;
345 target[15] = Algo16;
346 target[16] = Algo17;
347 target[17] = Algo18;
348
349 target = rank_algorithms(target, 0, 17);
350
351 printf("Fastest algorithms (ranking):\n");
352 printf("=============================\n");
353
354 for (int i = 0; i < 18; i++) {
355 printf("%d. ", i + 1);
356 printf("%s\n", target[i]->type);
357 printf("Average time: %f\n", target[i]->avg_time);
358 printf("---------------------------------\n");
359 }
360
361 printf("================================\n");
362 printf("Date: %s\n", Res->date);
363 printf("Architecture: %s\n", Res->arch);
364 printf("Compiler: %s\n", Res->compiler);
365 printf("================================\n");
366
367 printf("Mem used total: %d\n", memoryStats.memUsed);
368
369
370 free(Res);
371
372
373 for (int i = 0; i < array_count; i++) {
374 free(Algo1->iterations[i]);
375 }
376 free(Algo1);
377
378 for (int i = 0; i < array_count; i++) {
379 free(Algo2->iterations[i]);
380 }
381 free(Algo2);
382
383 for (int i = 0; i < array_count; i++) {
384 free(Algo3->iterations[i]);
385 }
386 free(Algo3);
387
388 for (int i = 0; i < array_count; i++) {
389 free(Algo4->iterations[i]);
390 }
391 free(Algo4);
392
393 for (int i = 0; i < array_count; i++) {
394 free(Algo5->iterations[i]);
395 }
396 free(Algo5);
397
398 for (int i = 0; i < array_count; i++) {
399 free(Algo6->iterations[i]);
400 }
401 free(Algo6);
402
403 for (int i = 0; i < array_count; i++) {
404 free(Algo7->iterations[i]);
405 }
406 free(Algo7);
407
408 for (int i = 0; i < array_count; i++) {
409 free(Algo8->iterations[i]);
410 }
411 free(Algo8);
412
413 for (int i = 0; i < array_count; i++) {
414 free(Algo9->iterations[i]);
415 }
416 free(Algo9);
417
418 for (int i = 0; i < array_count; i++) {
419 free(Algo10->iterations[i]);
420 }
421 free(Algo10);
422
423 for (int i = 0; i < array_count; i++) {
424 free(Algo11->iterations[i]);
425 }
426 free(Algo11);
427
428 for (int i = 0; i < array_count; i++) {
429 free(Algo12->iterations[i]);
430 }
431 free(Algo12);
432
433 for (int i = 0; i < array_count; i++) {
434 free(Algo13->iterations[i]);
435 }
436 free(Algo13);
437
438 for (int i = 0; i < array_count; i++) {
439 free(Algo14->iterations[i]);
440 }
441 free(Algo14);
442
443 for (int i = 0; i < array_count; i++) {
444 free(Algo15->iterations[i]);
445 }
446 free(Algo15);
447
448 for (int i = 0; i < array_count; i++) {
449 free(Algo16->iterations[i]);
450 }
451 free(Algo16);
452
453 for (int i = 0; i < array_count; i++) {
454 free(Algo17->iterations[i]);
455 }
456 free(Algo17);
457
458 for (int i = 0; i < array_count; i++) {
459 free(Algo18->iterations[i]);
460 }
461 free(Algo18);
462
463 free(target);
464 free(memoryStats.memJournal);
465 }
466
467
468 void filldata(int* data, int size, int min, int max, int repeat)
469 {
470 int i;
471
472 for (i = 0; i < size; i++) {
473 data[i] = min + rand() % (max - min + 1);
474 }
475
476 if (repeat > 1) {
477 int repeat_value = min + rand() % (max - min + 1);
478
479 int indexes[repeat];
480
481 int x;
482
483 // Non-duplicate number generation
484
485 i = 0;
486 while (i < repeat) {
487 int index = rand() % size;
488
489 for (x = 0; x < i; x++) {
490 if (indexes[x] == index) {
491 break;
492 }
493 }
494 if (x == i) {
495 indexes[i++] = index;
496 }
497 }
498
499 for (i = 0; i < repeat; i++) {
500 data[indexes[i]] = repeat_value;
501 }
502 }
503 }
504
505
506 void test_sort(int* data, int size, sort_pointer func, Algorithm* Algo, int no)
507 {
508
509 count_ncomp = 0;
510 count_assign = 0;
511
512 begin = clock();
513
514 int* target = NULL;
515 target = malloc(size * sizeof(int));
516 if (!target)
517 die("Memory error.");
518
519 memcpy(target, data, size * sizeof(int));
520
521 Iteration* Iter = malloc(sizeof(Iteration));
522 if (Iter == NULL) {
523 exit(1);
524 }
525 Iter->no = no;
526
527 if (is_sorted(func(target, size), size)) {
528 end = clock();
529 clocks = (double)(end - begin);
530 time_spent = clocks / CLOCKS_PER_SEC;
531
532 Iter->is_sorted = 1;
533 Iter->comp_count = count_ncomp;
534 Iter->assign_count = count_assign;
535 Iter->clocks_total = clocks;
536 Iter->time_spent = time_spent;
537 } else {
538 Iter->is_sorted = 0;
539
540 };
541
542 Algo->iterations[no - 1] = Iter;
543
544 if (target == NULL) {
545 debug("Target is NULL");
546 }
547
548 free(target);
549 }
550
551
552 void print_algo(Algorithm* Algo)
553 {
554
555 printf("Algorithm type: %s\n", Algo->type);
556 printf("Time complexity: %s\n", Algo->complexity);
557 printf("----------------------------------\n");
558 for (int i = 0; i < array_count; i++) {
559 if (!Algo->iterations[i]->is_sorted) {
560 printf("Not sorted");
561 } else {
562 printf("no: %d\n", Algo->iterations[i]->no);
563 printf("is_sorted: True\n");
564 printf("comp_count: %d\n", Algo->iterations[i]->comp_count);
565 printf("assign count: %d\n", Algo->iterations[i]->assign_count);
566 printf("clocks total: %f\n", Algo->iterations[i]->clocks_total);
567 printf("time spent: %f\n", Algo->iterations[i]->time_spent);
568 }
569 printf("----------------------------------\n");
570 }
571 printf("Iteration count: %d\n", Algo->iter_count);
572 printf("Average compare count: %d\n", Algo->avg_comp);
573 printf("Average assign count: %d\n", Algo->avg_assign);
574 printf("Average clocks: %f\n", Algo->avg_clocks);
575 printf("Average time spent: %f\n", Algo->avg_time);
576
577 printf("===================================\n");
578 }
579
580 void calculate_average(Algorithm* Algo)
581 {
582 int sum_comp = 0;
583 int sum_assign = 0;
584 double sum_clocks = 0;
585 double sum_time = 0;
586 int sorted_count = array_count;
587
588 for (int i = 0; i < array_count; i++) {
589
590 debug("is sorted %d", Algo->iterations[i]->is_sorted);
591 debug("Array count: %d", i);
592
593 if (!Algo->iterations[i]->is_sorted) {
594 sorted_count--;
595 } else {
596 sum_comp += Algo->iterations[i]->comp_count;
597 sum_assign += Algo->iterations[i]->assign_count;
598 sum_clocks += Algo->iterations[i]->clocks_total;
599 sum_time += Algo->iterations[i]->time_spent;
600 }
601 }
602 if (sorted_count > 0) {
603 Algo->avg_comp = sum_comp / sorted_count;
604 Algo->avg_assign = sum_assign / sorted_count;
605 Algo->avg_clocks = (double)(sum_clocks / sorted_count);
606 Algo->avg_time = (double)(sum_time / sorted_count);
607 Algo->iter_count = sorted_count;
608 }
609 }
610
611 Algorithm** rank_algorithms(Algorithm** target, int first, int last)
612 {
613
614 Algorithm* temp;
615 int pivot, j, i;
616
617 if (first < last) {
618 pivot = first;
619 i = first;
620 j = last;
621
622 while (i < j) {
623 while (
624 target[i]->avg_time <= target[pivot]->avg_time && i < last) {
625 i++;
626 }
627 while (target[j]->avg_time > target[pivot]->avg_time) {
628 j--;
629 }
630 if (i < j) {
631 temp = target[i];
632 target[i] = target[j];
633 target[j] = temp;
634 }
635 }
636
637 temp = target[pivot];
638 target[pivot] = target[j];
639 target[j] = temp;
640
641 rank_algorithms(target, first, j - 1);
642 rank_algorithms(target, j + 1, last);
643 }
644 return target;
645 }
646
What I can successfully do (running a program):
How many arrays would you like to test? > 100
What is the size of each array? > 10
What is the minimum number in each array? > 1
What is the maximum number in each array? > 10
How many repeating values there will be AT LEAST? > 0
What I can't do:
How many arrays would you like to test? > 1000
What is the size of each array? > 10
What is the minimum number in each array? > 1
What is the maximum number in each array? > 10
How many repeating values there will be AT LEAST? > 0
The problem is when there are 1000 arrays to be tested (instead of 100). This is the same error I get:
DEBUG pratybos12.c:590: is sorted 1
DEBUG pratybos12.c:591: Array count: 919
==5798== Invalid read of size 4
==5798== at 0x10A646: calculate_average (pratybos12.c:590)
==5798== by 0x1096F5: main (pratybos12.c:313)
==5798== Address 0x2d2d2d2d2d2d2d31 is not stack'd, malloc'd or (recently) free'd
==5798==
==5798==
==5798== Process terminating with default action of signal 11 (SIGSEGV): dumping core
==5798== General Protection Fault
==5798== at 0x10A646: calculate_average (pratybos12.c:590)
==5798== by 0x1096F5: main (pratybos12.c:313)
The question is, how to even start debugging it, ie where the problem might be.
A few notes: (1) When I run it with 100 arrays (first case), Valgrind reports that all memory is successfully freed, no leaks occur.
(2) I had a "double free or corruption error" in line 300:
300 free(data);
but I turned it off by setting MALLOC_CHECK_ to 0.
The size of Algorithm.iterations is MAX_ITER which is 100. And then you access Algorithm.iterations elements up to 1000th. This is undefined behavior.
Algorithm** target = malloc(18 * sizeof(Algorithm)); is wrong for sure. The type of target should be Algorithm *.