diff src/algorithms.c @ 38:8ed1256dd518

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
line wrap: on
line diff
--- a/src/algorithms.c	Thu Jun 29 20:09:55 2023 +0100
+++ b/src/algorithms.c	Fri Jun 30 19:25:38 2023 +0100
@@ -61,4 +61,127 @@
 
 /* Quick sort */
 
+int qs_partition(struct AlgoArgs *args, int left, int right) {
+	printf("Pivot index: %i\n", right);
 
+	args->arr[right].current = true;
+	float pivot = args->arr[right].value;
+	control_flow(args->delay / 4, args->sequentially, &args->pause);
+	
+	int i = left - 1;
+
+    for (int j = left; j < right; j++) {
+		args->comparisons++;
+		args->arr[j].current = true;
+		
+		control_flow(args->delay / 4, args->sequentially, &args->pause);
+        
+		if (args->arr[j].value < pivot) {
+			printf("Value at index %i is smaller than pivot\n", j);
+            i++;	
+			printf("Swap with value at index %i\n", i);
+
+            args->arr[i].current = true;
+			control_flow(args->delay / 4, args->sequentially, &args->pause);
+			args->arr[j].current = false;
+            args->arr[i].current = false;
+
+			struct Element temp = args->arr[i];
+			swap_elements(i, j, args->arr);
+
+        } else {
+			args->arr[j].current = false;
+		}
+    }
+	
+    
+	printf("Swap pivot with value at index %i\n", i + 1);
+	args->arr[i + 1].current = true;
+	control_flow(args->delay / 4, args->sequentially, &args->pause);
+	args->arr[right].current = false;
+	args->arr[i + 1].current = false;
+	
+	struct Element temp = args->arr[i + 1];
+	swap_elements(i + 1, right, args->arr);
+
+	printf("Finished partition\n");
+
+    return i + 1;
+}
+
+
+void *quick_sort(void *arguments) {
+	struct AlgoArgs *args = (struct AlgoArgs *)arguments;
+	
+	int left = 0;
+	int right = args->arr_size - 1;
+    int stack[right + 1 - left];
+    int top = -1;
+
+    stack[++top] = left;
+    stack[++top] = right;
+
+    while (top >= 0) {
+        right = stack[top--];
+        left = stack[top--];
+
+        int pivot_index = qs_partition(args, left, right);
+
+        if (pivot_index - 1 > left) {
+            stack[++top] = left;
+            stack[++top] = pivot_index - 1;
+        }
+
+        if (pivot_index + 1 < right) {
+            stack[++top] = pivot_index + 1;
+            stack[++top] = right;
+        }
+    }
+}
+
+
+/* Insertion sort */
+
+void *insertion_sort(void *arguments) {
+	struct AlgoArgs *args = (struct AlgoArgs *)arguments;
+
+	for (int step = 1; step < args->arr_size; step++) {
+		struct Element key = args->arr[step];
+
+		printf("Selected key at index: %i\n", step);
+		args->arr[step].current = true;
+		control_flow(args->delay / 3, args->sequentially, &args->pause);
+
+		int i = step - 1;
+
+		while (key.value < args->arr[i].value && i >= 0) {
+			args->comparisons++;
+			printf("Key value is smaller than value at index %i\n", i);
+			
+			args->arr[i].current = true;
+			args->arr[i + 1].value = 0;
+			control_flow(args->delay / 3, args->sequentially, &args->pause);
+			args->arr[i].current = false;
+			
+			printf("Move foward\n");
+			args->arr[i + 1] = args->arr[i];
+
+			i--;
+		}
+
+		printf("Place key at correct position\n");
+		args->arr[i + 1] = key;
+		
+		args->arr[i + 1].current = true;
+		control_flow(args->delay / 3, args->sequentially, &args->pause);
+		args->arr[i + 1].current = false;
+		args->arr[step].current = false;
+	}
+}
+
+
+/* Merge sort */
+
+void *merge_sort(void *arguments) {
+	struct AlgoArgs *args = (struct AlgoArgs *)arguments;
+}