Shell Sort Algorithm (Theory + Working + Pseudocode) with Example | Part - 1 | Sorting Algorithms

Показать описание

Support Simple Snippets by Donations -
--------------------------------------------------------------------------------------------- Understand the working of Shell sort algorithm with example and diagram. In this tutorial we will understand in detail how shell sort works with the help of a diagram. We will also dry run the pseudo code of shell sort with an example to understand how the shell sort algorithm progresses at every step.
1) ShellSort is an in-place comparison sort.
2)It is mainly a variation of sorting by exchange (bubble sort) or sorting by insertion (insertion sort)
3) 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.
4) The idea of shellSort is to allow exchange of far items.
5) This spacing is termed as interval or gap.
6) ShellSort is more efficient compared to Insertion Sort or Bubble sort specially when -
a. Smaller value elements are towards the end of the array/list
b. Large sized array/list
c. 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 Steps -
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.

Simple Snippets Official Website -
Simple Snippets on Facebook -
Simple Snippets on Instagram -
Simple Snippets on Twitter -
Simple Snippets Google Plus Page -
Simple Snippets email ID -

#shellsort #sortingalgorithms #datastructures #algorithms