Mercurial > public > algo-animator

comparison src/algorithms.c @ 49:cc6b3eeb0ad0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update algorithms.c Added merge_sort.c committer: GitHub <noreply@github.com>
author Pietro Molendys <89810437+Pedritos22@users.noreply.github.com>
date Wed, 02 Apr 2025 00:38:48 +0200
parents b656ed2e8957
children
comparison
equal deleted inserted replaced
48:10a7b0e258f4 49:cc6b3eeb0ad0
181 181
182 182
183 /* Merge sort (PENDING) */ 183 /* Merge sort (PENDING) */
184 184
185 void *merge_sort(void *arguments) { 185 void *merge_sort(void *arguments) {
186 struct AlgoArgs *args = (struct AlgoArgs *)arguments; 186 struct AlgoArgs *args = (struct AlgoArgs *)arguments;
187 } 187 int n = args->arr_size;
188 struct Element *temp = malloc(n * sizeof(struct Element));
189 if (!temp) return NULL;
190
191 for (int curr_size = 1; curr_size < n; curr_size *= 2) {
192 for (int left_start = 0; left_start < n; left_start += 2 * curr_size) {
193 int mid = left_start + curr_size - 1;
194 if (mid >= n) mid = n - 1;
195 int right_end = left_start + 2 * curr_size - 1;
196 if (right_end >= n) right_end = n - 1;
197
198 int i = left_start;
199 int j = mid + 1;
200 int k = left_start;
201
202 while (i <= mid && j <= right_end) {
203 args->comparisons++;
204 args->arr[i].current = true;
205 args->arr[j].current = true;
206
207 control_flow(args->delay, args->sequentially, &args->pause);
208
209 if (args->arr[i].value <= args->arr[j].value) {
210 temp[k++] = args->arr[i++];
211 } else {
212 temp[k++] = args->arr[j++];
213 }
214
215 args->arr[i-1].current = false;
216 args->arr[j-1].current = false;
217 }
218
219 while (i <= mid) {
220 temp[k++] = args->arr[i];
221 args->arr[i].current = true;
222 control_flow(args->delay, args->sequentially, &args->pause);
223 args->arr[i++].current = false;
224 }
225
226 while (j <= right_end) {
227 temp[k++] = args->arr[j];
228 args->arr[j].current = true;
229 control_flow(args->delay, args->sequentially, &args->pause);
230 args->arr[j++].current = false;
231 }
232
233 for (int k = left_start; k <= right_end; k++) {
234 args->arr[k] = temp[k];
235 args->arr[k].current = true;
236 control_flow(args->delay, args->sequentially, &args->pause);
237 args->arr[k].current = false;
238 }
239 }
240 }
241
242 free(temp);
243 return NULL;
244 }