Algorithms - Shell Sort

Shell sort is a sorting algorithm, devised by Donald Shell in 1959, that is a generalization of insertion sort, 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. In other words, it improves upon bubble sort and insertion sort by moving out of order elements more than one position at a time. The last step of Shell sort is a plain insertion sort, but by then, the array of data is guaranteed to be almost sorted.

C++ code

#include <iostream>
#include <iomanip>
using namespace std;

void print(int ar[], int sz, int step)
{	
	for(int i = 0; i < sz; ++i) { 
		if(((i + 1) % step) != 0)
			cout << setw(3) << ar[i]; 
		else
			cout << setw(3) << ar[i] << endl;

	}
	cout << endl;
}

void ShellSort(int a[], int sz)
{
	int i, j;
	int step, temp;
	step = sz / 2 ;
	while(step) {
		print(a, sz, step);
		cout << "==>" << endl;
		for (i = step; i < sz; i++) {
			temp = a[i];
			j = i;
			while (j >= step && a[j - step] > temp) {
				a[j] = a[j - step];
				j = j - step;
			}
			a[j] = temp;
		}
		print(a, sz, step);
		cout << "current array" << endl;
		print(a, sz, sz);
		cout << "----------------" << endl;

		step = step / 2.2;
	}
}

int main(void)
{	
	int a[] = {13, 14, 94, 33, 82, 25, 59, 94, 65, 23, 45, 27, 73, 25, 39, 10};
	const size_t sz = sizeof(a)/sizeof(a[0]);

	cout << "Initial array" << endl;
	print(a,sz,sz);
	cout << "-------------" << endl;

	ShellSort(a,sz); 

	cout << "Sorted array"  << endl;
	print(a,sz,sz); 
	return 0;
}

The implementation can be described as arranging the data sequence in a two-dimensional array and then sorting the columns of the array using insertion sort.

Output is:

Initial array
 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10

-------------
 13 14 94 33 82 25 59 94
 65 23 45 27 73 25 39 10

==>
 13 14 45 27 73 25 39 10
 65 23 94 33 82 25 59 94

current array
 13 14 45 27 73 25 39 10 65 23 94 33 82 25 59 94

----------------
 13 14 45
 27 73 25
 39 10 65
 23 94 33
 82 25 59
 94
==>
 13 10 25
 23 14 33
 27 25 45
 39 73 59
 82 94 65
 94
current array
 13 10 25 23 14 33 27 25 45 39 73 59 82 94 65 94

----------------
 13
 10
 25
 23
 14
 33
 27
 25
 45
 39
 73
 59
 82
 94
 65
 94

==>
 10
 13
 14
 23
 25
 25
 27
 33
 39
 45
 59
 65
 73
 82
 94
 94

current array
 10 13 14 23 25 25 27 33 39 45 59 65 73 82 94 94

----------------
Sorted array
 10 13 14 23 25 25 27 33 39 45 59 65 73 82 94 94

Shell sort groups with step elements together.
So, if step = 8 as in this example, we have two rows of data with 8 columns.

Initial array
 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10

 13 14 94 33 82 25 59 94
 65 23 45 27 73 25 39 10

Then, sort each column.

 13 14 45 27 73 25 39 10
 65 23 94 33 82 25 59 94

After that, it gathers the elements starting from the top row.
Then, we have the following array.

13 14 45 27 73 25 39 10 65 23 94 33 82 25 59 94

Repeat this process with different steps. The step sequence is a geometric sequence in which every term is roughly 2.2 times smaller than the previous one.

Although this method is inefficient for large data sets, it is one of the fastest algorithms for sorting small numbers of elements (sets with less than 1000 or so elements). Another advantage of this algorithm is that it requires relatively small amounts of memory.