| 1 | #include "utils.h" |
| 2 | #include <stdio.h> |
| 3 | void bubblesort(int a[], int n) { |
| 4 | int comparisons = 0; |
| 5 | for (int i = 0; i < n; i++) { |
| 6 | for (int j = 1; j < n - i; j++) { |
| 7 | comparisons++; |
| 8 | if (a[j - 1] > a[j]) { |
| 9 | swap(a, j, j - 1); |
| 10 | } |
| 11 | } |
| 12 | printarr(a, n); |
| 13 | printf("\n"); |
| 14 | } |
| 15 | } |
| 16 | |
| 17 | void selectionsort(int a[], int n) { |
| 18 | for (int i = 0; i < n; i++) { |
| 19 | int small = i; |
| 20 | for (int j = i; j < n; j++) { |
| 21 | if (a[j] < a[small]) { |
| 22 | small = j; |
| 23 | } |
| 24 | } |
| 25 | swap(a, i, small); |
| 26 | printarr(a, n); |
| 27 | printf("\n"); |
| 28 | } |
| 29 | } |
| 30 | |
| 31 | void insertionsort(int a[], int n) { |
| 32 | for (int i = 1; i < n; i++) { |
| 33 | int j = i; |
| 34 | while (j > 0 && a[j - 1] > a[j]) { |
| 35 | swap(a, j, j - 1); |
| 36 | j--; |
| 37 | } |
| 38 | printarr(a, n); |
| 39 | printf("\n"); |
| 40 | } |
| 41 | } |
| 42 | |
| 43 | int get_max(int a[], int n) { |
| 44 | int max = a[0]; |
| 45 | int i; |
| 46 | for (i = 1; i < n; i++) |
| 47 | if (a[i] > max) |
| 48 | max = a[i]; |
| 49 | return max; |
| 50 | } |
| 51 | void radixsort(int a[], int n) { |
| 52 | int bucket[10][10], bucket_cnt[10]; |
| 53 | int i, j, k, r, NOP = 0, divisor = 1, lar, pass; |
| 54 | lar = get_max(a, n); |
| 55 | while (lar > 0) { |
| 56 | NOP++; |
| 57 | lar /= 10; |
| 58 | } |
| 59 | for (pass = 0; pass < NOP; pass++) { |
| 60 | for (i = 0; i < 10; i++) { |
| 61 | bucket_cnt[i] = 0; |
| 62 | } |
| 63 | for (i = 0; i < n; i++) { |
| 64 | r = (a[i] / divisor) % 10; |
| 65 | bucket[r][bucket_cnt[r]] = a[i]; |
| 66 | bucket_cnt[r] += 1; |
| 67 | } |
| 68 | i = 0; |
| 69 | for (k = 0; k < 10; k++) { |
| 70 | for (j = 0; j < bucket_cnt[k]; j++) { |
| 71 | a[i] = bucket[k][j]; |
| 72 | i++; |
| 73 | } |
| 74 | } |
| 75 | divisor *= 10; |
| 76 | printarr(a, n); |
| 77 | printf("\n"); |
| 78 | } |
| 79 | } |