commit aa3cbca535242d02d73d795e23eb5a1e675e3372
parent 04b1eef81c8358648bea2c5b6ca01f5643471e0d
Author: klewer-martin <martin.cachari@gmail.com>
Date: Mon, 25 Apr 2022 00:08:25 -0300
Added reversed and in_order array functions plus other fixes
Two functions added to array module, reversed() and in_order() which as
its name suggest makes the array being reversed or in order as opposed
to shuffle which was the previous and unique method
Other fixes has been done mostly on sort module like adding delays to
reduce the differences in sorting time between different algorithms
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;
