sav

Index Commits Files Refs README LICENSE

commit 549e5938aff5b91788e96a233138b0936017c19f
parent b52c5cc0093bf97ebdc0967483d70f7c18d8ac1e
Author: klewer-martin <martin.cachari@gmail.com>
Date:   Tue, 19 Apr 2022 00:07:05 -0300

Added shellsort and bubblesort improved

One new algorithms added, shell short, and also an improved version of
bubble sort wich improves if the array is sorted (still sucks)

Diffstat:
M
drw.c
 | 
6
+++++-
M
main.c
 | 
10
++++++++--
M
sav.h
 | 
2
++
M
sort.c
 | 
54
++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
sort.h
 | 
3
+++

5 files changed, 72 insertions(+), 3 deletions(-)
diff --git a/drw.c b/drw.c
@@ -1,11 +1,15 @@
 #include "drw.h"
 
+#include <assert.h>
+
 static SDL_Rect rect;
 static const char *algo_sel_str[ALGORITHMS_COUNT] = {
     "bubble",
+    "improved bubble",
     "insertion",
     "merge",
-    "quick"
+    "quick",
+    "shell"
 };
 
 static const char *sort_status_str[STATUS_MAX] = {
diff --git a/main.c b/main.c
@@ -17,9 +17,11 @@ void *routine_wrapper(void *);
 
 static void (*sort_handler[ALGORITHMS_COUNT])(SAV *) = {
     &bubble_sort,
+    &bubble_sort_improved,
     &insertion_sort,
     &merge_sort_wrapper,
-    &quick_sort_wrapper
+    &quick_sort_wrapper,
+    &shell_sort
 };
 
 void *routine_wrapper(void *arg) {
@@ -52,7 +54,7 @@ int main (void) {
     shuffle(sav->arr);
 
     /* selecting the sorting algorithm */
-    sav->sort_algo = INSERTION_SORT;
+    sav->sort_algo = SHELL_SORT;
 
     sav->status = WELCOME;
     sav->sort_status = PAUSE;
@@ -96,6 +98,10 @@ int main (void) {
             /* let's start the sorting thread */
             pthread_create(&p1, NULL, &routine_wrapper, (void *)sav);
         }
+
+        if(sav->sort_status == SORTED) {
+            sav->sel = sav->cmp = ARR_LEN + 1;
+        }
     }
 
     end:
diff --git a/sav.h b/sav.h
@@ -12,9 +12,11 @@
 
 typedef enum {
     BUBBLE_SORT,
+    BUBBLE_SORT_IMPROVED,
     INSERTION_SORT,
     MERGE_SORT,
     QUICK_SORT,
+    SHELL_SORT,
     ALGORITHMS_COUNT
 } sort_t;
 
diff --git a/sort.c b/sort.c
@@ -101,6 +101,36 @@ void bubble_sort(SAV *sav) {
     sav->sel = sav->cmp = ARR_MAX + 1;
 }
 
+void bubble_sort_improved(SAV *sav) {
+    size_t i, j;
+    bool swap_happen;
+
+    if(sav == NULL) return;
+    if(sort_pause(sav) == STOP) 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;
+        for(j = 0; j < (sav->arr->len - 1 - i); j++, sav->its++) {
+            sav->sel = j + 1;
+            sav->cmp = j;
+            sav->cmps += 1;
+            if(sav->arr->v[j] - sav->arr->v[j + 1] > 0) {
+                swap(sav->arr->v + j, sav->arr->v+j+1);
+                sav->swps += 1;
+                swap_happen = true;
+            }
+            if(sort_delay(sav) == STOP) break;
+            if(sort_pause(sav) == STOP) break;
+        }
+    }
+
+    sav->tf = time(NULL);
+    if(sav->status != STOP) sav->sort_status = SORTED;
+    sav->sel = sav->cmp = ARR_MAX + 1;
+}
+
 void merge(SAV *sav, int low, int middle, int high) {
     size_t n1, n2, i, j, k;
 
@@ -213,3 +243,27 @@ void quick_sort_wrapper(SAV *sav) {
     sav->sel = sav->cmp = ARR_MAX + 1;
     sav->tf = time(NULL);
 }
+
+void shell_sort(SAV *sav) {
+    int gap, i, j, temp;
+    for (gap = ((sav->arr->len) / 2); gap > 0; gap /= 2) {
+        sav->cmps += 1;
+        for (i = gap; i < sav->arr->len; i += 1) {
+            temp = sav->arr->v[i];
+            sav->sel = i;
+            for (j = i; j >= gap && sav->arr->v[j - gap] > temp; j -= gap) {
+                sav->arr->v[j] = sav->arr->v[j - gap];
+                sav->cmp = j - gap;
+                sav->cmps += 1;
+
+                if(sort_delay(sav) == STOP) return;
+                if(sort_delay(sav) == STOP) return;
+                if(sort_pause(sav) == STOP) return;
+            }
+            sav->arr->v[j] = temp;
+            sav->swps += 1;
+            sav->cmps += 1;
+        }
+    }
+    if(sav->sort_status != STOP) sav->sort_status = SORTED;
+}
diff --git a/sort.h b/sort.h
@@ -12,6 +12,7 @@
 void set_sort_speed(SAV *sav, size_t new_value);
 
 void bubble_sort(SAV *);
+void bubble_sort_improved(SAV *);
 void insertion_sort(SAV *);
 
 void merge(SAV *, int, int, int);
@@ -22,4 +23,6 @@ void quick_sort_wrapper(SAV *sav);
 void quick_sort(SAV *sav, int low, int high);
 void quick_sort_partition(SAV *sav, int low, int *middle, int high);
 
+void shell_sort(SAV *sav);
+
 #endif // __SORT_H__