## Wednesday, November 18, 2009

### Art of computer programming -Sorting #3

Shell sort
For any sorting algorithm that moves only one position at a time , then the running time will always be proportional to n^2. Hence the idea was struck to make larger leaps rather than small ones. The small leaps is one of the prime reasons for insertion sort's low efficiency. And Donald Shell proposed shell sort.
Now you will be wondering how to choose he leap/step size. In shell sort we can start with an arbitrary step size in the first pass, after every pass the step size decreases. Hence shell sort is also known as decreasing increment sort. We'll take an example. In the first pass, let the step size be 8.
So during first pass element 0 is compared with element 8, element 16 , element 24.....element n.....element( n+8) etc. During second pass the increment is reduced to 4, so element 0 is compared with element 4, element 8........element n, element(n+4) etc. In the third pass increment size be 2, comparison will be between element 0, element 2, element 4....element n,element( n+2) etc. And finally increment becomes 1 in the last pass. In the last pass element 0, element 1, element 2 ....element n, element (n+1) etc is compared.

This is how the shell sort operates. During each pass the elements being compared are re-arranged in sorted order,ie, if element i and j are compared the position of i and j are rearranged so that the series i,j is in sorted order.

Points of interest
Like the insertion sort it has best case of O(n) hence its suitable to check whether an array is sorted or not.
Choosing the increment sequence is a tricky question. If you are concerned about the efficiency I have few recommendations for you:
The Sedgewick increment sequence..
$9\times4^i - 9\times2^i + 1$, or $4^{i} - 3\times2^i + 1$ ......
The best known sequence according to research by Marcin Ciura is 1, 4, 10, 23, 57, 132, 301, 701, 1750

Algorithm:
input: an array a of length n with array elements numbered 0 to n − 1inc ← round(n/2)while inc > 0 do:  for i = inc .. n − 1 do:      temp ← a[i]      j ← i      while j ≥ inc and a[j − inc] > temp do:          a[j] ← a[j − inc]          j ← j − inc      a[j] ← temp  inc ← round(inc / 2.2)

Worst case performance : Depends on the leap/step size sequence
Best case performance : O(n)
Average case performance : Depends on the leap/step size sequence
Worst case space complexity: O(n)