implement shell sort

1 files changed, 19 insertions, 4 deletions

diff --git a/sorts.c b/sorts.c
index f4bb9b3..a03dd68 100644
--- a/sorts.c
+++ b/sorts.c
@@ -11,8 +11,8 @@
 #include <string.h>
 #include <time.h>
 #include <assert.h>
-#define ARR_SIZE 20
-#define ARR_RANGE 10
+#define ARR_SIZE 50
+#define ARR_RANGE 13
 #define ELEM_LINE 10
 #define FNAME "sort.txt"
 #undef PRINT_FILE
@@ -28,6 +28,21 @@ void prnt_arr(int *, int);
 int *mk_rand_arr(int, int);
 void mergesort(int *, int, int);
 void merge(int *, int, int, int);
+void shell_sort(int *, int);
+
+void shell_sort(int *v, int n)
+{
+    int gap, i, j, temp;
+
+    for (gap = n/2; gap > 0; gap /= 2)
+        for (i = gap; i < n; i++)
+            for (j = i-gap; j >= 0 && v[j] > v[j+gap]; j -= gap)
+            {
+                temp = v[j];
+                v[j] = v[j+gap];
+                v[j+gap] = temp;
+            }
+}
 
 /* merge sort, divide and conquer */
 void mergesort(int a[], int low, int high)
@@ -166,7 +181,6 @@ int *mk_rand_arr(int elem, int range)
     return arr;
 }
 
-
 int main(int argc, char **argv)
 {
     srand( (unsigned int ) time(NULL) );
@@ -191,7 +205,8 @@ int main(int argc, char **argv)
     //bubble_sort(arr, ARR_SIZE);
     //select_sort(arr, ARR_SIZE);
     //insrt_sort(arr, ARR_SIZE);
-    mergesort(arr, 0, ARR_SIZE - 1);
+    //mergesort(arr, 0, ARR_SIZE - 1);
+    shell_sort(arr, ARR_SIZE);
 
 #ifdef PRINT_FILE
     fprintf(out, "sorted:\n");