Shell Sort

Facebooktwitterredditpinterestlinkedinmailby feather

Shell Sort

Shell sort is a sorting algorithm. It is an extended version of the insertion sort.

  • In this sorting, we compare the elements that are distant apart rather than the adjacent.
  • We start by comparing elements that are at a certain distance apart. So, if there are N elements then we start with a value gap < N.
  • In each iteration we keep decreasing the value of the gap until the difference becomes 1.
  • In the last iteration, the shell sort acts as an insertion-type.

Complexity table of shell sort

Complexity Best case Average case Worst case
Time O(n) O((nlog(n))2) O((nlog(n))2)
Space     O(1)

Algorithm of shell sort

Shell_Sort (array, size)   for interval i ← size /2 down to 1.     for each interval “i” in the array.         sort all the elements at interval “i”.   end Shell_Sort.  

Shell sort example

Suppose you have the following array, which you have to sort.

14 18 19 37 23 40 29 30 11
The size of array is 9, so n = 9.     Now, find the value of the Gap.                              Gap = floor(n / 2)                                      = floor (9 / 2)                                      = floor(4.5)                                      = 4                 Pass = 1 Gap = 4   Gap 4 means, if we consider the first element at index 0 then next element will be at index 0+4 = 4., and third element will be at index 4 + 4 = 8.     Similarly, if we consider the element at index 1 then next element will be at index 1 + 4 = 5, and third element will be at index 5 + 4 = 9. But there is no 9th index in the above array so we will just have index 1 and 5.   Similarly, if we consider the element at index 2, 3, and 4 respectively then next element will be at index 2 + 4 = 6, 3 + 4 = 7, and 4 + 4 = 8 respectively.     Compare the elements.   A[0] > A[4] = 14 > 23 // false   A[1] > A[5] = 18 > 40 // false   A[2] > A[6] = 19 > 29 // false   A[3] > A[7] = 37 > 30 // true i.e., swap the both element positions.       A[4] > A[8] = 23 > 11 // true i.e., swap the both element positions.   A[1] > A[4] = 14 > 11 // true i.e., swap the both element positions.      Pass 1 is complete.   Pass 2: Gap = floor(Gap / 2)             Gap = floor(4 / 2)  // in pass 1, Gap was 4.             Gap = 2   Gap 2 means, if we consider the first element at index 0 then next element will be at index 0+2 = 2, and similarly this process applied till the end of index. Compare the elements. A[0] > A[2] = 11 > 19 // false A[]1 > A[3] = 18 > 30 // false A[2] > A[4] = 19 > 14 // true, i.e. swap the both element positions. A[1] > A[2] = 11 > 14 // false   A[3] > A[5] = 30 > 40 //false A[4] > A[6] = 19 > 29 // false A[5] > A[7] = 40 > 37 // true, i.e. swap the both element positions. A[3] > A[5] = 30 > 37 // false   A[6] > A[8] = 29 > 23 // true, i.e. swap the both element positions. A[4] > A[6] = 19 > 23 // false Pass 2 is complete.   Pass 3: Gap = floor(Gap/2)              Gap = floor(2 / 2)  // in pass 2, Gap was 2.              Gap = 1                 // i.e. last pass when gap is 1, shell sort is like the insertion sort.   Compare the elements. A[0] > A[1] = 11 > 18 // false A[1] > A[2] = 18 > 14 // true i.e. swap the both element positions. A[0] > A[1] = 11 > 14 // false   A[2] > A[3] = 18 > 30 // false A[3] > A[4] = 30 > 19 // true i.e. swap the both element positions. A[2] > A[3] = 18 > 19 // false   A[4] > A[5] = 30 > 37 // false A[5] > A[6] = 37 > 23 // true i.e. swap the both element positions. A[4] > A[5] = 30 > 23 // true i.e. swap the both element positions. A[3] > A[4] = 19 > 23 // false    A[6] > A[7] = 37 > 40 // false A[7] > A[8] = 40 > 29 // true i.e. swap the both element positions. A[6] > A[7] = 37 > 29 // true i.e. swap the both element positions. A[5] > A[6] = 30 > 29 // true i.e. swap the both element positions. A[4] > A[5] = 23 > 29 // false Pass 3 is complete, and array is fully sorted.

Shell sort program in C language:

#include <stdio.h>   // Shell sort void shellSort(int array[], int n) {     // Rearrange elements at each n/2, n/4, n/8, … intervals   for (int gap = n / 2; gap > 0; gap /= 2) {     for (int i = gap; i < n; i += 1) {       int temp = array[i];       int j;       for (j = i; j >= gap && array[j – gap] > temp; j -= gap) {         array[j] = array[j – gap];       }       array[j] = temp;     }   } }   // Print an array void printArray(int array[], int size) {   for (int i = 0; i < size; ++i) {     printf(“%d  “, array[i]);   }   printf(“\n”); }   // Driver code int main() {   int data[] = {9, 8, 3, 7, 5, 6, 4, 1};   int size = sizeof(data) / sizeof(data[0]);   shellSort(data, size);   printf(“Sorted array: \n”);   printArray(data, size); }
Facebooktwitterredditpinterestlinkedinmailby feather