commit 02e7616bb964b6627d79e7cbb4b40ecf3c1850cc
parent 4e4c17a8aec28208452c36dd5eb97e58fe9ed5b8
Author: Martin J. Klöckner <64109770+klewer-martin@users.noreply.github.com>
Date: Mon, 25 Apr 2022 00:16:09 -0300
Merge pull request #13 from klewer-martin/array_methods
Added reversed and in_order array functions plus other fixes
Diffstat:
7 files changed, 68 insertions(+), 28 deletions(-)
diff --git a/array.c b/array.c
@@ -10,3 +10,22 @@ void shuffle(Arr *arr) {
printf("ARRAY: Shuffling array done\n");
}
+
+void reversed(Arr *arr) {
+ size_t i;
+ int per_element;
+
+ per_element = (ARR_MAX / arr->len);
+ for(i = 0; i < arr->len; i++)
+ arr->v[i] = (arr->len * per_element) - (i * per_element);
+}
+
+void in_order(Arr *arr) {
+ size_t i;
+ int per_element;
+
+ per_element = (ARR_MAX / arr->len);
+
+ for(i = 0; i < arr->len; i++)
+ arr->v[i] = (i * per_element);
+}
diff --git a/array.h b/array.h
@@ -4,7 +4,7 @@
#include <stdlib.h>
#define ARR_LEN 128
-#define ARR_MAX 500
+#define ARR_MAX 512
typedef struct {
int *v;
@@ -12,5 +12,7 @@ typedef struct {
} Arr;
void shuffle(Arr *arr);
+void reversed(Arr *arr);
+void in_order(Arr *arr);
#endif
diff --git a/drw.c b/drw.c
@@ -58,7 +58,8 @@ void drw_status_bar(Drw *drw, SAV *sav) {
else if(sav->status == RUN) {
if(sav->sort_status == PAUSE)
snprintf(drw->bar_text, drw->bar_text_len - 2,
- " %-8s [%s] 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)
diff --git a/main.c b/main.c
@@ -15,7 +15,6 @@ void check_events(Drw *, SAV *);
/* void *(*start_routine)(void *), pthread_create routine */
void *routine_wrapper(void *);
-void sort_selector(SAV *sav);
static void (*sort_handler[ALGORITHMS_COUNT])(SAV *) = {
&bubble_sort,
@@ -38,13 +37,7 @@ void *routine_wrapper(void *arg) {
return NULL;
}
-void sort_selector(SAV *sav) {
- if(sav->sort_algo == (ALGORITHMS_COUNT - 1))
- sav->sort_algo = 0;
- else sav->sort_algo++;
-}
-
-/* TODO: Support random, reversed, in_order arrays */
+/* TODO: Random, reversed, in_order arrays selector from GUI */
/* TODO: Support command line arguments */
/* TODO: Support sound */
@@ -52,6 +45,7 @@ int main (void) {
SAV *sav = NULL;
Drw *drw = NULL;
time_t tic, toc;
+ void (*reset_array)(Arr *arr);
pthread_t p1 = 0;
status_t st;
@@ -59,12 +53,13 @@ int main (void) {
if((st = SAV_new(&sav)) != OK) goto end;
if((st = Drw_new(&drw)) != OK) goto end;
- /* assigns random values to array */
- shuffle(sav->arr);
+ reset_array = &in_order;
/* selecting the sorting algorithm */
sav->sort_algo = SELECTION_SORT;
+ reset_array(sav->arr);
+
sav->status = WELCOME;
sav->sort_status = PAUSE;
tic = time(NULL);
@@ -100,8 +95,8 @@ int main (void) {
sav->sort_status = STOP;
pthread_join(p1, NULL);
- reset_sort_stats(sav);
- shuffle(sav->arr);
+ sort_reset_stats(sav);
+ reset_array(sav->arr);
sav->status = START;
sav->sort_status = PAUSE;
diff --git a/sav.c b/sav.c
@@ -1,7 +1,7 @@
#include "sav.h"
#include "sort.h"
-void reset_sort_stats(SAV *sav) {
+void sort_reset_stats(SAV *sav) {
if(sav == NULL) return;
sav->sel = sav->cmp = ARR_MAX + 1;
@@ -42,3 +42,9 @@ void SAV_destroy(SAV *sav) {
free(sav->arr);
free(sav);
}
+
+void sort_selector(SAV *sav) {
+ if(sav->sort_algo == (ALGORITHMS_COUNT - 1))
+ sav->sort_algo = 0;
+ else sav->sort_algo++;
+}
diff --git a/sav.h b/sav.h
@@ -34,6 +34,7 @@ typedef struct {
status_t SAV_new(SAV **sav);
void SAV_destroy(SAV *sav);
-void reset_sort_stats(SAV *sav);
+void sort_reset_stats(SAV *sav);
+void sort_selector(SAV *sav);
#endif
diff --git a/sort.c b/sort.c
@@ -104,9 +104,8 @@ void bubble_sort_improved(SAV *sav) {
if(sav == NULL) return;
sav->ti = time(NULL);
- for(i = 0; (i < sav->arr->len - 1) && (sav->sort_status != STOP) && (swap_happen != false); i++) {
- if(sort_delay(sav) == STOP) break;
- if(sort_pause(sav) == STOP) break;
+ swap_happen = false;
+ for(i = 0; (i < sav->arr->len - 1) && (sav->sort_status != STOP); i++) {
for(j = 0; j < (sav->arr->len - 1 - i); j++, sav->its++) {
sav->sel = j + 1;
sav->cmp = j;
@@ -119,6 +118,9 @@ void bubble_sort_improved(SAV *sav) {
if(sort_delay(sav) == STOP) break;
if(sort_pause(sav) == STOP) break;
}
+ if(sort_delay(sav) == STOP) break;
+ if(sort_pause(sav) == STOP) break;
+ if(swap_happen == false) break;
}
sav->tf = time(NULL);
@@ -129,8 +131,6 @@ void bubble_sort_improved(SAV *sav) {
void merge(SAV *sav, int low, int middle, int high) {
size_t n1, n2, i, j, k;
- if(sort_pause(sav) == STOP) return;
-
n1 = middle - low;
n2 = high - middle;
@@ -158,7 +158,7 @@ void merge(SAV *sav, int low, int middle, int high) {
sav->arr->v[k] = C[j++];
}
- sav->sel = (k + 1);
+ sav->sel = k;
sav->cmps += 1;
sav->its += 1;
@@ -168,15 +168,26 @@ void merge(SAV *sav, int low, int middle, int high) {
if(sort_pause(sav) == STOP) return;
}
- while(i < n1) sav->arr->v[k++] = B[i++];
- while(j < n2) sav->arr->v[k++] = C[j++];
+ while(i < n1) {
+ sav->sel = k;
+ sav->arr->v[k++] = B[i++];
+ if(sort_delay(sav) == STOP) return;
+ if(sort_delay(sav) == STOP) return;
+ if(sort_pause(sav) == STOP) return;
+ }
+ while(j < n2) {
+ sav->sel = k;
+ sav->arr->v[k++] = C[j++];
+ if(sort_delay(sav) == STOP) return;
+ if(sort_delay(sav) == STOP) return;
+ if(sort_pause(sav) == STOP) return;
+ }
}
void merge_sort(SAV *sav, int low, int high) {
int middle;
middle = ((high + low) / 2);
- sav->its += 1;
if((high - low) > 1) {
/* sort the middle low portion of the array */
@@ -271,7 +282,11 @@ void shell_sort(SAV *sav) {
}
sav->arr->v[j] = temp;
sav->swps += 1;
+ if(sort_delay(sav) == STOP) return;
+ if(sort_pause(sav) == STOP) return;
}
+ if(sort_delay(sav) == STOP) return;
+ if(sort_pause(sav) == STOP) return;
}
sav->tf = time(NULL);
@@ -289,8 +304,8 @@ void selection_sort(SAV *sav)
for (i = 0; i < sav->arr->len; i++) {
min = i;
- sav->sel = i;
for (j = i + 1; j < sav->arr->len; j++) {
+ sav->sel = j;
if (sav->arr->v[j] < sav->arr->v[min]) min = j;
sav->cmps += 1;
sav->cmp = j;
@@ -316,17 +331,18 @@ void heapify(SAV *sav, int len, int i) {
int child_left = 2 * i + 1;
int child_right = 2 * i + 2;
- sav->cmp = child_left;
+ sav->cmp = root;
sav->cmps += 1;
if((child_left < len) && (sav->arr->v[child_left] > sav->arr->v[root]))
root = child_left;
- sav->cmp = child_right;
+ sav->cmp = root;
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->cmp = root;
sav->cmps += 1;
if(root != i) {
sav->swps += 1;
