commit f03fe5bfb0a51004e1819ff0953b5ba3e2cd6862
parent aa7fd7837533098d0d27a9c20db902efb4cbf033
Author: klewer-martin <martin.cachari@gmail.com>
Date: Wed, 6 Apr 2022 00:04:49 -0300
Added bubble sort algorithm plus iterations counter
Also comparisons counter fixed since it was counting iterations
on previous builds.
Diffstat:
5 files changed, 36 insertions(+), 8 deletions(-)
diff --git a/drw.c b/drw.c
@@ -63,12 +63,13 @@ drw_status_bar(Drw *drw, SAV *sav) {
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) C: %ld, S: %ld", sav->cmps, sav->swps);
+ sprintf(status_text, "SORTING (insertion sort) L: %ld, C: %ld, S: %ld, I: %ld",
+ 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, "(insertion sort) done in %.2fs, C: %ld, S: %ld",
+ sprintf(status_text, "SORTED (insertion sort) done in %.2fs, L: %ld, C: %ld, S: %ld, I: %ld",
(double)(sav->tf - sav->ti) / CLOCKS_PER_SEC,
- sav->cmps, sav->swps);
+ sav->arr->len, sav->cmps, sav->swps, sav->its);
drw_text(drw, status_text, 0, drw->h - drw->font_size - 5);
}
diff --git a/sav.c b/sav.c
@@ -18,7 +18,7 @@ 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 = 0;
+ (*sav)->sel = (*sav)->cmp = (*sav)->cmps = (*sav)->swps = (*sav)->its = 0;
(*sav)->status = RUN;
if(((*sav)->arr = (Arr *)malloc(sizeof(Arr))) == NULL)
@@ -46,6 +46,7 @@ routine_wrapper(void *arg) {
SAV *sav = (SAV *)arg;
insertion_sort(sav);
+ /* bubble_sort(sav); */
return NULL;
}
@@ -72,7 +73,7 @@ main (void) {
/* start sorting thread */
pthread_create(&p1, NULL, &routine_wrapper, (void *)sav);
-/* main loop */
+ /* main loop */
while(sav->status != STOP) {
check_events(&(sav->status));
if(sav->status == UPDATE) {
diff --git a/sav.h b/sav.h
@@ -8,7 +8,7 @@
typedef struct {
Arr *arr;
- size_t sel, cmp, cmps, swps;
+ size_t sel, cmp, cmps, swps, its;
clock_t ti, tf;
status_t status;
} SAV;
diff --git a/sort.c b/sort.c
@@ -10,7 +10,7 @@ insertion_sort(SAV *sav) {
size_t i, j;
sav->ti = clock();
- for(i = 1; i < sav->arr->len; i++) {
+ for(i = 1; i < sav->arr->len; i++, sav->its++) {
sav->cmps += 1;
key = sav->arr->v[i];
j = i - 1;
@@ -21,6 +21,7 @@ insertion_sort(SAV *sav) {
sav->sel = i;
sav->cmp = j;
+ sav->its++;
/* wait 'til main thread updates graphics */
wait_main_thread(&(sav->status));
@@ -40,3 +41,28 @@ insertion_sort(SAV *sav) {
if(sav->status != STOP) sav->status = SORTED;
}
+
+void bubble_sort(SAV *sav) {
+ size_t i, j;
+
+ sav->ti = clock();
+ for(i = 0; i < sav->arr->len - 1; i++, sav->its++) {
+ 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;
+ }
+
+ /* wait 'til main thread updates graphics */
+ wait_main_thread(&(sav->status));
+ if(sav->status == STOP) break;
+ }
+ wait_main_thread(&(sav->status));
+ if(sav->status == STOP) break;
+ }
+ sav->tf = clock();
+ if(sav->status != STOP) sav->status = SORTED;
+}
diff --git a/sort.h b/sort.h
@@ -7,7 +7,7 @@
#include "sav.h"
#include "util.h"
-int bubble_sort(SAV *);
+void bubble_sort(SAV *);
void insertion_sort(SAV *);
#endif // __SORT_H__
