commit 0205dc18cddcfaa5f1647773f0977e639c268aff
parent fca225c2996cfd809ee096bbe8a8cf38f4f9effb
Author: klewer-martin <martin.cachari@gmail.com>
Date: Thu, 21 Apr 2022 23:31:40 -0300
Added selection sort
Diffstat:
5 files changed, 39 insertions(+), 8 deletions(-)
diff --git a/drw.h b/drw.h
@@ -50,7 +50,8 @@ static char * const algo_sel_str[ALGORITHMS_COUNT] = {
"insertion",
"merge",
"quick",
- "shell"
+ "shell",
+ "selection"
};
static char * const sort_status_str[STATUS_MAX] = {
diff --git a/main.c b/main.c
@@ -22,7 +22,8 @@ static void (*sort_handler[ALGORITHMS_COUNT])(SAV *) = {
&insertion_sort,
&merge_sort_wrapper,
&quick_sort_wrapper,
- &shell_sort
+ &shell_sort,
+ &selection_sort
};
void *routine_wrapper(void *arg) {
diff --git a/sav.h b/sav.h
@@ -17,6 +17,7 @@ typedef enum {
MERGE_SORT,
QUICK_SORT,
SHELL_SORT,
+ SELECTION_SORT,
ALGORITHMS_COUNT
} sort_t;
diff --git a/sort.c b/sort.c
@@ -74,12 +74,9 @@ void bubble_sort(SAV *sav) {
size_t i, j;
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); 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;
@@ -91,6 +88,8 @@ void bubble_sort(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;
}
sav->tf = time(NULL);
@@ -103,7 +102,6 @@ void bubble_sort_improved(SAV *sav) {
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++) {
@@ -167,8 +165,6 @@ void merge(SAV *sav, int low, int middle, int high) {
}
void merge_sort(SAV *sav, int low, int high) {
- if(sort_pause(sav) == STOP) return;
-
int middle;
middle = ((high + low) / 2);
@@ -244,6 +240,9 @@ void quick_sort_wrapper(SAV *sav) {
void shell_sort(SAV *sav) {
int gap, i, j, temp;
+
+ if(sav == NULL) return;
+
sav->ti = time(NULL);
for (gap = ((sav->arr->len) / 2); gap > 0; gap /= 2) {
@@ -268,3 +267,31 @@ void shell_sort(SAV *sav) {
if(sav->sort_status != STOP) sav->sort_status = SORTED;
}
+
+void selection_sort(SAV *sav)
+{
+ int i, j;
+ int min;
+
+ if(sav == NULL) return;
+
+ sav->ti = time(NULL);
+
+ for (i = 0; i < sav->arr->len; i++) {
+ min = i;
+ sav->sel = i;
+ for (j = i + 1; j < sav->arr->len; j++) {
+ if (sav->arr->v[j] < sav->arr->v[min]) min = j;
+ sav->cmp = min;
+ if(sort_delay(sav) == STOP) return;
+ if(sort_pause(sav) == STOP) return;
+ }
+ sav->cmp = min;
+ if(sort_delay(sav) == STOP) return;
+ if(sort_pause(sav) == STOP) return;
+ swap(&sav->arr->v[i], &sav->arr->v[min]);
+ }
+
+ sav->tf = time(NULL);
+ if(sav->sort_status != STOP) sav->sort_status = SORTED;
+}
diff --git a/sort.h b/sort.h
@@ -24,5 +24,6 @@ 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);
+void selection_sort(SAV *sav);
#endif // __SORT_H__
