changeset 19:a027304ec75d

implement selection sort
author Dennis C. M. <dennis@denniscm.com>
date Mon, 26 Jun 2023 17:49:41 +0100
parents 6a5c5b137348
children fc44102980fb
files main.c
diffstat 1 files changed, 69 insertions(+), 19 deletions(-) [+]
line wrap: on
line diff
--- a/main.c	Sun Jun 25 19:23:49 2023 +0100
+++ b/main.c	Mon Jun 26 17:49:41 2023 +0100
@@ -25,43 +25,81 @@
 	void (*function)();
 };
 
-struct Algo algos[1];
+struct Algo algos[2];
 
 int selected_algo = 0;
-int speed = 5;
+int speed = 1;
 int refresh_counter = 0;
 int iter_counter = 0;
 int arr_size;
 
-float* arr;
+float *arr;
 
 bool run;
 
 
 /* Algorithms */
 
-// Bubble sort
-struct BubbleSortInfo {
-	int step;
-	int i;
+// Just some variables to store the state of the running algorithm
+struct AlgoState {
+	int a;
+	int b;
+	int c;
 };
 
-struct BubbleSortInfo bs = {1, 0};
+struct AlgoState as = {0, 0, 0};
+
+
+void swap_elements(int x, int y) {
+	float temp = arr[x];
+	arr[x] = arr[y];
+	arr[y] = temp;
+}
+
 
 void bubble_sort() {
-	if (bs.i < arr_size - bs.step - 1) {
-		float current = arr[bs.i];
-		float next = arr[bs.i + 1];
 
-		if (current > next) {
-			arr[bs.i + 1] = current;
-			arr[bs.i] = next;
+	/*
+	 * a: Index of the current selection
+	 * b: Index boundary of the sorted array
+	 */
+
+	if (as.a < arr_size - 1 - as.b) {
+		if (arr[as.a] > arr[as.a + 1]) {
+			swap_elements(as.a + 1, as.a);
 		}
 
-		bs.i++;
+		as.a++;
 	} else {
-		bs.step++;
-		bs.i = 0;
+		as.b++;
+		as.a = 0;
+	}
+}
+
+
+void selection_sort() {
+
+	/*
+	 * a: Index of current selection
+	 * b: Index of boundary of sorted array
+	 * c: Index of the minimum element
+	 */
+	
+
+	if (as.a < arr_size) {
+		if (arr[as.a] < arr[as.c]) {
+			
+			// Save new minimum
+			as.c = as.a;
+		}
+
+		as.a++;
+	} else {
+		swap_elements(as.b, as.c);
+
+		as.b++;
+		as.a = as.b;
+		as.c = as.a;
 	}
 }
 
@@ -117,6 +155,8 @@
 }
 
 
+
+
 /* Render functions */
 
 void render_text(int x, int y, char* text) {
@@ -269,7 +309,7 @@
 		run = false;
 
 		// Reset algo steps
-		bs = (struct BubbleSortInfo){0, 0};
+		as = (struct AlgoState){0, 0};
 	}
 	
 	// u: Increase speed
@@ -279,7 +319,9 @@
 
 	// d: reduce speed
 	if (key == 100) {
-		speed--;
+		if (speed > 1) {
+			speed--;
+		}
 	}
 	
 	// enter: Run program
@@ -287,6 +329,11 @@
 		run = true;
 	}
 
+	// p: Pause program
+	if (key == 112) {
+		run = false;
+	}
+
 	
 }
 
@@ -353,6 +400,9 @@
 	strcpy(algos[0].name, "Bubble sort");
 	algos[0].function = &bubble_sort;
 
+	strcpy(algos[1].name, "Selection sort");
+	algos[1].function = &selection_sort;
+	
 	create_array();
 
 	glutInit(&argc, argv);