commit c20c5e7e5ecf8906058c773ce956d0092fae6f24
parent 580a98a42c5d1edeb4cd325b053fdaa217652bf4
Author: klewer-martin <martin.cachari@gmail.com>
Date: Wed, 13 Apr 2022 16:18:41 -0300
Added quick sort algorithm
Diffstat:
6 files changed, 71 insertions(+), 14 deletions(-)
diff --git a/drw.c b/drw.c
@@ -60,17 +60,17 @@ drw_status_bar(Drw *drw, SAV *sav) {
if(sav->status == UPDATE) {
/* sprintf(drw->bar_text, "Press SPACE to start sorting the array or ESC/q to quit"); */
snprintf(drw->bar_text, drw->bar_text_len - 2,
- "SORTING (%s sort) L: %ld, C: %ld, S: %ld, I: %ld",
+ "SORTING (%s sort) L: %ld, C: %ld, S: %ld",
algo_strings[sav->sel_algo], sav->arr->len, sav->cmps,
- sav->swps, sav->its);
+ sav->swps);
drw_text(drw, drw->bar_text, 0, drw->h - drw->font_size - 5);
} else if(sav->status == SORTED) {
snprintf(drw->bar_text, drw->bar_text_len - 2,
- "SORTED (%s sort) done in %.2fs, L: %ld, C: %ld, S: %ld, I: %ld, extra storage used: %ld Bytes",
+ "SORTED (%s sort) done in %.2fs, L: %ld, C: %ld, S: %ld, extra storage used: %ld Bytes",
algo_strings[sav->sel_algo],
(double)(sav->tf - sav->ti) / CLOCKS_PER_SEC,
- sav->arr->len, sav->cmps, sav->swps, sav->its, sav->B_used);
+ sav->arr->len, sav->cmps, sav->swps, sav->B_used);
drw_text(drw, drw->bar_text, 0, drw->h - drw->font_size - 5);
}
diff --git a/main.c b/main.c
@@ -6,12 +6,6 @@
#include "util.h"
#include "sdl_extra.h"
-char *algo_strings[SORT_MAX_ALGORITHMS] = {
- "bubble",
- "insertion",
- "merge"
-};
-
void *
routine_wrapper(void *arg) {
SAV *sav = (SAV *)arg;
@@ -20,6 +14,7 @@ routine_wrapper(void *arg) {
case BUBBLE_SORT: bubble_sort(sav); break;
case INSERTION_SORT: insertion_sort(sav); break;
case MERGE_SORT: merge_sort_wrapper(sav); break;
+ case QUICK_SORT: quick_sort_wrapper(sav); break;
default: {
fprintf(stderr, "\"sel_algo\" not set. exiting\n");
sav->status = STOP;
@@ -58,7 +53,9 @@ main (void) {
pthread_create(&p1, NULL, &routine_wrapper, (void *)sav);
/* selecting the sorting algorithms */
- sav->sel_algo = INSERTION_SORT;
+ sav->sel_algo = QUICK_SORT;
+
+ sav->status = RUN;
/* main loop */
while(sav->status != STOP) {
diff --git a/sav.c b/sav.c
@@ -5,6 +5,13 @@
#include "drw.h"
#include "util.h"
+char *algo_strings[SORT_MAX_ALGORITHMS] = {
+ "bubble",
+ "insertion",
+ "merge",
+ "quick"
+};
+
status_t SAV_New(SAV **sav) {
if((*sav = (SAV *)malloc(sizeof(SAV))) == NULL)
return ERROR_MEMORY_ALLOC;
diff --git a/sav.h b/sav.h
@@ -10,6 +10,7 @@ typedef enum {
BUBBLE_SORT = 0,
INSERTION_SORT,
MERGE_SORT,
+ QUICK_SORT,
SORT_MAX_ALGORITHMS
} sort_t;
diff --git a/sort.c b/sort.c
@@ -42,7 +42,8 @@ insertion_sort(SAV *sav) {
if(sav->status != STOP) sav->status = SORTED;
}
-void bubble_sort(SAV *sav) {
+void
+bubble_sort(SAV *sav) {
size_t i, j;
sav->ti = clock();
@@ -67,7 +68,8 @@ void bubble_sort(SAV *sav) {
if(sav->status != STOP) sav->status = SORTED;
}
-void merge(SAV *sav, int low, int middle, int high) {
+void
+merge(SAV *sav, int low, int middle, int high) {
size_t n1, n2, i, j, k;
n1 = middle - low;
@@ -106,7 +108,8 @@ void merge(SAV *sav, int low, int middle, int high) {
sav->arr->v[k++] = C[j++];
}
-void merge_sort(SAV *sav, int low, int high) {
+void
+merge_sort(SAV *sav, int low, int high) {
if(sav == NULL) return;
int middle;
@@ -133,3 +136,48 @@ void merge_sort_wrapper(SAV *sav) {
sav->sel = sav->arr->len + 1;
if(sav->status != STOP) sav->status = SORTED;
}
+
+void
+quick_sort_partition(SAV *sav, int low, int *middle, int high) {
+ int i, j, pivot;
+
+ pivot = high;
+ sav->sel = pivot;
+ printf("SORT: pivot: %d\n", pivot);
+
+ for(i = j = low; j < high; j++, sav->cmps += 1) {
+ if(sav->arr->v[j] < sav->arr->v[pivot]) {
+ swap(&(sav->arr->v[i++]), &(sav->arr->v[j]));
+ sav->swps += 1;
+ }
+
+ wait_main_thread(&(sav->status));
+ if(sav->status == STOP) return;
+ }
+
+ swap(&(sav->arr->v[i]), &(sav->arr->v[pivot]));
+ sav->swps += 1;
+ *middle = i;
+}
+
+void
+quick_sort(SAV *sav, int low, int high) {
+ int pivot;
+
+ wait_main_thread(&(sav->status));
+ if(sav->status == STOP) return;
+
+ if ((high - low) > 0) {
+ quick_sort_partition(sav, low, &pivot, high);
+ quick_sort(sav, low, pivot - 1);
+ quick_sort(sav, pivot + 1, high);
+ }
+}
+
+void
+quick_sort_wrapper(SAV *sav) {
+ sav->ti = clock();
+ quick_sort(sav, 0, sav->arr->len - 1);
+ sav->status = SORTED;
+ sav->tf = clock();
+}
diff --git a/sort.h b/sort.h
@@ -14,4 +14,8 @@ void merge(SAV *, int, int, int);
void merge_sort(SAV *, int, int);
void merge_sort_wrapper(SAV *);
+void quick_sort_wrapper(SAV *sav);
+void quick_sort(SAV *sav, int low, int high);
+void quick_sort_partition(SAV *sav, int low, int *middle, int high);
+
#endif // __SORT_H__
