This is forth and final tutorial of our TRIVIAL SORTING ALGORITHMS series and before going further to another solution that introduce Shell Sort, let us revisit the problem statement and constraints involved.

Problem Statement:

Suppose you have micro-controller or embedded system, in which you need to implement a sorting mechanism. It takes an array and its size as input and sort the given array.

Constraints:

1. Code footprint should not be more than some KB.
2. Stack size is very limited so do not use any form of recursion.
3. Memory is limited so try to minimize the space complexity.

Sample Data Property:

In the practical scenario size of data is not more than 50 elements and also having minimum inversion or partially sorted.

Solution:

For the sake of simplicity we will construct our algorithms on integer array a[] containing N elements.

Having done some optimization of the insertion sort in our previous post, let us consider the generalization of it known as the Shell Sort.

According to wikipedia:

“Shell sort method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbour exchange.”

What it means that shell sort allows the exchange of items that are far apart and make it partially sorted before actually running the insertion sort on whole array.

Consider the following example.

1, 13, 20, 23, 32, 5, 27

If we say that first sort the sub array consisting every third elements (h=3) then:

1, 13, 5, 23, 32, 20, 27

This is called 3-sorted array so when we would actually sort this array using insertion sort (called 1-sortted array), element 5 have to move only one slot, so only in two swaps we could put the element 5 in right position.

Beginning with large values of h; h-sort the original array thus reducing large amounts of disorder quickly, and leaving less work for smaller h-sort steps to do. If the file is then k-sorted for some smaller integer k, then the file remains h-sorted.

So when the Array is less sorted --> GAP is more thus elements cover large distance.

When GAP is less (1) --> Array is somewhat more sorted leads to less swapping.

Let us write the code that uses the GAP Sequence suggested by Knuth (3x+1)

First find the sequence:

 // according to knuth 3x + 1 sequence has good performance
 int h =1;
 while(h<size/3) {
        h = 3*h +1;
 } // sequence 1, 4, 13, 40, ...

Then perform insertion sort for each of the sequences:

while(h>=1)
{
    for(int i=h;i<size;i++) //--------------------- (1)
    {
        int tmp = a[i];
        int j = i;
        for(j=i;j>=h;j=j-h)  //------------------------- (2)
        {
            if(tmp < a[j-h] )
            {
                a[j] = a[j-h]; //------------------ (3)
            }
            else
            {
                break;
            }
        }
        a[j] = tmp;
    }

    h = h/3; //------------------------------ (4)
}

Please make note of the changes:

(1) --> loop start from h rather than 0 as we are h-sorting the array.

(2) --> J is decremented by the h (GAP SEQUENCE) times at each inner loop.

(3) --> Swapping is done between elements h hops apart

(4) --> change the HOP SEQUENCE.

consider the sequence:

1, 20, 27, 23, 13, 32, 5

first we will demonstrate the sorting using insertion sort than using shell sort with GAP sequence suggested by Knuth and then compare the two methods.

using Insertion sort

1, 20, 27, 23, 13, 32, 5 // tmp = 20

1, 20, 27, 23, 13, 32, 5 // tmp = 27

1, 20, 27, 23, 13, 32, 5 // tmp = 23 

1, 20, 23, 27, 13, 32, 5 // tmp = 23 swapped

1, 20, 23, 27, 13, 32, 5 // tmp = 13

1, 20, 23, 27, 27, 32, 5 // tmp = 13

1, 20, 23, 23, 27, 32, 5 // tmp = 13

1, 20, 20, 23, 27, 32, 5 // tmp = 13

1, 13, 20, 23, 27, 32, 5 // tmp = 32

1, 13, 20, 23, 27, 32, 5 // tmp = 5

1, 13, 20, 23, 27, 32, 32 // tmp = 5

1, 13, 20, 23, 27, 27, 32 // tmp = 5

1, 13, 20, 23, 23, 27, 32 // tmp = 5

1, 13, 20, 20, 23, 27, 32 // tmp = 5

1, 13, 13, 20, 23, 27, 32 // tmp = 5

1, 5, 13, 20, 23, 27, 32 // tmp = 5

Using shell sort → N = 7 so sequence would be 1, 4

h = 4

1, 20, 27, 23, 13, 32, 5 // i = h= 4 → a[i] = tmp = 13 → compare (13, 1)

1, 20, 27, 23, 13, 32, 5 // h= 4, i = 5 → a[i] = tmp = 32 → compare (32, 20)

1, 20, 27, 23, 13, 32, 5 // h= 4, i = 6 → a[i] = tmp = 5 → compare (5, 27)

1, 20, 5, 23, 13, 32, 27 // h= 4, i = 6 → a[i] = tmp = 5 swap

h = 1 now it became insertion sort.

1, 20, 20, 23, 13, 32, 27 // tmp = 5

1, 5, 20, 23, 13, 32, 27 // tmp = 23

1, 5, 20, 23, 23, 32, 27 // tmp = 13

1, 5, 13, 20, 23, 32, 27 // tmp = 13

1, 5, 13, 20, 23, 32, 27 // tmp = 32

1, 5, 13, 20, 23, 32, 32 // tmp = 27

1, 5, 13, 20, 23, 27, 32 // tmp = 27

In this sequence 5 has jumped 3 places saving some comparisons and assignment. It is not more visible here but in real scenario where data has less inversions this algorithm works very well.

It is evident that performance of the algorithm would depends upon the GAP sequence (h) chosen. You can check out the GAP SEQUENCE chosen and their performance over period of time here.

Though the performance analyses of shell sort and finding perfect GAP SEQUENCE are still the field of research, the performance of Shell sort is considered to be better than NlogN in some cases while maintaining little code footprint and consuming less space, making it the best solution for our problem and for the similar reasons there is an implementation of shell sort in Linux Kernel.

Though there are many more sorting algorithms that are simple and have little code footprint, they all are variants of Bubble, Insertion or Selection sort, so Shell Sort is the final solution we propose, for the problem stated in the TRIVIAL SORTING ALGORITHMS series.