Mercurial > public > algo-animator

comparison main.c @ 19:a027304ec75d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
implement selection sort
author Dennis C. M. <dennis@denniscm.com>
date Mon, 26 Jun 2023 17:49:41 +0100
parents 6a5c5b137348
children fc44102980fb
comparison
equal deleted inserted replaced
18:6a5c5b137348 19:a027304ec75d
23 struct Algo { 23 struct Algo {
24 char name[50]; 24 char name[50];
25 void (*function)(); 25 void (*function)();
26 }; 26 };
27 27
28 struct Algo algos[1]; 28 struct Algo algos[2];
29 29
30 int selected_algo = 0; 30 int selected_algo = 0;
31 int speed = 5; 31 int speed = 1;
32 int refresh_counter = 0; 32 int refresh_counter = 0;
33 int iter_counter = 0; 33 int iter_counter = 0;
34 int arr_size; 34 int arr_size;
35 35
36 float* arr; 36 float *arr;
37 37
38 bool run; 38 bool run;
39 39
40 40
41 /* Algorithms */ 41 /* Algorithms */
42 42
43 // Bubble sort 43 // Just some variables to store the state of the running algorithm
44 struct BubbleSortInfo { 44 struct AlgoState {
45 int step; 45 int a;
46 int i; 46 int b;
47 int c;
47 }; 48 };
48 49
49 struct BubbleSortInfo bs = {1, 0}; 50 struct AlgoState as = {0, 0, 0};
51
52
53 void swap_elements(int x, int y) {
54 float temp = arr[x];
55 arr[x] = arr[y];
56 arr[y] = temp;
57 }
58
50 59
51 void bubble_sort() { 60 void bubble_sort() {
52 if (bs.i < arr_size - bs.step - 1) { 61
53 float current = arr[bs.i]; 62 /*
54 float next = arr[bs.i + 1]; 63 * a: Index of the current selection
55 64 * b: Index boundary of the sorted array
56 if (current > next) { 65 */
57 arr[bs.i + 1] = current; 66
58 arr[bs.i] = next; 67 if (as.a < arr_size - 1 - as.b) {
59 } 68 if (arr[as.a] > arr[as.a + 1]) {
60 69 swap_elements(as.a + 1, as.a);
61 bs.i++; 70 }
71
72 as.a++;
62 } else { 73 } else {
63 bs.step++; 74 as.b++;
64 bs.i = 0; 75 as.a = 0;
76 }
77 }
78
79
80 void selection_sort() {
81
82 /*
83 * a: Index of current selection
84 * b: Index of boundary of sorted array
85 * c: Index of the minimum element
86 */
87
88
89 if (as.a < arr_size) {
90 if (arr[as.a] < arr[as.c]) {
91
92 // Save new minimum
93 as.c = as.a;
94 }
95
96 as.a++;
97 } else {
98 swap_elements(as.b, as.c);
99
100 as.b++;
101 as.a = as.b;
102 as.c = as.a;
65 } 103 }
66 } 104 }
67 105
68 106
69 /* Helper functions */ 107 /* Helper functions */
113 151
114 if (selection >= lower && selection <= upper) { 152 if (selection >= lower && selection <= upper) {
115 selected_algo = selection; 153 selected_algo = selection;
116 } 154 }
117 } 155 }
156
157
118 158
119 159
120 /* Render functions */ 160 /* Render functions */
121 161
122 void render_text(int x, int y, char* text) { 162 void render_text(int x, int y, char* text) {
267 iter_counter = 0; 307 iter_counter = 0;
268 refresh_counter = 0; 308 refresh_counter = 0;
269 run = false; 309 run = false;
270 310
271 // Reset algo steps 311 // Reset algo steps
272 bs = (struct BubbleSortInfo){0, 0}; 312 as = (struct AlgoState){0, 0};
273 } 313 }
274 314
275 // u: Increase speed 315 // u: Increase speed
276 if (key == 117) { 316 if (key == 117) {
277 speed++; 317 speed++;
278 } 318 }
279 319
280 // d: reduce speed 320 // d: reduce speed
281 if (key == 100) { 321 if (key == 100) {
282 speed--; 322 if (speed > 1) {
323 speed--;
324 }
283 } 325 }
284 326
285 // enter: Run program 327 // enter: Run program
286 if (key == 13) { 328 if (key == 13) {
287 run = true; 329 run = true;
330 }
331
332 // p: Pause program
333 if (key == 112) {
334 run = false;
288 } 335 }
289 336
290 337
291 } 338 }
292 339
351 398
352 int main(int argc, char** argv) { 399 int main(int argc, char** argv) {
353 strcpy(algos[0].name, "Bubble sort"); 400 strcpy(algos[0].name, "Bubble sort");
354 algos[0].function = &bubble_sort; 401 algos[0].function = &bubble_sort;
355 402
403 strcpy(algos[1].name, "Selection sort");
404 algos[1].function = &selection_sort;
405
356 create_array(); 406 create_array();
357 407
358 glutInit(&argc, argv); 408 glutInit(&argc, argv);
359 glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB); 409 glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB);
360 glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT); 410 glutInitWindowSize(WINDOW_WIDTH, WINDOW_HEIGHT);