ShellSort 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 exchange of far items. In shellSort, 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 is sorted.

Following is C++ implementation of ShellSort.

 C
[pastacode lang=”c” manual=”%2F%2F%20C%2B%2B%20implementation%20of%20Shell%20Sort%0A%23include%20%20%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F*%20function%20to%20sort%20arr%20using%20shellSort%20*%2F%0Aint%20shellSort(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Start%20with%20a%20big%20gap%2C%20then%20reduce%20the%20gap%0A%20%20%20%20for%20(int%20gap%20%3D%20n%2F2%3B%20gap%20%3E%200%3B%20gap%20%2F%3D%202)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Do%20a%20gapped%20insertion%20sort%20for%20this%20gap%20size.%0A%20%20%20%20%20%20%20%20%2F%2F%20The%20first%20gap%20elements%20a%5B0..gap-1%5D%20are%20already%20in%20gapped%20order%0A%20%20%20%20%20%20%20%20%2F%2F%20keep%20adding%20one%20more%20element%20until%20the%20entire%20array%20is%0A%20%20%20%20%20%20%20%20%2F%2F%20gap%20sorted%20%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%20gap%3B%20i%20%3C%20n%3B%20i%20%2B%3D%201)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20add%20a%5Bi%5D%20to%20the%20elements%20that%20have%20been%20gap%20sorted%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20save%20a%5Bi%5D%20in%20temp%20and%20make%20a%20hole%20at%20position%20i%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20temp%20%3D%20arr%5Bi%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20shift%20earlier%20gap-sorted%20elements%20up%20until%20the%20correct%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20location%20for%20a%5Bi%5D%20is%20found%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20j%3B%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(j%20%3D%20i%3B%20j%20%3E%3D%20gap%20%26%26%20arr%5Bj%20-%20gap%5D%20%3E%20temp%3B%20j%20-%3D%20gap)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bj%5D%20%3D%20arr%5Bj%20-%20gap%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20%20put%20temp%20(the%20original%20a%5Bi%5D)%20in%20its%20correct%20location%0A%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bj%5D%20%3D%20temp%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20return%200%3B%0A%7D%0A%20%0Avoid%20printArray(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20arr%5Bi%5D%20%3C%3C%20%22%20%22%3B%0A%7D%0A%20%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B12%2C%2034%2C%2054%2C%202%2C%203%7D%2C%20i%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22Array%20before%20sorting%3A%20%5Cn%22%3B%0A%20%20%20%20printArray(arr%2C%20n)%3B%0A%20%0A%20%20%20%20shellSort(arr%2C%20n)%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22%5CnArray%20after%20sorting%3A%20%5Cn%22%3B%0A%20%20%20%20printArray(arr%2C%20n)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”c” highlight=”” provider=”manual”/]
[ad type=”banner”]

JAVA

[pastacode lang=”java” manual=”%2F%2F%20Java%20implementation%20of%20ShellSort%0Aclass%20ShellSort%0A%7B%0A%20%20%20%20%2F*%20An%20utility%20function%20to%20print%20array%20of%20size%20n*%2F%0A%20%20%20%20static%20void%20printArray(int%20arr%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20arr.length%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(arr%5Bi%5D%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20System.out.println()%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20function%20to%20sort%20arr%20using%20shellSort%20*%2F%0A%20%20%20%20int%20sort(int%20arr%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20arr.length%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Start%20with%20a%20big%20gap%2C%20then%20reduce%20the%20gap%0A%20%20%20%20%20%20%20%20for%20(int%20gap%20%3D%20n%2F2%3B%20gap%20%3E%200%3B%20gap%20%2F%3D%202)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Do%20a%20gapped%20insertion%20sort%20for%20this%20gap%20size.%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20The%20first%20gap%20elements%20a%5B0..gap-1%5D%20are%20already%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20in%20gapped%20order%20keep%20adding%20one%20more%20element%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20until%20the%20entire%20array%20is%20gap%20sorted%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%20gap%3B%20i%20%3C%20n%3B%20i%20%2B%3D%201)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20add%20a%5Bi%5D%20to%20the%20elements%20that%20have%20been%20gap%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20sorted%20save%20a%5Bi%5D%20in%20temp%20and%20make%20a%20hole%20at%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20position%20i%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20temp%20%3D%20arr%5Bi%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20shift%20earlier%20gap-sorted%20elements%20up%20until%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20the%20correct%20location%20for%20a%5Bi%5D%20is%20found%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20j%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20(j%20%3D%20i%3B%20j%20%3E%3D%20gap%20%26%26%20arr%5Bj%20-%20gap%5D%20%3E%20temp%3B%20j%20-%3D%20gap)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bj%5D%20%3D%20arr%5Bj%20-%20gap%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20put%20temp%20(the%20original%20a%5Bi%5D)%20in%20its%20correct%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20location%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bj%5D%20%3D%20temp%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20method%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20arr%5B%5D%20%3D%20%7B12%2C%2034%2C%2054%2C%202%2C%203%7D%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22Array%20before%20sorting%22)%3B%0A%20%20%20%20%20%20%20%20printArray(arr)%3B%0A%20%0A%20%20%20%20%20%20%20%20ShellSort%20ob%20%3D%20new%20ShellSort()%3B%0A%20%20%20%20%20%20%20%20ob.sort(arr)%3B%0A%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Array%20after%20sorting%22)%3B%0A%20%20%20%20%20%20%20%20printArray(arr)%3B%0A%20%20%20%20%7D%0A%7D%20″ message=”java” highlight=”” provider=”manual”/]

PYTHON

[pastacode lang=”python” manual=”%23%20Python%20program%20for%20implementation%20of%20Shell%20Sort%0A%20%0Adef%20shellSort(arr)%3A%0A%20%0A%20%20%20%20%23%20Start%20with%20a%20big%20gap%2C%20then%20reduce%20the%20gap%0A%20%20%20%20n%20%3D%20len(arr)%0A%20%20%20%20gap%20%3D%20n%2F2%0A%20%0A%20%20%20%20%23%20Do%20a%20gapped%20insertion%20sort%20for%20this%20gap%20size.%0A%20%20%20%20%23%20The%20first%20gap%20elements%20a%5B0..gap-1%5D%20are%20already%20in%20gapped%20%0A%20%20%20%20%23%20order%20keep%20adding%20one%20more%20element%20until%20the%20entire%20array%0A%20%20%20%20%23%20is%20gap%20sorted%0A%20%20%20%20while%20gap%20%3E%200%3A%0A%20%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(gap%2Cn)%3A%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20add%20a%5Bi%5D%20to%20the%20elements%20that%20have%20been%20gap%20sorted%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20save%20a%5Bi%5D%20in%20temp%20and%20make%20a%20hole%20at%20position%20i%0A%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20arr%5Bi%5D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20shift%20earlier%20gap-sorted%20elements%20up%20until%20the%20correct%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20location%20for%20a%5Bi%5D%20is%20found%0A%20%20%20%20%20%20%20%20%20%20%20%20j%20%3D%20i%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20%20j%20%3E%3D%20gap%20and%20arr%5Bj-gap%5D%20%3Etemp%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bj%5D%20%3D%20arr%5Bj-gap%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20j%20-%3D%20gap%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20put%20temp%20(the%20original%20a%5Bi%5D)%20in%20its%20correct%20location%0A%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bj%5D%20%3D%20temp%0A%20%20%20%20%20%20%20%20gap%20%2F%3D%202%0A%20%0A%20%0A%23%20Driver%20code%20to%20test%20above%0Aarr%20%3D%20%5B%2012%2C%2034%2C%2054%2C%202%2C%203%5D%0A%20%0An%20%3D%20len(arr)%0Aprint%20(%22Array%20before%20sorting%3A%22)%0Afor%20i%20in%20range(n)%3A%0A%20%20%20%20print(arr%5Bi%5D)%2C%0A%20%0AshellSort(arr)%0A%20%0Aprint%20(%22%5CnArray%20after%20sorting%3A%22)%0Afor%20i%20in%20range(n)%3A%0A%20%20%20%20print(arr%5Bi%5D)%2C%0A%20″ message=”python” highlight=”” provider=”manual”/]
[ad type=”banner”]