C++ Program to Implement Shell Sort

shell sort is basically an Insertion Sort variant. In the insertion sort, we only transfer elements ahead of one location. Many movements are involved when an item has to be pushed far ahead. The idea behind shell sort is to allow the exchange of far-flung items. In shell sort, for a great value of h, we make the array h-sorted. We hold the value of h decreasing until it is 1. If all sublists of any h’th element are sorted, an array is said to be h-sorted.

The complexity of the Shell Sort Technique

  • Time Complexity: O(n log n) for the best-case scenario, and relies heavily on the distance series also in other cases.
  • Space Complexity: O(1)

Input:- The unsorted list: 25, 4, 87, 94, 11, 30, 210, 200, 51, 99, 10

Output:- Array after Sorting: 4, 10, 11, 25, 30, 51, 87, 94, 99, 200, 210

Algorithm

Input: A data collection, and the overall number in the array

Output: The sorted Array

Thus, we first set N in the above algorithm, which is the gap to sort the array A using shell sort. In the next step, we divide the whole array into sub-arrays using the distance. Then we sort each of the sub-arrays in the next step so that we get a sorted array at the end of the loop.

Simple Example Code of shell sort

Output:

C++ Program to Implement Shell Sort

Pin It on Pinterest

Share This