commit 04b1eef81c8358648bea2c5b6ca01f5643471e0d
parent 0205dc18cddcfaa5f1647773f0977e639c268aff
Author: klewer-martin <martin.cachari@gmail.com>
Date: Sun, 24 Apr 2022 01:44:58 -0300
Added heap sort algorithm
Heap sort algorithm added, plus other fixes
Diffstat:
| M | drw.c | | | 12 | ++++++------ |
| M | drw.h | | | 18 | ++++++++++-------- |
| M | main.c | | | 18 | ++++++++++-------- |
| M | sav.h | | | 1 | + |
| M | sort.c | | | 88 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------- |
| M | sort.h | | | 3 | +++ |
6 files changed, 111 insertions(+), 29 deletions(-)
diff --git a/drw.c b/drw.c
@@ -47,29 +47,29 @@ void drw_status_bar(Drw *drw, SAV *sav) {
/* TODO: create a function which fetchs the status text to be drawn based on the status */
if(sav->status == WELCOME) {
snprintf(drw->bar_text, drw->bar_text_len - 2,
- " Welcome to sorting algorithms visualized [%s sort] press SPACE to start sorting",
+ " Welcome to sorting algorithms visualized [%s] press SPACE to start sorting",
algo_sel_str[sav->sort_algo]);
}
else if(sav->status == START) {
snprintf(drw->bar_text, drw->bar_text_len - 2,
- " %-8s [%s sort] press SPACE to start sorting", sort_status_str[OK],
+ " %-8s [%s] press SPACE to start sorting", sort_status_str[OK],
algo_sel_str[sav->sort_algo]);
}
else if(sav->status == RUN) {
if(sav->sort_status == PAUSE)
snprintf(drw->bar_text, drw->bar_text_len - 2,
- " %-8s [%s sort] L: %ld, C: %ld, S: %ld Press SPACE to resume", sort_status_str[sav->sort_status],
+ " %-8s [%s] L: %ld, C: %ld, S: %ld Press SPACE to resume", sort_status_str[sav->sort_status],
algo_sel_str[sav->sort_algo], sav->arr->len, sav->cmps,
sav->swps);
else if(sav->sort_status == SORTED)
snprintf(drw->bar_text, drw->bar_text_len - 2,
- " %-8s [%s sort] L: %ld, C: %ld, S: %ld, done in %lds, extra storage used: %ld Bytes",
+ " %-8s [%s] L: %ld, C: %ld, S: %ld, done in %lds, extra storage used: %ld Bytes",
sort_status_str[sav->sort_status],
algo_sel_str[sav->sort_algo],
sav->arr->len, sav->cmps, sav->swps, (sav->tf - sav->ti), sav->B_used);
else if(sav->sort_status == RUN)
snprintf(drw->bar_text, drw->bar_text_len - 2,
- " %-8s [%s sort] L: %ld, C: %ld, S: %ld", sort_status_str[sav->sort_status],
+ " %-8s [%s] L: %ld, C: %ld, S: %ld", sort_status_str[sav->sort_status],
algo_sel_str[sav->sort_algo], sav->arr->len, sav->cmps,
sav->swps);
}
@@ -141,7 +141,7 @@ status_t Drw_new(Drw **drw) {
{
int w_text, h_text;
TTF_SizeText(font,
- "SORTED [XXXXXXXXXXs sort] done in XXX.Xs, L: XXXXX,\
+ "SORTED [XXXXXXXXXXXXXXXXXXXXX] done in XXX.Xs, L: XXXXX,\
C: XXXXXX, S: XXXXXX, I: XXXXXX, storage used: XXXXXX Bytes",
&w_text, &h_text);
diff --git a/drw.h b/drw.h
@@ -44,14 +44,16 @@ typedef struct {
char *bar_text;
} Drw;
-static char * const algo_sel_str[ALGORITHMS_COUNT] = {
- "bubble",
- "improved bubble",
- "insertion",
- "merge",
- "quick",
- "shell",
- "selection"
+static char * const algo_sel_str[ALGORITHMS_COUNT + 1] = {
+ "bubble sort",
+ "improved bubble sort",
+ "insertion sort",
+ "merge sort",
+ "quick sort",
+ "shell sort",
+ "selection sort",
+ "heap sort",
+ "sort not set"
};
static char * const sort_status_str[STATUS_MAX] = {
diff --git a/main.c b/main.c
@@ -1,5 +1,6 @@
#include <stdio.h>
#include <pthread.h>
+#include <assert.h>
#include "sav.h"
#include "drw.h"
@@ -23,16 +24,16 @@ static void (*sort_handler[ALGORITHMS_COUNT])(SAV *) = {
&merge_sort_wrapper,
&quick_sort_wrapper,
&shell_sort,
- &selection_sort
+ &selection_sort,
+ &heap_sort
};
void *routine_wrapper(void *arg) {
SAV *sav = (SAV *)arg;
- if(sav->sort_algo == ALGORITHMS_COUNT) {
- fprintf(stderr, "ERROR: \"sort_algo\" not set. exiting\n");
- sav->status = STOP;
- } else sort_handler[sav->sort_algo](sav);
+ assert((sav->sort_algo != ALGORITHMS_COUNT) && "Default sorting algorithm not set");
+
+ sort_handler[sav->sort_algo](sav);
return NULL;
}
@@ -48,8 +49,8 @@ void sort_selector(SAV *sav) {
/* TODO: Support sound */
int main (void) {
- SAV *sav;
- Drw *drw;
+ SAV *sav = NULL;
+ Drw *drw = NULL;
time_t tic, toc;
pthread_t p1 = 0;
@@ -62,7 +63,7 @@ int main (void) {
shuffle(sav->arr);
/* selecting the sorting algorithm */
- sav->sort_algo = QUICK_SORT;
+ sav->sort_algo = SELECTION_SORT;
sav->status = WELCOME;
sav->sort_status = PAUSE;
@@ -77,6 +78,7 @@ int main (void) {
drw_array_graph(drw, sav);
drw_status_bar(drw, sav);
+
SDL_RenderPresent(drw->rend);
/* Print welcome message only on startup */
diff --git a/sav.h b/sav.h
@@ -18,6 +18,7 @@ typedef enum {
QUICK_SORT,
SHELL_SORT,
SELECTION_SORT,
+ HEAP_SORT,
ALGORITHMS_COUNT
} sort_t;
diff --git a/sort.c b/sort.c
@@ -7,7 +7,7 @@
void set_sort_speed(SAV *sav, size_t new_value) {
if(sav == NULL) return;
- if((new_value > 0) && (new_value < SORT_DELAY_MAX)) {
+ if((new_value > 0) && (new_value <= SORT_DELAY_MAX)) {
printf("INFO: Updating sort_delay to: %ld\n", new_value);
sav->sort_delay = new_value;
}
@@ -143,19 +143,27 @@ void merge(SAV *sav, int low, int middle, int high) {
for(i = low, j = 0; i < middle; i++, j++)
B[j] = sav->arr->v[i];
- /* C middle high part of the array */
+ /* C middle high */
for(i = middle, j = 0; i < high; i++, j++)
C[j] = sav->arr->v[i];
- /* merge B1 and C1 in order */
+ /* merge B and C in order */
for(k = low, i = j = 0; (k < high) && (i < n1) && (j < n2); k++) {
- if(B[i] <= C[j]) sav->arr->v[k] = B[i++];
- else sav->arr->v[k] = C[j++];
+ if(B[i] <= C[j]) {
+ sav->arr->v[k] = B[i++];
+ sav->cmps += 1;
+ }
+ else {
+ sav->cmps += 1;
+ sav->arr->v[k] = C[j++];
+ }
sav->sel = (k + 1);
sav->cmps += 1;
sav->its += 1;
+ /* double delay; to match speed of other algorithms */
+ if(sort_delay(sav) == STOP) return;
if(sort_delay(sav) == STOP) return;
if(sort_pause(sav) == STOP) return;
}
@@ -179,6 +187,8 @@ void merge_sort(SAV *sav, int low, int high) {
/* merge both arrays ordered */
merge(sav, low, middle, high);
+
+ sav->cmps += 1;
}
}
@@ -208,6 +218,7 @@ void quick_sort_partition(SAV *sav, int low, int *middle, int high) {
sav->cmp = j;
if(sort_delay(sav) == STOP) return;
+ if(sort_delay(sav) == STOP) return;
if(sort_pause(sav) == STOP) return;
}
@@ -260,7 +271,6 @@ void shell_sort(SAV *sav) {
}
sav->arr->v[j] = temp;
sav->swps += 1;
- sav->cmps += 1;
}
}
sav->tf = time(NULL);
@@ -282,7 +292,8 @@ void selection_sort(SAV *sav)
sav->sel = i;
for (j = i + 1; j < sav->arr->len; j++) {
if (sav->arr->v[j] < sav->arr->v[min]) min = j;
- sav->cmp = min;
+ sav->cmps += 1;
+ sav->cmp = j;
if(sort_delay(sav) == STOP) return;
if(sort_pause(sav) == STOP) return;
}
@@ -290,8 +301,71 @@ void selection_sort(SAV *sav)
if(sort_delay(sav) == STOP) return;
if(sort_pause(sav) == STOP) return;
swap(&sav->arr->v[i], &sav->arr->v[min]);
+ sav->swps += 1;
}
sav->tf = time(NULL);
if(sav->sort_status != STOP) sav->sort_status = SORTED;
}
+
+
+/* build max_heap */
+void heapify(SAV *sav, int len, int i) {
+ /* Find largest among root, left child and right child */
+ int root = i;
+ int child_left = 2 * i + 1;
+ int child_right = 2 * i + 2;
+
+ sav->cmp = child_left;
+ sav->cmps += 1;
+ if((child_left < len) && (sav->arr->v[child_left] > sav->arr->v[root]))
+ root = child_left;
+
+ sav->cmp = child_right;
+ sav->cmps += 1;
+ if((child_right < len) && (sav->arr->v[child_right] > sav->arr->v[root]))
+ root = child_right;
+
+ /* Swap and continue heapifying if root is not root */
+ sav->cmps += 1;
+ if(root != i) {
+ sav->swps += 1;
+ swap(&(sav->arr->v[i]), &sav->arr->v[root]);
+ heapify(sav, len, root);
+ }
+
+ if(sort_delay(sav) == STOP) return;
+ if(sort_pause(sav) == STOP) return;
+}
+
+/* Main function to do heap sort */
+void heap_sort(SAV *sav) {
+ int i;
+ if(sav == NULL) return;
+
+ sav->ti = time(NULL);
+
+ /* Build max heap */
+ for (i = ((sav->arr->len / 2) - 1); i >= 0; i--) {
+ heapify(sav, sav->arr->len, i);
+ }
+
+ /* Heap sort */
+ for (i = (sav->arr->len - 1); i >= 0; i--) {
+ /* The root element gets swapped with the last one, then gets ignored */
+ sav->sel = i;
+
+ sav->swps += 1;
+ swap(&sav->arr->v[0], &sav->arr->v[i]);
+
+ if(sort_delay(sav) == STOP) return;
+ if(sort_pause(sav) == STOP) return;
+
+ /* Heapify root element to get highest element at root again */
+ heapify(sav, i, 0);
+ }
+
+ if(sav->sort_status != STOP) sav->sort_status = SORTED;
+ sav->sel = sav->cmp = ARR_MAX + 1;
+ sav->tf = time(NULL);
+}
diff --git a/sort.h b/sort.h
@@ -26,4 +26,7 @@ void quick_sort_partition(SAV *sav, int low, int *middle, int high);
void shell_sort(SAV *sav);
void selection_sort(SAV *sav);
+void heap_sort(SAV *sav);
+void heapify(SAV *sav, int len, int i);
+
#endif // __SORT_H__
