commit 5fb3b1f25bdf88105fc7ec194ff9a347c83721bb
parent e14c6bdecaa21ede122588c85c693347bb168bfc
Author: klewer-martin <martin.cachari@gmail.com>
Date: Sun, 10 Apr 2022 01:14:42 -0300
Added merge sort algorithm and main.c file
In this commit a main.c file has been added in which is located the main
function, leaving the sav.c file (where it was located previously) free
to use for the SAV structure and functions.
Merge sort algorithms has also been added.
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
