Shell sort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of ShellSort is to allow the exchange of far items. In Shell sort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element are sorted.
Algorithm:
Step 1 − StartStep 2 − Initialize the value of gap size, say h.Step 3 − Divide the list into smaller sub-part. Each must have equal intervals to h.Step 4 − Sort these sub-lists using insertion sort.Step 5 - Repeat this step 2 until the list is sorted.Step 6 - Print a sorted list.Step 7 - Stop.
Following is the implementation of ShellSort.
Time Complexity: Time complexity of the above implementation of Shell sort is O(n2). In the above implementation, the gap is reduced by half in every iteration. There are many other ways to reduce gaps which leads to better time complexity. See this for more details.
Worst Case ComplexityThe worst-case complexity for shell sort is O(n2)Best Case ComplexityWhen the given array list is already sorted the total count of comparisons of each interval is equal to the size of the given array.So best case complexity is Ω(n log(n))Average Case ComplexityThe Average Case Complexity: O(n*log n)~O(n1.25)Space ComplexityThe space complexity of the shell sort is O(1).
Questions:
1. Which is more efficient shell or heap sort?
Ans. As per big-O notation, shell sort has O(n^{1.25}) average time complexity whereas, heap sort has O(N log N) time complexity. According to a strict mathematical interpretation of the big-O notation, heap sort surpasses shell sort in efficiency as we approach 2000 elements to be sorted.Note:- Big-O is a rounded approximation and analytical evaluation is not always 100% correct, it depends on the algorithms’ implementation which can affect actual run time.
Shell Sort Applications
1. Replacement for insertion sort, where it takes a long time to complete a given task.2. To call stack overhead we use shell sort.3. when recursion exceeds a particular limit we use shell sort.4. For medium to large-sized datasets.5. In insertion sort to reduce the number of operations.
References: http://en.wikipedia.org/wiki/Shellsort
Snapshots:
Quiz on Shell Sort
Other Sorting Algorithms on GeeksforGeeks/GeeksQuiz:
- Selection Sort
- Bubble Sort
- Insertion Sort
- Merge Sort
- Heap Sort
- QuickSort
- Radix Sort
- Counting Sort
- Bucket Sort