{"id":25046,"date":"2017-10-15T14:08:54","date_gmt":"2017-10-15T08:38:54","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25046"},"modified":"2017-10-15T14:08:54","modified_gmt":"2017-10-15T08:38:54","slug":"selection-sort","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/selection-sort\/","title":{"rendered":"Selection Sort"},"content":{"rendered":"

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) <\/span>from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.<\/p>\n

1) The subarray which is already sorted.
\n2) Remaining subarray which is unsorted.<\/p>\n

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.<\/p>\n

Following example explains the above steps:<\/p>\n

arr[] = 64 25 12 22 11<\/p>\n

\/\/ Find the minimum element in arr[0\u20264]\n

\/\/ and place it at beginning 11 <\/strong>25 12 22 64<\/p>\n

\/\/ Find the minimum element in arr[1\u20264]\n

\/\/ and place it at beginning of arr[1\u20264] 11 12 <\/strong>25 22 64<\/p>\n

\/\/ Find the minimum element in arr[2\u20264]\n

\/\/ and place it at beginning of arr[2\u20264] 11 12 22 <\/strong>25 64<\/p>\n

\/\/ Find the minimum element in arr[3\u20264]\n

\/\/ and place it at beginning of arr[3\u20264] 11 12 22 25 <\/strong>64<\/p>\n

