Shell Sort

ShellSort is an in-place comparison sort.  It is mainly a variation of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). This algorithm avoids large shifts as in case of insertion sort, if the smaller value is to the far right and has to be moved to the far left. The idea of shell sort is to allow exchange of far items. This spacing is termed as interval or gap. ShellSort is more efficient compared to Insertion Sort or Bubble sort specially when –

• 1. Smaller value elements are towards the end of the array/list
• 2. Large sized array/list
• 3. Efficiency depends on how we select the GAP/interval

Time Complexity –

• 1. Best Case – Ω(n log(n))
• 2. Worst Case – O(n^2)
• 3. Average Case – θ(n log(n)2)

Space Complexity – O(1)

Working –

• Step 1 − Initialize the value of gap/interval (here we take n/2 iteratively)
• Step 2 − Compare 2 elements at the distance of gap at every iteration
• Step 3 − if element at the left is smaller than element at the right, perform swap or shift(depending on whether you use bubble sort or insertion sort respectively)
• Step 3 − Repeat until complete list is sorted.

Algorithm:

void ShellSort(int arr[], int n)

for(int gap=n/2; gap>0; gap /= 2)

for(int j = gap; j<n; j+=1)

for(i=j; i>=0; i-=gap)

if (arr[i+gap] >= arr[i])

                                       Break:

                                else

                swap(a[i+gap], arr[i])

To improve the Time Complexity of the Shell Sort algorithm, the different sequences may be used to create the intervals.

• Step 1 : Considering the array to be sorted 
• Step 2 : Selecting elements with N/2 intervals 
• Step 3 : Insertion sort is applied on the elements selected in the previous step 
  • Step 4 : Selection of elements with N/2 intervals and application of Insertion sort is carried out on the rest of the array 
  • Step 5 : Selecting elements in an N/4 interval and applying Insertion sort on them 
  • Step 6 : Step 5 is repeated on the rest of the array 
  • Step 7 : Selection of elements in an interval of N/8 elements and the application of Insertion sort on them is carried out 
  • Step 8 : The final sorted array