SHELL SORTING: It is also called diminishing increment sort, named after its discoverer. Shell sort algorithm provides mofo significant improvement on simple insertion sort. This method sorts separate sub-files of the original file. These subfiles contain every k elements of the original file. The value of k is called an increment or a gap. The idea behind the shell sort is a simple one We have already noted that the simple insertion sort is highly efficient on a file that is in almost sorted order. It is also important to realize that when the file size n is small an O (N²) sort is often more efficient than an O (N log N) sort.
The reason for this is that O (N2) sorts are generally quite simple to program and involve very few actions other than comparisons and replacements on each pass. An O (N log N) sort is generally quite complex and employs a large number of extra operations on each pass in order to reduce the work of subsequent passes. When n is larger (N log N). is better than (N²). However when n is small (N2) is not much larger than (N log N), a large difference in those constants often causes an O (N²) sort to be faster.
Since the first increment used by the shell sort is large the individual sub-files are quite small so the simple insertion sorts on those sub-files are fairly fast. Each sort of subfile causes the entire file to be more nearly sorted. Thus, although successive passes of the shell sort use smaller increments and therefore deal with larger sub-files those sub-files are almost sorted due to the actions of previous passes. Thus, the insertion sorts on those sub-files are also quite efficient. In this connection, it is significant to note that if a file is partially sorted using an increment k and is subsequently partially sorted using an increment j, the file remains partially sorted on the increment k. That is subsequent partial sorts do not disturb earlier ones.
The actual time requirements for a specific sort depend on the number of elements in the array increments and on their actual values. When the span equals 1 the array is almost sorted. It has been shown that the order of the shell sort can be approximated by O (n (log n) ^ 2) if an appropriate sequence of increments is used. In general, the shell sort is recommended for files having several hundred elements.
Algorithm Shell sorting in c programming.
SHELL SORT (A. N)
Here A is an array with N elements. This algorithm sorts the array A with N elements in ascending order.
1. Set SPAN = N/2 [Initializes]
2. Repeat Steps from 3 to 5 while SPAN > = 1:
3. Set I = SPAN + 1
4. Repeat Steps while 1 < = N.
(a) Set ITEM = A [I],
(b) Set J = I – SPAN.
(c) Repeat Steps while J > = 1 AND A [J] > ITEM:
(i) Set A [J + SPAN] : = A [J] [Shifting]
(ii) Set J := J – SPAN
[End of Step (c) loop.]
(d) Set A [J + SPAN] = ITEM. [Insert.]
(e) Set I:=I + 1.
[End of Step 4 loop.]
5. Set SPAN:= SPAN / 2.
[End of Step 2 loop.]
6. Return.
Shell Sorting program in c programming.
#include<stdio.h>
#include<conio.h>
#define SIZE 10
void shell_sort(int [],int);
void main()
{
int a[SIZE],i,n;
clrscr();
printf("Enter how many elements");
scanf("%d",&n);
/* Input Array */
for(i=0;i<n;i++)
{
printf("Enter element %d ", i+1);
scanf("%d",&a[i]);
}
shell_sort(a,n);
/* Outpput Array */
for(i=0;i<n;i++)
printf("%dn",a[i]);
getch();
}
void shell_sort(int a[],int n)
{
int i,j,item,span;
span = n/2;
while(span >= 1)
{
for(i=span;i<n;i++)
{
item = a[i];
/*shifting */
for(j=i-span;j>=0 && a[j] > item; j-=span)
a[j+span] = a[j];
/*insert*/
a[j+span] = item;
}
span = span / 2;
}
}Also, Read