add radix sort

1 files changed, 38 insertions, 0 deletions

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");
+  }
+}