Back to Course

Algorithm

0% Complete
0/82 Steps
  1. Getting Started with Algorithm
    What is an Algorithm?
  2. Characteristics of Algorithm
    1 Topic
  3. Analysis Framework
  4. Performance Analysis
    3 Topics
  5. Mathematical Analysis
    2 Topics
  6. Sorting Algorithm
    Sorting Algorithm
    10 Topics
  7. Searching Algorithm
    6 Topics
  8. Fundamental of Data Structures
    Stacks
  9. Queues
  10. Graphs
  11. Trees
  12. Sets
  13. Dictionaries
  14. Divide and Conquer
    General Method
  15. Binary Search
  16. Recurrence Equation for Divide and Conquer
  17. Finding the Maximum and Minimum
  18. Merge Sort
  19. Quick Sort
  20. Stassen’s Matrix Multiplication
  21. Advantages and Disadvantages of Divide and Conquer
  22. Decrease and Conquer
    Insertion Sort
  23. Topological Sort
  24. Greedy Method
    General Method
  25. Coin Change Problem
  26. Knapsack Problem
  27. Job Sequencing with Deadlines
  28. Minimum Cost Spanning Trees
    2 Topics
  29. Single Source Shortest Paths
    1 Topic
  30. Optimal Tree Problem
    1 Topic
  31. Transform and Conquer Approach
    1 Topic
  32. Dynamic Programming
    General Method with Examples
  33. Multistage Graphs
  34. Transitive Closure
    1 Topic
  35. All Pairs Shortest Paths
    6 Topics
  36. Backtracking
    General Method
  37. N-Queens Problem
  38. Sum of Subsets problem
  39. Graph Coloring
  40. Hamiltonian Cycles
  41. Branch and Bound
    2 Topics
  42. 0/1 Knapsack problem
    2 Topics
  43. NP-Complete and NP-Hard Problems
    1 Topic
Lesson 6, Topic 10
In Progress

Shell Sort

Lesson Progress
0% Complete

Shell sort is an algorithm that first sorts the elements far apart from each other and successively reduces the interval between the elements to be sorted. It is a generalized version of insertion sort.

In shell sort, elements at a specific interval are sorted. The interval between the elements is gradually decreased based on the sequence used. the performance of the shell sort depends on the type of sequence used for a given input array.

Some of the optimal sequences used are:

  • Shell’s original sequence: N/2 , N/4 , …, 1
  • Knuth’s increments: 1, 4, 13, …, (3k – 1) / 2
  • Sedgewick’s increments: 1, 8, 23, 77, 281, 1073, 4193, 16577…4j+1+ 3·2j+ 1.
  • Hibbard’s increments: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Papernov & Stasevich increment: 1, 3, 5, 9, 17, 33, 65,…
  • Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81….

How Shell Sort Works?

  1. Suppose, we need to sort the following array.
KodNest 11

2.We are using the shell’s original sequence (N/2, N/4, ...1) as intervals in our algorithm.

In the first loop, if the array size is N = 8 then, the elements lying at the interval of N/2 = 4 are compared and swapped if they are not in order.

  1. The 0th element is compared with the 4th element.
  2. If the 0th element is greater than the 4th one then, the 4th element is first stored in temp variable and the 0th element (ie. greater element) is stored in the 4th position and the element stored in temp is stored in the 0th position.
KodNest 1 7

This process goes on for all the remaining elements.

KodNest 2 3

3.In the second loop, an interval of N/4 = 8/4 = 2 is taken and again the elements lying at these intervals are sorted.

KodNest 3 3

You might get confused at this point.

KodNest 4 2

The elements at 4th and 2nd position are compared. The elements at 2nd and 0th position are also compared. All the elements in the array lying at the current interval are compared.

4.The same process goes on for remaining elements.

KodNest 5 2

5. Finally, when the interval is N/8 = 8/8 =1 then the array elements lying at the interval of 1 are sorted. The array is now completely sorted.

KodNest 6 1

Shell Sort Algorithm

shellSort(array, size)
  for interval i <- size/2n down to 1
    for each interval "i" in array
        sort all the elements at interval "i"
end shellSort

Shell Sort Program in C

// Shell Sort in C programming
#include <stdio.h>
void shellSort(int array[], int n){
  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;
    }
  }
}
void printArray(int array[], int size){
  for(int i=0; i<size; ++i){
     printf("%d  ", array[i]);
  }
  printf("\n");
}
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);
}

Complexity

Shell sort is unstable sorting algorithm because this algorithm does not examine the elements lying in between the intervals.

Time Complexity

  • Worst Case Complexity: less than or equal to O(n2)

    Worst case complexity for shell sort is always less than or equal to O(n2).

    According to Poonen Theorem, worst case complexity for shell sort is Θ(NlogN)2/(log logN)2) or Θ(NlogN)2/log logN) or Θ(N(logN)2) or something in between.
     
  • Best Case ComplexityO(n*log n)

    When the array is already sorted, the total number of comparison for each interval (or increment) is equal to the size of the array.
     
  • Average Case ComplexityO(n*log n)

    It is around O(n1.25).

The complexity depends on the interval chosen. The above complexities differ for different increment sequence chosen. Best increment sequence is unknown.

Space Complexity:

The space complexity for shell sort is O(1).


Shell Sort Applications

Shell sort is used when:

  • calling a stack is overhead. uClibc library uses this sort.
  • recursion exceeds a limit. bzip2 compressor uses it.
  • Insertion sort does not perform well when the close elements are far apart. Shell sort helps in reducing the distance between the close elements. Thus, there will be less number of swappings to be performed.
KodNest Training New Batch is starting on 19th October 2020. Attend one week free demo classes.Register Now

New Report

Close