# HG changeset patch
# User Dennis C. M. <dennis@denniscm.com>
# Date 1688149538 -3600
# Node ID 8ed1256dd5182f1b32ffdfd9cee77b99ac1c0b57
# Parent  0e21212354139a4f6124e2b47f59b24603ca3bbd
finish quick sort and add insertion sort

diff -r 0e2121235413 -r 8ed1256dd518 README.md
--- a/README.md	Thu Jun 29 20:09:55 2023 +0100
+++ b/README.md	Fri Jun 30 19:25:38 2023 +0100
@@ -73,3 +73,6 @@
 Press `q` then press `ENTER` to visualize the algorithm step by step.   
 [Video.webm](https://github.com/denniscmartin/algo-animator/assets/66180929/743c00d8-5236-437d-85ad-b139611175ef)
 
+## Notes
+
+This project has not been designed to compare the speed of the algorithms side by side. The main objective is the visualization of the algorithms for educational purposes.
diff -r 0e2121235413 -r 8ed1256dd518 src/algorithms.c
--- 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;
+}
diff -r 0e2121235413 -r 8ed1256dd518 src/algorithms.h
--- a/src/algorithms.h	Thu Jun 29 20:09:55 2023 +0100
+++ b/src/algorithms.h	Fri Jun 30 19:25:38 2023 +0100
@@ -6,6 +6,8 @@
 
 void *bubble_sort(void *arguments);
 void *selection_sort(void *arguments);
+void *quick_sort(void *arguments);
+void *insertion_sort(void *arguments);
 
 
 #endif // ALGORITHMS_H
diff -r 0e2121235413 -r 8ed1256dd518 src/main.c
--- a/src/main.c	Thu Jun 29 20:09:55 2023 +0100
+++ b/src/main.c	Fri Jun 30 19:25:38 2023 +0100
@@ -7,7 +7,7 @@
 int rect_width = 5;
 int space = 1;
 
-struct Algo algos[2];
+struct Algo algos[4];
 int selected_algo = 0;
 int algos_size;
 
@@ -76,7 +76,7 @@
 	glBegin(GL_QUADS);
 
 	int x = 0;
-	for (int i = 0; i < algo_args.arr_size - 1; i++) {
+	for (int i = 0; i < algo_args.arr_size; i++) {
 
 		if (algo_args.arr[i].current) {
 			glColor3f(1.0, 1.0, 1.0);
@@ -304,6 +304,12 @@
 	strcpy(algos[1].name, "Selection sort");
 	algos[1].function = selection_sort;
 
+	strcpy(algos[2].name, "Quick sort");
+	algos[2].function = quick_sort;
+
+	strcpy(algos[3].name, "Insertion sort");
+	algos[3].function = insertion_sort;
+	
 	algos_size = sizeof(algos) / sizeof(algos[0]);
 
 	create_array(algo_args.arr, algo_args.arr_size, window_height, vpadding);