Mercurial > public > algo-animator

comparison src/algorithms.c @ 38:8ed1256dd518

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
finish quick sort and add insertion sort
author Dennis C. M. <dennis@denniscm.com>
date Fri, 30 Jun 2023 19:25:38 +0100
parents 61104b22a25d
children b656ed2e8957
comparison
equal deleted inserted replaced
37:0e2121235413 38:8ed1256dd518
59 } 59 }
60 60
61 61
62 /* Quick sort */ 62 /* Quick sort */
63 63
64 int qs_partition(struct AlgoArgs *args, int left, int right) {
65 printf("Pivot index: %i\n", right);
64 66
67 args->arr[right].current = true;
68 float pivot = args->arr[right].value;
69 control_flow(args->delay / 4, args->sequentially, &args->pause);
70
71 int i = left - 1;
72
73 for (int j = left; j < right; j++) {
74 args->comparisons++;
75 args->arr[j].current = true;
76
77 control_flow(args->delay / 4, args->sequentially, &args->pause);
78
79 if (args->arr[j].value < pivot) {
80 printf("Value at index %i is smaller than pivot\n", j);
81 i++;
82 printf("Swap with value at index %i\n", i);
83
84 args->arr[i].current = true;
85 control_flow(args->delay / 4, args->sequentially, &args->pause);
86 args->arr[j].current = false;
87 args->arr[i].current = false;
88
89 struct Element temp = args->arr[i];
90 swap_elements(i, j, args->arr);
91
92 } else {
93 args->arr[j].current = false;
94 }
95 }
96
97
98 printf("Swap pivot with value at index %i\n", i + 1);
99 args->arr[i + 1].current = true;
100 control_flow(args->delay / 4, args->sequentially, &args->pause);
101 args->arr[right].current = false;
102 args->arr[i + 1].current = false;
103
104 struct Element temp = args->arr[i + 1];
105 swap_elements(i + 1, right, args->arr);
106
107 printf("Finished partition\n");
108
109 return i + 1;
110 }
111
112
113 void *quick_sort(void *arguments) {
114 struct AlgoArgs *args = (struct AlgoArgs *)arguments;
115
116 int left = 0;
117 int right = args->arr_size - 1;
118 int stack[right + 1 - left];
119 int top = -1;
120
121 stack[++top] = left;
122 stack[++top] = right;
123
124 while (top >= 0) {
125 right = stack[top--];
126 left = stack[top--];
127
128 int pivot_index = qs_partition(args, left, right);
129
130 if (pivot_index - 1 > left) {
131 stack[++top] = left;
132 stack[++top] = pivot_index - 1;
133 }
134
135 if (pivot_index + 1 < right) {
136 stack[++top] = pivot_index + 1;
137 stack[++top] = right;
138 }
139 }
140 }
141
142
143 /* Insertion sort */
144
145 void *insertion_sort(void *arguments) {
146 struct AlgoArgs *args = (struct AlgoArgs *)arguments;
147
148 for (int step = 1; step < args->arr_size; step++) {
149 struct Element key = args->arr[step];
150
151 printf("Selected key at index: %i\n", step);
152 args->arr[step].current = true;
153 control_flow(args->delay / 3, args->sequentially, &args->pause);
154
155 int i = step - 1;
156
157 while (key.value < args->arr[i].value && i >= 0) {
158 args->comparisons++;
159 printf("Key value is smaller than value at index %i\n", i);
160
161 args->arr[i].current = true;
162 args->arr[i + 1].value = 0;
163 control_flow(args->delay / 3, args->sequentially, &args->pause);
164 args->arr[i].current = false;
165
166 printf("Move foward\n");
167 args->arr[i + 1] = args->arr[i];
168
169 i--;
170 }
171
172 printf("Place key at correct position\n");
173 args->arr[i + 1] = key;
174
175 args->arr[i + 1].current = true;
176 control_flow(args->delay / 3, args->sequentially, &args->pause);
177 args->arr[i + 1].current = false;
178 args->arr[step].current = false;
179 }
180 }
181
182
183 /* Merge sort */
184
185 void *merge_sort(void *arguments) {
186 struct AlgoArgs *args = (struct AlgoArgs *)arguments;
187 }