commit 365b49e12fb2494e35268346cdae4db873dba322
parent e14c6bdecaa21ede122588c85c693347bb168bfc
Author: Martin J. Klöckner <64109770+klewer-martin@users.noreply.github.com>
Date: Sun, 10 Apr 2022 01:18:32 -0300
Merge pull request #1 from klewer-martin/mergesort
Added merge sort algorithm and main.c file
Diffstat:
| M | Makefile | | | 2 | +- |
| M | README.md | | | 12 | +++++++++++- |
| M | drw.c | | | 13 | ++++--------- |
| A | main.c | | | 78 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | sav.c | | | 68 | +++----------------------------------------------------------------- |
| M | sav.h | | | 10 | ++++++++++ |
| M | sort.c | | | 64 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | sort.h | | | 4 | ++++ |
| M | util.h | | | 4 | ++-- |
9 files changed, 177 insertions(+), 78 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,7 +1,7 @@
CC := cc
CLIBS := `sdl2-config --libs --cflags`
CFLAGS := -lSDL2_ttf -lm -Werror -Wall -pedantic -ansi -std=c99 -g -pthread
-SRCS := sav.c util.c sort.c drw.c sdl_extra.c
+SRCS := main.c sav.c util.c sort.c drw.c sdl_extra.c
OBJS := $(SRCS:.c=.o)
TARGET := sav
diff --git a/README.md b/README.md
@@ -2,6 +2,16 @@
The idea is to develop a visual program that shows how an array is being sorted
+Written using C and SDL2 library for graphics
+
-ToDo: make the window more responsive, mapping keyboard keys to control speed of sorting, play, pause the sort, etc; commandline arguments, sounds
+# Quick start
+```console
+$ make
+$ ./sav
+```
+
+You can set the sorting algorithm by setting the varible "sel\_algo" in the main function
+
+(in a future this will be done by parsing command line arguments)
diff --git a/drw.c b/drw.c
@@ -57,24 +57,19 @@ drw_status_bar(Drw *drw, SAV *sav) {
char status_text[drw-> w / drw->font_size];
- /* sprintf(status_text, "SORTING (insertion sort) C: %ld, S: %ld", sav->comparisons, sav->swaps); */
- /* sprintf(status_text, "SORTING (insertion sort)", sav->comparisons, sav->swaps); */
- /* sprintf(status_text, "C: %ld, S: %ld", sav->comparisons, sav->swaps); */
-
if((sav->status == RUN) || (sav->status == UPDATE)) {
/* sprintf(status_text, "Press SPACE to start sorting the array or ESC/q to quit"); */
- sprintf(status_text, "SORTING (insertion sort) L: %ld, C: %ld, S: %ld, I: %ld",
- sav->arr->len, sav->cmps, sav->swps, sav->its);
+ sprintf(status_text, "SORTING (%s sort) L: %ld, C: %ld, S: %ld, I: %ld",
+ algo_strings[sav->sel_algo], sav->arr->len, sav->cmps, sav->swps, sav->its);
drw_text(drw, status_text, 0, drw->h - drw->font_size - 5);
} else if(sav->status == SORTED) {
- sprintf(status_text, "SORTED (insertion sort) done in %.2fs, L: %ld, C: %ld, S: %ld, I: %ld",
+ sprintf(status_text, "SORTED (%s sort) done in %.2fs, L: %ld, C: %ld, S: %ld, I: %ld",
+ algo_strings[sav->sel_algo],
(double)(sav->tf - sav->ti) / CLOCKS_PER_SEC,
sav->arr->len, sav->cmps, sav->swps, sav->its);
drw_text(drw, status_text, 0, drw->h - drw->font_size - 5);
}
-
- /* SDL_RenderCopy(drw->rend, drw->text_texture, NULL, &text_rect); */
}
void drw_text(Drw *drw, char *text, int x, int y) {
diff --git a/main.c b/main.c
@@ -0,0 +1,78 @@
+#include <stdio.h>
+#include <pthread.h>
+
+#include "drw.h"
+#include "sort.h"
+#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;
+
+ switch(sav->sel_algo) {
+ case BUBBLE_SORT: bubble_sort(sav); break;
+ case INSERTION_SORT: insertion_sort(sav); break;
+ case MERGE_SORT: merge_sort_wrapper(sav); break;
+ default: {
+ fprintf(stderr, "\"sel_algo\" not set. exiting\n");
+ sav->status = STOP;
+ break;
+ }
+ }
+ return NULL;
+}
+
+int
+main (void) {
+ SAV *sav;
+ Drw *drw;
+ SDL_Renderer *rend;
+ SDL_Window *win;
+
+ pthread_t p1;
+
+ setup(&win, &rend);
+
+ SAV_New(&sav);
+ DRW_New(rend, win, &drw);
+
+ /* assigns random values to array */
+ srand((unsigned int)time(NULL));
+ for(size_t i = 0; i < sav->arr->len; i++)
+ while(!(sav->arr->v[i] = rand() % ARR_MAX));
+
+ /* start sorting thread */
+ pthread_create(&p1, NULL, &routine_wrapper, (void *)sav);
+
+ /* selecting the sorting algorithms */
+ sav->sel_algo = MERGE_SORT;
+
+ /* main loop */
+ while(sav->status != STOP) {
+ check_events(&(sav->status));
+ if(sav->status == UPDATE) {
+ drw_array_graph(drw, sav);
+ sav->status = RUN;
+ SDL_RenderPresent(rend);
+ }
+ if(sav->status == SORTED) {
+ drw_array_graph(drw, sav);
+ SDL_RenderPresent(rend);
+ }
+ }
+
+ pthread_join(p1, NULL);
+
+ SAV_Destroy(sav);
+ DRW_Destroy(drw);
+
+ cleanup(win, rend);
+ return 0;
+}
diff --git a/sav.c b/sav.c
@@ -1,25 +1,18 @@
-#include <time.h>
-#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdbool.h>
-#include <pthread.h>
-#include <SDL2/SDL.h>
-#include <SDL2/SDL_ttf.h>
-
-#include "sav.h"
#include "drw.h"
#include "util.h"
-#include "sort.h"
-#include "sdl_extra.h"
status_t SAV_New(SAV **sav) {
if((*sav = (SAV *)malloc(sizeof(SAV))) == NULL)
return ERROR_MEMORY_ALLOC;
- (*sav)->sel = (*sav)->cmp = (*sav)->cmps = (*sav)->swps = (*sav)->its = 0;
+ (*sav)->sel = (*sav)->cmps = (*sav)->swps = (*sav)->its = 0;
+ (*sav)->cmp = ARR_MAX + 1;
(*sav)->status = RUN;
+ (*sav)->sel_algo = SORT_MAX_ALGORITHMS;
if(((*sav)->arr = (Arr *)malloc(sizeof(Arr))) == NULL)
return ERROR_MEMORY_ALLOC;
@@ -40,58 +33,3 @@ void SAV_Destroy(SAV *sav) {
free(sav->arr);
free(sav);
}
-
-void *
-routine_wrapper(void *arg) {
- SAV *sav = (SAV *)arg;
-
- insertion_sort(sav);
- /* bubble_sort(sav); */
-
- return NULL;
-}
-
-int
-main (void) {
- SAV *sav;
- Drw *drw;
- SDL_Renderer *rend;
- SDL_Window *win;
-
- pthread_t p1;
-
- setup(&win, &rend);
-
- SAV_New(&sav);
- DRW_New(rend, win, &drw);
-
- /* assigns random values to array */
- srand((unsigned int)time(NULL));
- for(size_t i = 0; i < sav->arr->len; i++)
- while(!(sav->arr->v[i] = rand() % ARR_MAX));
-
- /* start sorting thread */
- pthread_create(&p1, NULL, &routine_wrapper, (void *)sav);
-
- /* main loop */
- while(sav->status != STOP) {
- check_events(&(sav->status));
- if(sav->status == UPDATE) {
- drw_array_graph(drw, sav);
- sav->status = RUN;
- SDL_RenderPresent(rend);
- }
- if(sav->status == SORTED) {
- drw_array_graph(drw, sav);
- SDL_RenderPresent(rend);
- }
- }
-
- pthread_join(p1, NULL);
-
- SAV_Destroy(sav);
- DRW_Destroy(drw);
-
- cleanup(win, rend);
- return 0;
-}
diff --git a/sav.h b/sav.h
@@ -6,13 +6,23 @@
#include <time.h>
#include <SDL2/SDL.h>
+typedef enum {
+ BUBBLE_SORT = 0,
+ INSERTION_SORT,
+ MERGE_SORT,
+ SORT_MAX_ALGORITHMS
+} sort_t;
+
typedef struct {
Arr *arr;
size_t sel, cmp, cmps, swps, its;
clock_t ti, tf;
status_t status;
+ sort_t sel_algo;
} SAV;
+extern char *algo_strings[SORT_MAX_ALGORITHMS];
+
status_t SAV_New(SAV **sav);
void SAV_Destroy(SAV *sav);
diff --git a/sort.c b/sort.c
@@ -66,3 +66,67 @@ void bubble_sort(SAV *sav) {
sav->tf = clock();
if(sav->status != STOP) sav->status = SORTED;
}
+
+void merge(SAV *sav, int low, int middle, int high) {
+ size_t n1, n2, i, j, k;
+
+ n1 = middle - low;
+ n2 = high - middle;
+
+ int B[n1], C[n2];
+
+ /* B holds middle low array */
+ for(i = low, j = 0; i < middle; i++, j++)
+ B[j] = sav->arr->v[i];
+
+ /* C middle high part of the array */
+ for(i = middle, j = 0; i < high; i++, j++)
+ C[j] = sav->arr->v[i];
+
+ /* merge B1 and C1 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++];
+
+ sav->sel = (k + 1);
+ sav->cmps += 1;
+ sav->its += 1;
+
+ wait_main_thread(&(sav->status));
+ if(sav->status == STOP) return;
+ }
+
+ while(i < n1)
+ sav->arr->v[k++] = B[i++];
+
+ while (j < n2)
+ sav->arr->v[k++] = C[j++];
+}
+
+void merge_sort(SAV *sav, int low, int high) {
+ if(sav == NULL) return;
+
+ int middle;
+
+ middle = ((high + low) / 2);
+ sav->its += 1;
+
+ if((high - low) > 1) {
+ /* sort the middle low portion of the array */
+ merge_sort(sav, low, middle);
+
+ /* sort the middle high portion of the array */
+ merge_sort(sav, middle, high);
+
+ /* merge both arrays ordered */
+ merge(sav, low, middle, high);
+ }
+}
+
+void merge_sort_wrapper(SAV *sav) {
+ sav->ti = clock();
+ merge_sort(sav, 0, sav->arr->len);
+ sav->tf = clock();
+ sav->sel = sav->arr->len + 1;
+ if(sav->status != STOP) sav->status = SORTED;
+}
diff --git a/sort.h b/sort.h
@@ -10,4 +10,8 @@
void bubble_sort(SAV *);
void insertion_sort(SAV *);
+void merge(SAV *, int, int, int);
+void merge_sort(SAV *, int, int);
+void merge_sort_wrapper(SAV *);
+
#endif // __SORT_H__
diff --git a/util.h b/util.h
@@ -4,8 +4,8 @@
#include <stdio.h>
#include <stdlib.h>
-#define ARR_LEN 100
-#define ARR_MAX 400
+#define ARR_LEN 150
+#define ARR_MAX 500
#define X_BORDER 40
#define Y_BORDER 40
