add radix sort

3 files changed, 43 insertions, 3 deletions

diff --git a/src/main.c b/src/main.c
index c177290..86e9db6 100644
--- a/src/main.c
+++ b/src/main.c
@@ -8,7 +8,7 @@
 const int EASY_SCORE_DECREMENT = 10;
 const int MEDIUM_SCORE_DECREMENT = 20;
 const int LOWER = 1;
-const int UPPER = 3;
+const int UPPER = 4;
 
 typedef enum Difficulty {
   Easy,
@@ -56,7 +56,9 @@ int main(int argc, char *argv[]) {
       getarr(size);
       selectionsort(list, size);
       break;
-    // case 4: radixsort(list); break;
+    case 4:
+      radixsort(list, size);
+      break;
     default:
       break;
     }
diff --git a/src/sort.c b/src/sort.c
index 6ea4b26..df8b1f5 100644
--- a/src/sort.c
+++ b/src/sort.c
@@ -39,3 +39,41 @@ void insertionsort(int a[], int n) {
     printf("\n");
   }
 }
+
+int get_max(int a[], int n) {
+  int max = a[0];
+  int i;
+  for (i = 1; i < n; i++)
+    if (a[i] > max)
+      max = a[i];
+  return max;
+}
+void radixsort(int a[], int n) {
+  int bucket[10][10], bucket_cnt[10];
+  int i, j, k, r, NOP = 0, divisor = 1, lar, pass;
+  lar = get_max(a, n);
+  while (lar > 0) {
+    NOP++;
+    lar /= 10;
+  }
+  for (pass = 0; pass < NOP; pass++) {
+    for (i = 0; i < 10; i++) {
+      bucket_cnt[i] = 0;
+    }
+    for (i = 0; i < n; i++) {
+      r = (a[i] / divisor) % 10;
+      bucket[r][bucket_cnt[r]] = a[i];
+      bucket_cnt[r] += 1;
+    }
+    i = 0;
+    for (k = 0; k < 10; k++) {
+      for (j = 0; j < bucket_cnt[k]; j++) {
+        a[i] = bucket[k][j];
+        i++;
+      }
+    }
+    divisor *= 10;
+    printarr(a, n);
+    printf("\n");
+  }
+}
diff --git a/src/sort.h b/src/sort.h
index f1ea550..0a64588 100644
--- a/src/sort.h
+++ b/src/sort.h
@@ -4,4 +4,4 @@
 void bubblesort(int a[], int n);
 void selectionsort(int a[], int n);
 void insertionsort(int a[], int n);
-void radixsort(int a[]);
+void radixsort(int a[], int n);