shell sort2 Algorithm
Shell sort, also known as Diminishing Increment Sort, is an efficient in-place comparison based sorting algorithm that is an extension of the insertion sort. It was invented by Donald L. Shell in 1959. The algorithm works by first arranging elements at a specific interval apart, forming a sub-array, and then sorting these sub-arrays using an insertion sort. After sorting the sub-arrays, the interval is reduced, and the process is repeated until the interval becomes one, making it a standard insertion sort. The advantage of shell sort over traditional insertion sort is that it can move elements to their correct positions much faster, as it takes advantage of the partially sorted sub-arrays.
The performance of the shell sort algorithm largely depends on the choice of the interval sequence. The original shell sort algorithm used intervals of powers of two minus one, but further research has led to the discovery of more efficient interval sequences, such as the Pratt sequence, the Hibbard sequence, and the Sedgewick sequence. By choosing a good interval sequence, the shell sort algorithm can achieve a time complexity of O(n^(3/2)) or even O(n*log(n)), making it suitable for sorting medium-sized arrays. While it may not be as efficient as more advanced sorting algorithms like merge sort or quick sort, shell sort is relatively easy to implement and requires less overhead, making it a popular choice for certain applications.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ELEMENT_NR 20000
#define ARRAY_LEN(x) (sizeof(x) / sizeof((x)[0]))
void show_data(int arr[], int len)
{
int i;
for (i = 0; i < len; i++)
printf("%3d ", arr[i]);
printf("\n");
}
void swap(int *a, int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
/**
* Optimized algorithm - takes half the time as other
**/
void shell_sort(int array[], int LEN)
{
const int gaps[] = {701, 301, 132, 57, 23, 10, 4, 1};
const int gap_len = 8;
int i, j, g;
for (g = 0; g < gap_len; g++)
{
int gap = gaps[g];
for (i = gap; i < LEN; i++)
{
int tmp = array[i];
for (j = i; j >= gap && (array[j - gap] - tmp) > 0; j -= gap)
array[j] = array[j - gap];
array[j] = tmp;
}
}
#ifdef DEBUG
for (i = 0; i < LEN; i++)
printf("%s\t", data[i]);
#endif
}
int main(int argc, char *argv[])
{
int i;
int array[ELEMENT_NR];
int range = 500;
int size;
double time_spent;
srand(time(NULL));
for (i = 0; i < ELEMENT_NR; i++)
array[i] = rand() % range + 1;
size = ARRAY_LEN(array);
show_data(array, size);
clock_t t1 = clock();
shell_sort(array, size);
clock_t t2 = clock();
printf("Data Sorted\n");
show_data(array, size);
printf("Time spent sorting: %.4g s\n", (t2 - t1) / CLOCKS_PER_SEC);
return 0;
}
