Shell sort works by comparing distant elements before processing neighboring elements. And the distance used for comparison keeps decreases for each pass.
Example:
83 97 14 101 15 39 23 98 31 63
Pass 1: (Distance: 5)
Apply insertion sort to sub-array (a0, a5), (a1, a6), (a2, a7), (a3, a8), (a4, a9)
39 97 14 101 15 83 23 98 31 63 - (a0, a5)
39 23 14 101 15 83 97 98 31 63 - (a1, a6)
39 23 14 101 15 83 97 98 31 63 - (a2, a7)
39 23 14 31 15 83 97 98 101 63 - (a3, a8)
39 23 14 31 15 83 97 98 101 63 - (a4, a9)
Pass 2: (Distance: 2)
Apply insertion sort on sub-arrays (a0, a2), (a1, a3), (a0, a2, a4), (a1, a3, a5), (a0, a2, a4, a6), (a1, a3, a5, a7), (a0, a2, a3, a6, a8), (a1, a3, a5, a7, a9)
14 23 39 31 15 83 97 98 101 63 - (a0, a2)
14 23 39 31 15 83 97 98 101 63 - (a1, a3)
14 23 15 31 39 83 97 98 101 63 - (a0, a2, a4)
14 23 15 31 39 83 97 98 101 63 - (a1, a3, a5)
14 23 15 31 39 83 97 98 101 63 - (a0, a2, a4, a6)
14 23 15 31 39 83 97 98 101 63 - (a1, a3, a5, a7)
14 23 15 31 39 83 97 98 101 63 - (a0, a2, a3, a6, a8)
14 23 15 31 39 63 97 83 101 98 - (a1, a3, a5, a7, a9)
Pass 3: (Distance: 1)
Apply insertion sort on a0..a9
14 23 15 31 39 63 97 83 101 98 - inserted 23 at the right place
14 15 23 31 39 63 97 83 101 98 - inserted 15 at the right place
14 15 23 31 39 63 97 83 101 98 - inserted 31 at the right place
14 15 23 31 39 63 97 83 101 98 - inserted 39 at the right place
14 15 23 31 39 63 97 83 101 98 - inserted 63 at the right place
14 15 23 31 39 63 97 83 101 98 - inserted 97 at the right place
14 15 23 31 39 63 83 97 101 98 - inserted 83 at the right place
14 15 23 31 39 63 83 97 101 98 - inserted 101 at the right place
14 15 23 31 39 63 83 97 98 101 - inserted 98 at the right place
#include <stdio.h>
#include <stdlib.h>
void shell_sort(int *data, int n) {
int i, j, k, l, tmp;
for (i = n/2; i > 0; i = i/2) {
for (j = i; j < n; j++) {
tmp = data[j];
for (k = j; k >= i && data[k-i] > tmp; k = k-i) {
data[k] = data[k-i];
}
data[k] = tmp;
}
}
printf("Sorted data:\n");
for (l = 0; l < n; l++)
printf("%3d ", data[l]);
printf("\n");
}
int main() {
int n, i, *data;
printf("Enter the no of data:");
scanf("%d", &n);
data = (int *)malloc(sizeof (int) * n);
for (i = 0; i < n; i++)
scanf("%d", &data[i]);
shell_sort(data, n);
return 0;
}
Example:
83 97 14 101 15 39 23 98 31 63
Pass 1: (Distance: 5)
Apply insertion sort to sub-array (a0, a5), (a1, a6), (a2, a7), (a3, a8), (a4, a9)
39 97 14 101 15 83 23 98 31 63 - (a0, a5)
39 23 14 101 15 83 97 98 31 63 - (a1, a6)
39 23 14 101 15 83 97 98 31 63 - (a2, a7)
39 23 14 31 15 83 97 98 101 63 - (a3, a8)
39 23 14 31 15 83 97 98 101 63 - (a4, a9)
Pass 2: (Distance: 2)
Apply insertion sort on sub-arrays (a0, a2), (a1, a3), (a0, a2, a4), (a1, a3, a5), (a0, a2, a4, a6), (a1, a3, a5, a7), (a0, a2, a3, a6, a8), (a1, a3, a5, a7, a9)
14 23 39 31 15 83 97 98 101 63 - (a0, a2)
14 23 39 31 15 83 97 98 101 63 - (a1, a3)
14 23 15 31 39 83 97 98 101 63 - (a0, a2, a4)
14 23 15 31 39 83 97 98 101 63 - (a1, a3, a5)
14 23 15 31 39 83 97 98 101 63 - (a0, a2, a4, a6)
14 23 15 31 39 83 97 98 101 63 - (a1, a3, a5, a7)
14 23 15 31 39 83 97 98 101 63 - (a0, a2, a3, a6, a8)
14 23 15 31 39 63 97 83 101 98 - (a1, a3, a5, a7, a9)
Pass 3: (Distance: 1)
Apply insertion sort on a0..a9
14 23 15 31 39 63 97 83 101 98 - inserted 23 at the right place
14 15 23 31 39 63 97 83 101 98 - inserted 15 at the right place
14 15 23 31 39 63 97 83 101 98 - inserted 31 at the right place
14 15 23 31 39 63 97 83 101 98 - inserted 39 at the right place
14 15 23 31 39 63 97 83 101 98 - inserted 63 at the right place
14 15 23 31 39 63 97 83 101 98 - inserted 97 at the right place
14 15 23 31 39 63 83 97 101 98 - inserted 83 at the right place
14 15 23 31 39 63 83 97 101 98 - inserted 101 at the right place
14 15 23 31 39 63 83 97 98 101 - inserted 98 at the right place
See Also:
Example Program For Shell Sort:
#include <stdio.h>
#include <stdlib.h>
void shell_sort(int *data, int n) {
int i, j, k, l, tmp;
for (i = n/2; i > 0; i = i/2) {
for (j = i; j < n; j++) {
tmp = data[j];
for (k = j; k >= i && data[k-i] > tmp; k = k-i) {
data[k] = data[k-i];
}
data[k] = tmp;
}
}
printf("Sorted data:\n");
for (l = 0; l < n; l++)
printf("%3d ", data[l]);
printf("\n");
}
int main() {
int n, i, *data;
printf("Enter the no of data:");
scanf("%d", &n);
data = (int *)malloc(sizeof (int) * n);
for (i = 0; i < n; i++)
scanf("%d", &data[i]);
shell_sort(data, n);
return 0;
}
Output: (C Program To Implement Shell Sort)
jp@jp-VirtualBox:s$ ./a.out
Enter the no of data:10
83 97 14 101 15 39 23 98 31 63
Sorted data:
14 15 23 31 39 63 83 97 98 101
Enter the no of data:10
83 97 14 101 15 39 23 98 31 63
Sorted data:
14 15 23 31 39 63 83 97 98 101
No comments:
Post a Comment