{"id":25200,"date":"2017-10-15T15:33:29","date_gmt":"2017-10-15T10:03:29","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25200"},"modified":"2017-10-15T15:33:29","modified_gmt":"2017-10-15T10:03:29","slug":"shellsort","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/shellsort\/","title":{"rendered":"ShellSort"},"content":{"rendered":"

ShellSort is mainly a variation of Insertion Sort<\/a>.<\/span> 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\u2019th element is sorted.<\/p>\n

Following is C++ implementation of ShellSort.<\/p>\n

\n
\n
\u00a0C<\/strong><\/div>\n
\n[pastacode lang=\u201dc\u201d manual=\u201d%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\u201d message=\u201dc\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<\/div>\n
\n[ad type=\u201dbanner\u201d]\n

JAVA<\/strong><\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%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\u2033 message=\u201djava\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

PYTHON<\/strong><\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%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\u2033 message=\u201dpython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<\/div>\n<\/div>\n<\/div>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"

ShellSort – Searching and Sorting – 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. <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,71670,83505],"tags":[70054,2380,70478,71995,72054,70052,70263,70273,70268,71987,70461,71121,70978,71122,71129,70780,71993,70465,71151,70497,71868,70048,71144,70507,70271,70928,71216,70017,70979,71225,70969,34643,70262,71262,71263,71281,71267,70046,71145,71269,71266,71870,72056,71120,70016,70964,70965,71697,72055,71674,71125,71162,71695,70020,70019,70967,71156,72053,71990,72052],"class_list":["post-25200","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-searching-and-sorting","category-shellsort","tag-algorithm","tag-array-sort","tag-avl-tree","tag-bein-sport","tag-best-sorting-algorithm-in-java","tag-binary-search","tag-binary-search-tree","tag-binary-sort","tag-binary-tree","tag-bitbucket","tag-bubble-sort","tag-bubble-sort-algorithm","tag-bubble-sort-c","tag-bubble-sort-java","tag-bubble-sort-program","tag-bubblesort","tag-bucket","tag-bucket-sort","tag-bucket-sort-algorithm","tag-counting-sort","tag-counting-sort-algorithm","tag-data-structures","tag-different-sorting-algorithms","tag-hash-table","tag-heap-sort","tag-heap-sort-algorithm","tag-insertion-sort","tag-insertion-sort-algorithm","tag-insertion-sort-c","tag-insertion-sort-program","tag-java-sorting-algorithms","tag-keyword","tag-merge-sort","tag-merge-sort-algorithm","tag-merge-sort-java","tag-merge-sort-program","tag-quick-sort-algorithm","tag-quicksort","tag-quicksort-c","tag-radix-sort","tag-radix-sort-algorithm","tag-radix-sort-algorithm-in-data-structure","tag-radix-sort-example-step-by-step","tag-selection-sort","tag-selection-sort-algorithm","tag-selection-sort-code","tag-selection-sort-program","tag-shell-sort","tag-shell-sort-algorithm","tag-sort","tag-sort-code","tag-sort-java","tag-sorted","tag-sorting-algorithms","tag-sorting-algorithms-in-java","tag-sorting-algorithms-java","tag-sorting-algorithms-with-examples","tag-sorting-in-java","tag-sorting-techniques-in-java","tag-types-of-sorting"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25200","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25200"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25200\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25200"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25200"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25200"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}