Shell Sort
Shell sort, also called diminishing increment sort, is (along with bubble sort) a simple sorting algorithm. It starts by sorting pairs of elements far apart from each other, then gradually reducing the gap between the elements to be compared. The shell sort is especially useful when the data being sorted is an almost sorted list.
Shell Sort works by hinging the array into a number of sublists. These sublists are derived by adding a gap to the array size before splitting it into subarrays. The gap size is derived by finding a number such that all the elements of the subarray lie within the gap; that is, the subarrays consist of elements separated by a gap of N places or more from each other.
Once the sublists are derived, the elements are compared and sorted. As the sublists are sorted and the gap reduces over consecutive iterations. This sorting approach of using different gap sizes improves the performance of the algorithm.
Now, Shell sort begins by comparing elements that are N places away from each other. This step is known as a ‘pass’. In each pass, the elements that are compared and swapped are of the same ‘distance’ from each other. This distance is decided by the gap, which is a variable used to control the length of the sublists. After completing the pass, the gap reduces, and the same procedure is repeated until all the elements are sorted.
For example, consider an array [7, 3, 2, 8, 1]. Let us assume that the gap is of size 2, meaning that all the elements which are 2 places away from each other are compared. The steps are as follows:
First Pass:
Compare elements [7, 2] (7 > 2 so, swap them)
Compare elements [3, 8] (3 < 8 so, no swapping needed)
Compare elements [2, 1] (2 > 1 so, swap them)
Second Pass:
Compare elements [2, 7] (2 < 7 so, no swapping needed)
Compare elements [3, 1] (3 > 1 so, swap them)
The array would become [2, 7, 1, 8, 3]. This sorting technique leads to the formation of a slightly-sorted list. The ‘gap’ of 2 places is reduced by one more place after the first pass, leading to a gap of 1 place. Because the elements have already been partially sorted, the next pass does not take long.
The final pass would also involve a gap of 1 place, and would sort all the elements correctly. The sorted array would then be [1, 2, 3, 7, 8].
To conclude, shell sort proves to be an effective sorting algorithm. It is easy to implement and is also faster than other sorting algorithms such as bubble sort, insertion sort, etc. It is mainly used for sorting small sequences which are almost sorted as a single pass would be enough for sorting the entire sequence. Shell sort can also be used for sorting large sequences, however, in this case more passes have to be done in order to sort the whole sequence.
