commit 7b58aefa91c06a7c6eaaf39914e208e8c192e6a3
parent 7bd2407f7d44290ca008ff4d0680db7ab14245fe
Author: Martin J. Klöckner <64109770+klewer-martin@users.noreply.github.com>
Date: Wed, 13 Apr 2022 16:19:04 -0300
Merge pull request #4 from klewer-martin/quicksort
Quicksort
Diffstat:
7 files changed, 89 insertions(+), 19 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",
+ "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->arr->len, sav->cmps, sav->swps, sav->B_used);
drw_text(drw, drw->bar_text, 0, drw->h - drw->font_size - 5);
}
@@ -125,7 +125,17 @@ status_t DRW_New(SDL_Renderer *rend, SDL_Window *win, Drw **drw) {
else if((*drw)->h < WIN_MIN_H)
(*drw)->h = WIN_MIN_H;
- (*drw)->bar_text_len = (*drw)->w / (*drw)->font_size;
+ {
+ int w_text, h_text;
+ TTF_SizeText(font,
+ "SORTED (XXXXXXXXXXs sort) done in XXX.Xs, L: XXXXX,\
+ C: XXXXXX, S: XXXXXX, I: XXXXXX, storage used: XXXXXX Bytes",
+ &w_text, &h_text);
+
+ (*drw)->bar_text_len = w_text;
+ }
+
+
(*drw)->bar_text = (char *)malloc(sizeof(char) * (*drw)->bar_text_len);
if((*drw)->bar_text == NULL) return ERROR_MEMORY_ALLOC;
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 = MERGE_SORT;
+ sav->sel_algo = QUICK_SORT;
+
+ sav->status = RUN;
/* main loop */
while(sav->status != STOP) {
diff --git a/sav.c b/sav.c
@@ -5,11 +5,18 @@
#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;
- (*sav)->sel = (*sav)->cmps = (*sav)->swps = (*sav)->its = 0;
+ (*sav)->sel = (*sav)->cmps = (*sav)->swps = (*sav)->its = (*sav)->B_used = 0;
(*sav)->cmp = ARR_MAX + 1;
(*sav)->status = RUN;
(*sav)->sel_algo = SORT_MAX_ALGORITHMS;
diff --git a/sav.h b/sav.h
@@ -10,12 +10,13 @@ typedef enum {
BUBBLE_SORT = 0,
INSERTION_SORT,
MERGE_SORT,
+ QUICK_SORT,
SORT_MAX_ALGORITHMS
} sort_t;
typedef struct {
Arr *arr;
- size_t sel, cmp, cmps, swps, its;
+ size_t sel, cmp, cmps, swps, its, B_used;
clock_t ti, tf;
status_t status;
sort_t sel_algo;
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;
@@ -75,6 +77,9 @@ void merge(SAV *sav, int low, int middle, int high) {
int B[n1], C[n2];
+ sav->B_used += n1;
+ sav->B_used += n2;
+
/* B holds middle low array */
for(i = low, j = 0; i < middle; i++, j++)
B[j] = sav->arr->v[i];
@@ -103,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;
@@ -130,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__
diff --git a/util.h b/util.h
@@ -4,14 +4,14 @@
#include <stdio.h>
#include <stdlib.h>
-#define ARR_LEN 120
+#define ARR_LEN 128
#define ARR_MAX 500
#define X_BORDER 40
#define Y_BORDER 40
#define TOP_BORDER 50
-#define RECT_WIDTH 6
+#define RECT_WIDTH 5
typedef enum {
OK = 0,
