ShellSort | C ++ implementation of Shell Sort ; An utility function to print array of size n ; function to sort arr using shellSort ; Start with a big gap , then reduce the gap ; Do a gapped insertion sort for this gap size . The first gap elements a [ 0. . gap - 1 ] are already in gapped order keep adding one more element until the entire array is gap sorted ; add a [ i ] to the elements that have been gap sorted save a [ i ] in temp and make a hole at position i ; shift earlier gap - sorted elements up until the correct location for a [ i ] is found ; put temp ( the original a [ i ] ) in its correct location ; Driver method
#include <iostream> NEW_LINE using namespace std ; void printArray ( int arr [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) cout << arr [ i ] << " ▁ " ; } int shellSort ( int arr [ ] , int n ) { for ( int gap = n / 2 ; gap > 0 ; gap /= 2 ) { for ( int i = gap ; i < n ; i += 1 ) { int temp = arr [ i ] ; int j ; for ( j = i ; j >= gap && arr [ j - gap ] > temp ; j -= gap ) arr [ j ] = arr [ j - gap ] ; arr [ j ] = temp ; } } return 0 ; } int main ( ) { int arr [ ] = { 12 , 34 , 54 , 2 , 3 } , i ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << " Array ▁ before ▁ sorting : ▁ STRNEWLINE " ; printArray ( arr , n ) ; shellSort ( arr , n ) ; cout << " Array after sorting : " ; printArray ( arr , n ) ; return 0 ; }