Mercurial > public > algo-animator

annotate 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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
29
dae463bbf5ca implementing multi-thread and refactoring
Dennis C. M. <dennis@denniscm.com>
parents:
diff changeset
1 #include "algorithms.h"
dae463bbf5ca implementing multi-thread and refactoring
Dennis C. M. <dennis@denniscm.com>
parents:
diff changeset
2
dae463bbf5ca implementing multi-thread and refactoring
Dennis C. M. <dennis@denniscm.com>
parents:
diff changeset
3
30
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
4 /* Bubble sort */
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
5
29
dae463bbf5ca implementing multi-thread and refactoring
Dennis C. M. <dennis@denniscm.com>
parents:
diff changeset
6 void *bubble_sort(void *arguments) {
dae463bbf5ca implementing multi-thread and refactoring
Dennis C. M. <dennis@denniscm.com>
parents:
diff changeset
7 struct AlgoArgs *args = (struct AlgoArgs *)arguments;
dae463bbf5ca implementing multi-thread and refactoring
Dennis C. M. <dennis@denniscm.com>
parents:
diff changeset
8
30
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
9 for (int step = 0; step < args->arr_size - 1; step++) {
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
10 int swapped = false;
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
11
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
12 for (int i = 0; i < args->arr_size - step - 1; i++) {
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
13 args->comparisons++;
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
14 args->arr[i].current = true;
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
15 args->arr[i + 1].current = true;
29
dae463bbf5ca implementing multi-thread and refactoring
Dennis C. M. <dennis@denniscm.com>
parents:
diff changeset
16
30
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
17 if (args->arr[i].value > args->arr[i + 1].value) {
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
18 swap_elements(i, i + 1, args->arr);
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
19 swapped = true;
29
dae463bbf5ca implementing multi-thread and refactoring
Dennis C. M. <dennis@denniscm.com>
parents:
diff changeset
20 }
30
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
21
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
22 control_flow(args->delay, args->sequentially, &args->pause);
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
23 args->arr[i].current = false;
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
24 args->arr[i + 1].current = false;
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
25 }
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
26
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
27 if (swapped == 0) {
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
28 break;
29
dae463bbf5ca implementing multi-thread and refactoring
Dennis C. M. <dennis@denniscm.com>
parents:
diff changeset
29 }
dae463bbf5ca implementing multi-thread and refactoring
Dennis C. M. <dennis@denniscm.com>
parents:
diff changeset
30 }
dae463bbf5ca implementing multi-thread and refactoring
Dennis C. M. <dennis@denniscm.com>
parents:
diff changeset
31 }
30
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
32
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
33
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
34 /* Selection sort */
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
35
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
36 void *selection_sort(void *arguments) {
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
37 struct AlgoArgs *args = (struct AlgoArgs *)arguments;
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
38
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
39 for (int step = 0; step < args->arr_size - 1; step++) {
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
40 int min_idx = step;
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
41
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
42 for (int i = step + 1; i < args->arr_size; i++) {
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
43 args->comparisons++;
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
44 args->arr[i].current = true;
31
61104b22a25d I think it is working now...
Dennis C. M. <dennis@denniscm.com>
parents: 30
diff changeset
45 args->arr[min_idx].current = true;
61104b22a25d I think it is working now...
Dennis C. M. <dennis@denniscm.com>
parents: 30
diff changeset
46
61104b22a25d I think it is working now...
Dennis C. M. <dennis@denniscm.com>
parents: 30
diff changeset
47 control_flow(args->delay, args->sequentially, &args->pause);
61104b22a25d I think it is working now...
Dennis C. M. <dennis@denniscm.com>
parents: 30
diff changeset
48 args->arr[i].current = false;
61104b22a25d I think it is working now...
Dennis C. M. <dennis@denniscm.com>
parents: 30
diff changeset
49 args->arr[min_idx].current = false;
30
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
50
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
51 if (args->arr[i].value < args->arr[min_idx].value) {
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
52 min_idx = i;
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
53 }
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
54
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
55 }
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
56
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
57 swap_elements(min_idx, step, args->arr);
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
58 }
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
59 }
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
60
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
61
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
62 /* Quick sort */
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
63
38
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
64 int qs_partition(struct AlgoArgs *args, int left, int right) {
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
65 printf("Pivot index: %i\n", right);
30
f945bcc3571f refactor
Dennis C. M. <dennis@denniscm.com>
parents: 29
diff changeset
66
38
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
67 args->arr[right].current = true;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
68 float pivot = args->arr[right].value;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
69 control_flow(args->delay / 4, args->sequentially, &args->pause);
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
70
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
71 int i = left - 1;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
72
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
73 for (int j = left; j < right; j++) {
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
74 args->comparisons++;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
75 args->arr[j].current = true;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
76
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
77 control_flow(args->delay / 4, args->sequentially, &args->pause);
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
78
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
79 if (args->arr[j].value < pivot) {
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
80 printf("Value at index %i is smaller than pivot\n", j);
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
81 i++;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
82 printf("Swap with value at index %i\n", i);
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
83
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
84 args->arr[i].current = true;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
85 control_flow(args->delay / 4, args->sequentially, &args->pause);
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
86 args->arr[j].current = false;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
87 args->arr[i].current = false;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
88
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
89 struct Element temp = args->arr[i];
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
90 swap_elements(i, j, args->arr);
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
91
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
92 } else {
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
93 args->arr[j].current = false;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
94 }
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
95 }
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
96
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
97
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
98 printf("Swap pivot with value at index %i\n", i + 1);
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
99 args->arr[i + 1].current = true;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
100 control_flow(args->delay / 4, args->sequentially, &args->pause);
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
101 args->arr[right].current = false;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
102 args->arr[i + 1].current = false;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
103
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
104 struct Element temp = args->arr[i + 1];
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
105 swap_elements(i + 1, right, args->arr);
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
106
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
107 printf("Finished partition\n");
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
108
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
109 return i + 1;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
110 }
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
111
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
112
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
113 void *quick_sort(void *arguments) {
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
114 struct AlgoArgs *args = (struct AlgoArgs *)arguments;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
115
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
116 int left = 0;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
117 int right = args->arr_size - 1;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
118 int stack[right + 1 - left];
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
119 int top = -1;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
120
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
121 stack[++top] = left;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
122 stack[++top] = right;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
123
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
124 while (top >= 0) {
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
125 right = stack[top--];
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
126 left = stack[top--];
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
127
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
128 int pivot_index = qs_partition(args, left, right);
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
129
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
130 if (pivot_index - 1 > left) {
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
131 stack[++top] = left;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
132 stack[++top] = pivot_index - 1;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
133 }
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
134
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
135 if (pivot_index + 1 < right) {
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
136 stack[++top] = pivot_index + 1;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
137 stack[++top] = right;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
138 }
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
139 }
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
140 }
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
141
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
142
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
143 /* Insertion sort */
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
144
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
145 void *insertion_sort(void *arguments) {
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
146 struct AlgoArgs *args = (struct AlgoArgs *)arguments;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
147
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
148 for (int step = 1; step < args->arr_size; step++) {
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
149 struct Element key = args->arr[step];
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
150
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
151 printf("Selected key at index: %i\n", step);
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
152 args->arr[step].current = true;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
153 control_flow(args->delay / 3, args->sequentially, &args->pause);
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
154
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
155 int i = step - 1;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
156
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
157 while (key.value < args->arr[i].value && i >= 0) {
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
158 args->comparisons++;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
159 printf("Key value is smaller than value at index %i\n", i);
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
160
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
161 args->arr[i].current = true;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
162 args->arr[i + 1].value = 0;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
163 control_flow(args->delay / 3, args->sequentially, &args->pause);
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
164 args->arr[i].current = false;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
165
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
166 printf("Move foward\n");
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
167 args->arr[i + 1] = args->arr[i];
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
168
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
169 i--;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
170 }
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
171
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
172 printf("Place key at correct position\n");
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
173 args->arr[i + 1] = key;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
174
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
175 args->arr[i + 1].current = true;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
176 control_flow(args->delay / 3, args->sequentially, &args->pause);
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
177 args->arr[i + 1].current = false;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
178 args->arr[step].current = false;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
179 }
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
180 }
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
181
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
182
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
183 /* Merge sort */
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
184
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
185 void *merge_sort(void *arguments) {
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
186 struct AlgoArgs *args = (struct AlgoArgs *)arguments;
8ed1256dd518 finish quick sort and add insertion sort
Dennis C. M. <dennis@denniscm.com>
parents: 31
diff changeset
187 }