How to write a C Program For ShellSort Using C Programming Language ?
Shell sort is a sorting algorithm, devised by Donald Shell in 1959, that is a generalization of insertionsort, which exploits the fact that insertion sort works efficiently on input that is already almost sorted. It improves on insertion sort by allowing the comparison and exchange of elements that are far apart.
The last step of Shell sort is a plain insertion sort, but by then, the array of data is guaranteed to be
almost sorted.
See More : Shellsort
-------------------------------
SHELL SORT ALGORITHM
-------------------------------input: an array num of length n with array elements numbered 0 to n - 1
Shell.Sort(num,n,key)
1. Assign, span = int(n/2)
2. while span > 0 do:
a) for i from span to n - 1, Repeat step b,c,e
b) assign num[i] to key and i to j
c) while j = span and num[j - span] > key, Repeat step d
d) swap num[j] and num[j - span]
e) Assign, span = int(span / 2.2)
3. Use Insertion Sort to sort remaining array of data
----------------------------------------------------------------------------
The following is an implementation of Shell sort written in pseudocode.
The increment sequence is a geometric sequence in which every term is
roughly 2.2 times smaller than the previous one:
---------------------
SHELL SORT PSEUDOCODE
---------------------span = int(n/2)
while span > 0 do:
for i = span .. n - 1 do:
key = num[i]
j = i
while j = span and num[j - span] > key do:
num[j] = num[j - span]
j = j - span
num[j] = key
span = int(span / 2.2)
****************************************************************************/
#include "iostream.h"
#include "conio.h"
void insertionSort(int num[],int N)
{
int i,j,key;
for(j = 1;j < N;j++) //From Second Element to Last
{
key = num[j]; //Assign num[j] to key
i = j - 1;
while(i >= 0 && num[i] > key)
{
//Swap two elements
num[i + 1] = num[i];
i--;
num[i + 1] = key;
}
}
}
int main()
{
int num[50],N,i,j,span,key;
cout << "How many numbers? " ;
cin >> N;
cout << "\nEnter " << N << " Numbers\n";
for(i = 0;i < N;i++)
cin >> num[i];
span = int(N/2);
while(span > 0)
{
for(i = span;i < N;i += span)
{
key = num[i];
j = i;
while(j >= span && num[j - span] > key)
{
num[j] = num[j - span];
j = j - span;
}
num[j] = key;
}
span = int(span/2.2);
}
//Now, the array of data is almost sorted
//So, using Insertion Sort as last step
insertionSort(num,N);
cout << endl;
for(int i = 0;i < N;i++)
cout << num[i] << ' ';
getch();
return 0;
}
OUTPUT of C Program Shell Sort :
How many numbers? 10
Enter 10 Numbers
25 65 47 88 64 10 -98 0 35 6
-98 0 6 10 25 35 47 64 65 88