C and C++<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20C%20program%20for%20implementation%20of%20selection%20sort%0A%23include%20%3Cstdio.h%3E%0A%20%0Avoid%20swap(int%20*xp%2C%20int%20*yp)%0A%7B%0A%20%20%20%20int%20temp%20%3D%20*xp%3B%0A%20%20%20%20*xp%20%3D%20*yp%3B%0A%20%20%20%20*yp%20%3D%20temp%3B%0A%7D%0A%20%0Avoid%20selectionSort(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20int%20i%2C%20j%2C%20min_idx%3B%0A%20%0A%20%20%20%20%2F%2F%20One%20by%20one%20move%20boundary%20of%20unsorted%20subarray%0A%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20n-1%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20the%20minimum%20element%20in%20unsorted%20array%0A%20%20%20%20%20%20%20%20min_idx%20%3D%20i%3B%0A%20%20%20%20%20%20%20%20for%20(j%20%3D%20i%2B1%3B%20j%20%3C%20n%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20if%20(arr%5Bj%5D%20%3C%20arr%5Bmin_idx%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20min_idx%20%3D%20j%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Swap%20the%20found%20minimum%20element%20with%20the%20first%20element%0A%20%20%20%20%20%20%20%20swap(%26arr%5Bmin_idx%5D%2C%20%26arr%5Bi%5D)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20Function%20to%20print%20an%20array%20*%2F%0Avoid%20printArray(int%20arr%5B%5D%2C%20int%20size)%0A%7B%0A%20%20%20%20int%20i%3B%0A%20%20%20%20for%20(i%3D0%3B%20i%20%3C%20size%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20arr%5Bi%5D)%3B%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B64%2C%2025%2C%2012%2C%2022%2C%2011%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20selectionSort(arr%2C%20n)%3B%0A%20%20%20%20printf(%22Sorted%20array%3A%20%5Cn%22)%3B%0A%20%20%20%20printArray(arr%2C%20n)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dc and c++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n

Python<\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20for%20implementation%20of%20Selection%0A%23%20Sort%0Aimport%20sys%0AA%20%3D%20%5B64%2C%2025%2C%2012%2C%2022%2C%2011%5D%0A%20%0A%23%20Traverse%20through%20all%20array%20elements%0Afor%20i%20in%20range(len(A))%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20Find%20the%20minimum%20element%20in%20remaining%20%0A%20%20%20%20%23%20unsorted%20array%0A%20%20%20%20min_idx%20%3D%20i%0A%20%20%20%20for%20j%20in%20range(i%2B1%2C%20len(A))%3A%0A%20%20%20%20%20%20%20%20if%20A%5Bmin_idx%5D%20%3E%20A%5Bj%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20min_idx%20%3D%20j%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%23%20Swap%20the%20found%20minimum%20element%20with%20%0A%20%20%20%20%23%20the%20first%20element%20%20%20%20%20%20%20%20%0A%20%20%20%20A%5Bi%5D%2C%20A%5Bmin_idx%5D%20%3D%20A%5Bmin_idx%5D%2C%20A%5Bi%5D%0A%20%0A%23%20Driver%20code%20to%20test%20above%0Aprint%20(%22Sorted%20array%22)%0Afor%20i%20in%20range(len(A))%3A%0A%20%20%20%20print(%22%25d%22%20%25A%5Bi%5D)%2C%20\u2033 message=\u201dpython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Java<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Java%20program%20for%20implementation%20of%20Selection%20Sort%0Aclass%20SelectionSort%0A%7B%0A%20%20%20%20void%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%20One%20by%20one%20move%20boundary%20of%20unsorted%20subarray%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n-1%3B%20i%2B%2B)%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%20Find%20the%20minimum%20element%20in%20unsorted%20array%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20min_idx%20%3D%20i%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20j%20%3D%20i%2B1%3B%20j%20%3C%20n%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(arr%5Bj%5D%20%3C%20arr%5Bmin_idx%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20min_idx%20%3D%20j%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Swap%20the%20found%20minimum%20element%20with%20the%20first%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20element%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20temp%20%3D%20arr%5Bmin_idx%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bmin_idx%5D%20%3D%20arr%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bi%5D%20%3D%20temp%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Prints%20the%20array%0A%20%20%20%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%2B%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%2F%20Driver%20code%20to%20test%20above%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%20SelectionSort%20ob%20%3D%20new%20SelectionSort()%3B%0A%20%20%20%20%20%20%20%20int%20arr%5B%5D%20%3D%20%7B64%2C25%2C12%2C22%2C11%7D%3B%0A%20%20%20%20%20%20%20%20ob.sort(arr)%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22Sorted%20array%22)%3B%0A%20%20%20%20%20%20%20%20ob.printArray(arr)%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201djava\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

\u00a0<\/p>\n

Output:<\/p>\n

Sorted array: 11 12 22 25 64<\/p>\n

Time Complexity:<\/strong> O(n2<\/sup>) as there are two nested loops.<\/p>\n

Auxiliary Space:<\/strong> O(1)<\/p>\n

The good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.<\/p>\n[ad type=\u201dbanner\u201d]\n

\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"

Selection Sort – searching and sorting algorithm – The selection sort algorithm sorts an array by repeatedly finding the minimum element .<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,71670,83471],"tags":[70962,70963,70978,70975,70972,70260,70966,70979,70976,70969,70968,70977,70971,70974,70964,70539,70961,70973,70548,70960,70965,70970,70541,70967,70257],"class_list":["post-25046","post","type-post","status-publish","format-standard","hentry","category-coding","category-searching-and-sorting","category-selection-sort","tag-algorithm-for-selection-sort","tag-algorithm-of-selection-sort","tag-bubble-sort-c","tag-bubble-sort-example","tag-c-program-for-selection-sort","tag-complexity-of-selection-sort","tag-insert-sort","tag-insertion-sort-c","tag-insertion-sort-example","tag-java-sorting-algorithms","tag-program-for-selection-sort","tag-quicksort-java","tag-selection-sort-algorithm-in-c","tag-selection-sort-c-program","tag-selection-sort-code","tag-selection-sort-complexity","tag-selection-sort-example","tag-selection-sort-in-c-program","tag-selection-sort-in-data-structure","tag-selection-sort-java","tag-selection-sort-program","tag-selection-sort-program-in-c","tag-selection-sort-time-complexity","tag-sorting-algorithms-java","tag-time-complexity-of-selection-sort"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25046","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=25046"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25046\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25046"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25046"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25046"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}