sort.c - sav - Sorting Algorithms Visualized

sort.c (9205B)
Line numbers
   1 #include <stdio.h>
   2 #include <stdbool.h>
   3 #include <time.h>
   4 #include <SDL2/SDL.h>
   5 
   6 #include "sort.h"
   7 
   8 static void (*sort_handler[])(SAV *) = {
   9     /* &bubble_sort, */
  10     &bubble_sort_improved,
  11     &insertion_sort,
  12     &merge_sort_wrapper,
  13     &quick_sort_wrapper,
  14     &shell_sort,
  15     &selection_sort,
  16     &heap_sort
  17 };
  18 
  19 /* pthread_create compliant start routine */
  20 void *start_sorting(void *arg) {
  21     SAV *sav = (SAV *)arg;
  22 
  23     assert((sav->sort_algo != ALGORITHMS_COUNT) && "Default sorting algorithm not set");
  24 
  25     sort_handler[sav->sort_algo](sav);
  26 
  27     return NULL;
  28 }
  29 
  30 void set_sort_speed(SAV *sav, size_t new_value) {
  31     if(sav == NULL) return;
  32 
  33     if((new_value > 0) && (new_value <= SAV_SORT_DELAY_MAX)) {
  34         printf("INFO: Updating sort_delay to: %ld\n", new_value);
  35         sav->sort_delay = new_value;
  36     }
  37 }
  38 
  39 status_t sort_delay(const SAV *sav) {
  40     size_t i;
  41 
  42     for(i = 0; i < sav->sort_delay; i++, SDL_Delay(1))
  43         if((sav->sort_status == STOP) || (sav->status == STOP))
  44             return STOP;
  45 
  46     return OK;
  47 }
  48 
  49 status_t sort_pause(const SAV *sav) {
  50     while(sav->sort_status == PAUSE)
  51         if(sort_delay(sav) == STOP) return STOP;
  52 
  53     return sav->sort_status == STOP ? STOP : OK;
  54 }
  55 
  56 void insertion_sort(SAV *sav) {
  57     int key;
  58     size_t i, j;
  59 
  60     if(sav == NULL) return;
  61     if(sort_pause(sav) == STOP) return;
  62 
  63     sav->ti = time(NULL);
  64 
  65     for(i = 1; (i < sav->arr->len) && (sav->sort_status != STOP); i++) {
  66         if(sort_delay(sav) == STOP) break;
  67         if(sort_pause(sav) == STOP) break;
  68 
  69         sav->cmps += 1;
  70         key = sav->arr->v[i];
  71         j = i - 1;
  72         while((j >= 0) && (sav->arr->v[j] > key)) {
  73             sav->cmps += 1;
  74             sav->arr->v[j + 1] = sav->arr->v[j];
  75             j--;
  76 
  77             sav->sel = i;
  78             sav->cmp = j + 1;
  79             sav->its++;
  80 
  81             if(sort_delay(sav) == STOP) break;
  82             if(sort_pause(sav) == STOP) break;
  83         }
  84         sav->arr->v[j + 1] = key;
  85         sav->sel = i;
  86         sav->cmp = j + 1;
  87         sav->swps += 1;
  88     }
  89 
  90     sav->tf = time(NULL);
  91 
  92     if(sav->sort_status != STOP) sav->sort_status = SORTED;
  93     sav->sel = sav->cmp = ARR_MAX + 1;
  94 }
  95 
  96 void bubble_sort(SAV *sav) {
  97     size_t i, j;
  98 
  99     if(sav == NULL) return;
 100 
 101     sav->ti = time(NULL);
 102     for(i = 0; (i < sav->arr->len - 1) && (sav->sort_status != STOP); i++) {
 103         for(j = 0; j < (sav->arr->len - 1 - i); j++, sav->its++) {
 104             sav->sel = j + 1;
 105             sav->cmp = j;
 106             sav->cmps += 1;
 107             if(sav->arr->v[j] - sav->arr->v[j + 1] > 0) {
 108                 swap(sav->arr->v + j, sav->arr->v+j+1);
 109                 sav->swps += 1;
 110             }
 111             if(sort_delay(sav) == STOP) break;
 112             if(sort_pause(sav) == STOP) break;
 113         }
 114         if(sort_delay(sav) == STOP) break;
 115         if(sort_pause(sav) == STOP) break;
 116     }
 117 
 118     sav->tf = time(NULL);
 119     if(sav->status != STOP) sav->sort_status = SORTED;
 120     sav->sel = sav->cmp = ARR_MAX + 1;
 121 }
 122 
 123 void bubble_sort_improved(SAV *sav) {
 124     size_t i, j;
 125     bool swap_happen;
 126 
 127     if(sav == NULL) return;
 128 
 129     sav->ti = time(NULL);
 130     swap_happen = false;
 131     for(i = 0; (i < sav->arr->len - 1) && (sav->sort_status != STOP); i++) {
 132         for(j = 0; j < (sav->arr->len - 1 - i); j++, sav->its++) {
 133             sav->sel = j + 1;
 134             sav->cmp = j;
 135             sav->cmps += 1;
 136             if(sav->arr->v[j] - sav->arr->v[j + 1] > 0) {
 137                 swap(sav->arr->v + j, sav->arr->v+j+1);
 138                 sav->swps += 1;
 139                 swap_happen = true;
 140             }
 141             if(sort_delay(sav) == STOP) break;
 142             if(sort_pause(sav) == STOP) break;
 143         }
 144         if(sort_delay(sav) == STOP) break;
 145         if(sort_pause(sav) == STOP) break;
 146         if(swap_happen == false) break;
 147     }
 148 
 149     sav->tf = time(NULL);
 150     if(sav->status != STOP) sav->sort_status = SORTED;
 151     sav->sel = sav->cmp = ARR_MAX + 1;
 152 }
 153 
 154 void merge(SAV *sav, int low, int middle, int high) {
 155     size_t n1, n2, i, j, k;
 156 
 157     n1 = middle - low;
 158     n2 = high - middle;
 159 
 160     int B[n1], C[n2];
 161 
 162     sav->B_used += n1;
 163     sav->B_used += n2;
 164 
 165     /* B holds middle low array */
 166     for(i = low, j = 0; i < middle; i++, j++)
 167         B[j] = sav->arr->v[i];
 168 
 169     /* C middle high */
 170     for(i = middle, j = 0; i < high; i++, j++)
 171         C[j] = sav->arr->v[i];
 172 
 173     /* merge B and C in order */
 174     for(k = low, i = j = 0; (k < high) && (i < n1) && (j < n2); k++) {
 175         sav->cmp = middle + j;
 176         if(B[i] <= C[j]) {
 177             sav->arr->v[k] = B[i++];
 178             sav->cmps += 1;
 179         }
 180         else {
 181             sav->cmps += 1;
 182             sav->arr->v[k] = C[j++];
 183         }
 184 
 185         sav->sel = k;
 186         sav->cmps += 1;
 187         sav->its += 1;
 188 
 189         /* double delay; to match speed of other algorithms */
 190         if(sort_delay(sav) == STOP) return;
 191         if(sort_delay(sav) == STOP) return;
 192         if(sort_pause(sav) == STOP) return;
 193     }
 194 
 195     while(i < n1) {
 196         sav->sel = k;
 197         sav->arr->v[k++] = B[i++];
 198         if(sort_delay(sav) == STOP) return;
 199         if(sort_delay(sav) == STOP) return;
 200         if(sort_pause(sav) == STOP) return;
 201     }
 202     while(j < n2) {
 203         sav->sel = k;
 204         sav->arr->v[k++] = C[j++];
 205         if(sort_delay(sav) == STOP) return;
 206         if(sort_delay(sav) == STOP) return;
 207         if(sort_pause(sav) == STOP) return;
 208     }
 209 }
 210 
 211 void merge_sort(SAV *sav, int low, int high) {
 212     int middle;
 213 
 214     middle = ((high + low) / 2);
 215 
 216     if((high - low) > 1) {
 217         /* sort the middle low portion of the array */
 218         merge_sort(sav, low, middle);
 219 
 220         /* sort the middle high portion of the array */
 221         merge_sort(sav, middle, high);
 222 
 223         /* merge both arrays ordered */
 224         merge(sav, low, middle, high);
 225 
 226         sav->cmps += 1;
 227     }
 228 }
 229 
 230 void merge_sort_wrapper(SAV *sav) {
 231     if(sav == NULL) return;
 232 
 233     sav->ti = time(NULL);
 234     merge_sort(sav, 0, sav->arr->len);
 235     sav->tf = time(NULL);
 236 
 237     sav->sel = sav->arr->len + 1;
 238     if(sav->status != STOP) sav->sort_status = SORTED;
 239     sav->sel = sav->cmp = ARR_MAX + 1;
 240 }
 241 
 242 void quick_sort_partition(SAV *sav, int low, int *middle, int high) {
 243     int i, j, pivot;
 244 
 245     pivot = high;
 246     sav->sel = pivot;
 247 
 248     for(i = j = low; j < high; j++, sav->cmps += 1) {
 249         if(sav->arr->v[j] < sav->arr->v[pivot]) {
 250             swap(&(sav->arr->v[i++]), &(sav->arr->v[j]));
 251             sav->swps += 1;
 252         }
 253         sav->cmp = j;
 254 
 255         if(sort_delay(sav) == STOP) return;
 256         if(sort_delay(sav) == STOP) return;
 257         if(sort_pause(sav) == STOP) return;
 258     }
 259 
 260     swap(&(sav->arr->v[i]), &(sav->arr->v[pivot]));
 261     sav->swps += 1;
 262     *middle = i;
 263 }
 264 
 265 void quick_sort(SAV *sav, int low, int high) {
 266     int pivot;
 267 
 268     if(sort_pause(sav) == STOP) return;
 269 
 270     if ((high - low) > 0) {
 271         quick_sort_partition(sav, low, &pivot, high);
 272         quick_sort(sav, low, pivot - 1);
 273         quick_sort(sav, pivot + 1, high);
 274     }
 275 }
 276 
 277 void quick_sort_wrapper(SAV *sav) {
 278     if(sav == NULL) return;
 279 
 280     sav->ti = time(NULL);
 281     quick_sort(sav, 0, sav->arr->len - 1);
 282     if(sav->sort_status != STOP) sav->sort_status = SORTED;
 283     sav->sel = sav->cmp = ARR_MAX + 1;
 284     sav->tf = time(NULL);
 285 }
 286 
 287 void shell_sort(SAV *sav) {
 288     int gap, i, j, temp;
 289 
 290     if(sav == NULL) return;
 291 
 292     sav->ti = time(NULL);
 293 
 294     for (gap = ((sav->arr->len) / 2); gap > 0; gap /= 2) {
 295         sav->cmps += 1;
 296         for (i = gap; i < sav->arr->len; i += 1) {
 297             temp = sav->arr->v[i];
 298             sav->sel = i;
 299             for (j = i; j >= gap && sav->arr->v[j - gap] > temp; j -= gap) {
 300                 sav->arr->v[j] = sav->arr->v[j - gap];
 301                 sav->cmp = j - gap;
 302                 sav->cmps += 1;
 303 
 304                 if(sort_delay(sav) == STOP) return;
 305                 if(sort_pause(sav) == STOP) return;
 306             }
 307             sav->arr->v[j] = temp;
 308             sav->swps += 1;
 309             if(sort_delay(sav) == STOP) return;
 310             if(sort_pause(sav) == STOP) return;
 311         }
 312         if(sort_delay(sav) == STOP) return;
 313         if(sort_pause(sav) == STOP) return;
 314     }
 315     sav->tf = time(NULL);
 316 
 317     if(sav->sort_status != STOP) sav->sort_status = SORTED;
 318 }
 319 
 320 void selection_sort(SAV *sav)
 321 {
 322     int i, j;
 323     int min;
 324 
 325     if(sav == NULL) return;
 326 
 327     sav->ti = time(NULL);
 328 
 329     for (i = 0; i < sav->arr->len; i++) {
 330         min = i;
 331         for (j = i + 1; j < sav->arr->len; j++) {
 332             sav->sel = j;
 333             if (sav->arr->v[j] < sav->arr->v[min]) {
 334                 min = j;
 335                 sav->cmp = min;
 336             }
 337             sav->cmps += 1;
 338             if(sort_delay(sav) == STOP) return;
 339             if(sort_pause(sav) == STOP) return;
 340         }
 341         sav->cmp = min;
 342         if(sort_delay(sav) == STOP) return;
 343         if(sort_pause(sav) == STOP) return;
 344         swap(&sav->arr->v[i], &sav->arr->v[min]);
 345         sav->swps += 1;
 346     }
 347 
 348     sav->tf = time(NULL);
 349     if(sav->sort_status != STOP) sav->sort_status = SORTED;
 350 }
 351 
 352 
 353 /* build max_heap */
 354 void heapify(SAV *sav, int len, int i) {
 355     /* Find largest among root, left child and right child */
 356     int root = i;
 357     int child_left = 2 * i + 1;
 358     int child_right = 2 * i + 2;
 359 
 360     sav->cmp = root;
 361     sav->cmps += 1;
 362     if((child_left < len) && (sav->arr->v[child_left] > sav->arr->v[root]))
 363         root = child_left;
 364 
 365     sav->cmp = root;
 366     sav->cmps += 1;
 367     if((child_right < len) && (sav->arr->v[child_right] > sav->arr->v[root]))
 368         root = child_right;
 369 
 370     /* Swap and continue heapifying if root is not root */
 371     sav->cmp = root;
 372     sav->cmps += 1;
 373     if(root != i) {
 374         sav->swps += 1;
 375         swap(&(sav->arr->v[i]), &sav->arr->v[root]);
 376         heapify(sav, len, root);
 377     }
 378 
 379     if(sort_delay(sav) == STOP) return;
 380     if(sort_pause(sav) == STOP) return;
 381 }
 382 
 383 /* Main function to do heap sort */
 384 void heap_sort(SAV *sav) {
 385     int i;
 386     if(sav == NULL) return;
 387 
 388     sav->ti = time(NULL);
 389 
 390     /* Build max heap */
 391     for (i = ((sav->arr->len / 2) - 1); i >= 0; i--)
 392         heapify(sav, sav->arr->len, i);
 393 
 394     /* Heap sort */
 395     for (i = (sav->arr->len - 1); i >= 0; i--) {
 396         /* The root element gets swapped with the last one, then gets ignored */
 397         sav->sel = i;
 398 
 399         sav->swps += 1;
 400         swap(&sav->arr->v[0], &sav->arr->v[i]);
 401 
 402         if(sort_delay(sav) == STOP) return;
 403         if(sort_pause(sav) == STOP) return;
 404 
 405         /* Heapify root element to get highest element at root again */
 406         heapify(sav, i, 0);
 407     }
 408 
 409     if(sav->sort_status != STOP) sav->sort_status = SORTED;
 410     sav->sel = sav->cmp = ARR_MAX + 1;
 411     sav->tf = time(NULL);
 412 }