C++ Program to Implement Shell Sort
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
ShellSort(array, size)
Input: A data collection, and the overall number in the array
Output: The sorted Array
shell_sort (A, N)
where A – list to be sorted; N – gap_size
set gap_size = N, flag = 1
while gap_size > 1 or flag = 1, repeat
begin
set flag = 0
set gap_size = (gap_size + 1)/2
end
for i = 0 to i< (N-gap_size) repeat
begin
if A[i + gap_size] > A[i]
swap A[i + gap_size], A[i]
set flag = 0
end
end
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
// Program to implementation of Shell Sort in C++
#include <iostream>
using namespace std;
int shellSort(int array[], int p)
{
for (int gap = p/2; gap > 0; gap /= 2)
{
// Do a gapped insertion sort for this gap size.
// keep adding one more element until the entire array is
// gap sorted
for (int l = gap; l < p; l += 1)
{
// add a[l] to the elements that have been gap sorted
// save a[l] in temp and make a hole at position l
int temp = array[l];
// shift earlier gap-sorted elements up until the correct
// location for a[l] is found
int j;
for (j = l; j >= gap && array[j - gap] > temp; j -= gap)
array[j] = array[j - gap];
// put temp (the original a[l]) in its correct location
array[j] = temp;
}
}
return 0;
}
void printArray(int array[], int p)
{
for (int l=0; l<p; l++)
cout << array[l] << " ";
}
int main()
{
int array[] = {70, 5, 3, 16, 25, 77, 110, 40, 21}, l;
int p = sizeof(array)/sizeof(array[0]);
cout << "Array before sorting: \n";
printArray(array, p);
shellSort(array, p);
cout << "\nArray after sorting: \n";
printArray(array, p);
return 0;
}
Output:
