From bf301724bcda4f53bfe315c19b09951e59bed7e4 Mon Sep 17 00:00:00 2001 From: Kyle K Date: Sat, 20 Nov 2010 16:38:34 -0600 Subject: implement shell sort --- sorts.c | 23 +++++++++++++++++++---- 1 file 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 #include #include -#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"); -- cgit v1.2.3