{"id":25216,"date":"2017-10-15T15:43:50","date_gmt":"2017-10-15T10:13:50","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25216"},"modified":"2017-10-15T15:43:50","modified_gmt":"2017-10-15T10:13:50","slug":"cycle-sort","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/cycle-sort\/","title":{"rendered":"Cycle Sort"},"content":{"rendered":"<p>Cycle sort is an in-place sorting Algorithm, <a href=\"https:\/\/en.wikipedia.org\/wiki\/Sorting_algorithm#Stability\" target=\"_blank\" rel=\"noopener\">unstable sorting algorithm<\/a>, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array.<\/p>\n<ul>\n<li>It is optimal in terms of number of memory writes. It <a href=\"http:\/\/www.geeksforgeeks.org\/which-sorting-algorithm-makes-minimum-number-of-writes\/\" target=\"_blank\" rel=\"noopener\">minimizes the number of memory writes<\/a> to sort (Each value is either written zero times, if it\u2019s already in its correct position, or written one time to its correct position.)<\/li>\n<li>It is based on the idea that array to be sorted can be divided into cycles. Cycles can be visualized as a graph. We have n nodes and an edge directed from node i to node j if the element at i-th index must be present at j-th index in the sorted array.<br \/>\nCycle in arr[] = {4, 5, 2, 1, 5}<\/li>\n<li>We one by one consider all cycles. We first consider the cycle that includes first element. We find correct position of first element, place it at its correct position, say j. We consider old value of arr[j] and find its correct position, we keep doing this till all elements of current cycle are placed at correct position, i.e., we don\u2019t come back to cycle starting point.\n<div id=\"practice\">\n<p>Recommended: Please try your approach on <b><i><u>{IDE}<\/u><\/i><\/b> first, before moving on to the solution.<\/p>\n<\/div>\n<p><strong>Explanation :<\/strong><\/p>\n<pre> arr[] = {10, 5, 2, 3}\r\n index =  0   1   2   3\r\ncycle_start = 0 \r\n<strong>item<\/strong> = 10 = arr[0]\r\n\r\nFind position where we put the item  \r\npos = cycle_start\r\nwhile (arr[i] < item)  \r\n    pos++;\r\n\r\nWe put 10 at arr[3] and change item to \r\nold value of arr[3].\r\narr[] = {10, 5, 2, <strong><em>10<\/em><\/strong>} \r\n<strong>item<\/strong> = 3 \r\n\r\nAgain rotate rest cycle that start with <strong>index '0' <\/strong>\r\nFind position where we put the item = 3 \r\nwe swap item with element at arr[1] now \r\narr[] = {10, <strong><em>3<\/em><\/strong>, 2, <strong><em>10<\/em><\/strong>} \r\n<strong>item<\/strong> = 5\r\n\r\nAgain rotate rest cycle that start with index '0' and item = 5 \r\nwe swap item with element at arr[2].\r\narr[] = {10, <strong><em>3<\/em><\/strong>, <strong><em>5<\/em><\/strong>, <strong><em>10<\/em> <\/strong>} \r\n<strong>item<\/strong> = 2\r\n\r\nAgain rotate rest cycle that start with index '0' and item = 2\r\narr[] = {<strong><em>2<\/em><\/strong> ,<strong><em>3<\/em><\/strong> ,<strong> <em>5<\/em><\/strong>, <strong><em>10<\/em><\/strong>}  \r\n\r\nAbove is one iteration for cycle_stat = 0.\r\nRepeat above steps for cycle_start = 1, 2, ..n-2<\/pre>\n<p>\u00a0<\/p>\n[ad type=\u201dbanner\u201d]<\/li>\n<li><strong>Below is C++ implementation of above Cycle Sort.<\/strong><\/li>\n<\/ul>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20impleament%20cycle%20sort%0A%23include%20%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Function%20sort%20the%20array%20using%20Cycle%20sort%0Avoid%20cycleSort%20(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20count%20number%20of%20memory%20writes%0A%20%20%20%20int%20writes%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20traverse%20array%20elements%20and%20put%20it%20to%20on%0A%20%20%20%20%2F%2F%20the%20right%20place%0A%20%20%20%20for%20(int%20cycle_start%3D0%3B%20cycle_start%3C%3Dn-2%3B%20cycle_start%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20initialize%20item%20as%20starting%20point%0A%20%20%20%20%20%20%20%20int%20item%20%3D%20arr%5Bcycle_start%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Find%20position%20where%20we%20put%20the%20item.%20We%20basically%0A%20%20%20%20%20%20%20%20%2F%2F%20count%20all%20smaller%20elements%20on%20right%20side%20of%20item.%0A%20%20%20%20%20%20%20%20int%20pos%20%3D%20cycle_start%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%20cycle_start%2B1%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(arr%5Bi%5D%20%3C%20item)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pos%2B%2B%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20If%20item%20is%20already%20in%20correct%20position%0A%20%20%20%20%20%20%20%20if%20(pos%20%3D%3D%20cycle_start)%0A%20%20%20%20%20%20%20%20%20%20%20%20continue%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20ignore%20all%20duplicate%20%20elements%0A%20%20%20%20%20%20%20%20while%20(item%20%3D%3D%20arr%5Bpos%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20pos%20%2B%3D%201%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20put%20the%20item%20to%20it\u2019s%20right%20position%0A%20%20%20%20%20%20%20%20if%20(pos%20!%3D%20cycle_start)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20swap(item%2C%20arr%5Bpos%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20writes%2B%2B%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Rotate%20rest%20of%20the%20cycle%0A%20%20%20%20%20%20%20%20while%20(pos%20!%3D%20cycle_start)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20pos%20%3D%20cycle_start%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Find%20position%20where%20we%20put%20the%20element%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%20cycle_start%2B1%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(arr%5Bi%5D%20%3C%20item)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pos%20%2B%3D%201%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20ignore%20all%20duplicate%20%20elements%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20(item%20%3D%3D%20arr%5Bpos%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pos%20%2B%3D%201%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20put%20the%20item%20to%20it\u2019s%20right%20position%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(item%20!%3D%20arr%5Bpos%5D)%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%20swap(item%2C%20arr%5Bpos%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20writes%2B%2B%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%7D%0A%20%0A%20%20%20%20%2F%2F%20Number%20of%20memory%20writes%20or%20swaps%0A%20%20%20%20%2F%2F%20cout%20%3C%3C%20writes%20%3C%3C%20endl%20%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B1%2C%208%2C%203%2C%209%2C%2010%2C%2010%2C%202%2C%204%20%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20cycleSort(arr%2C%20%20n)%20%3B%0A%20%0A%20%20%20%20cout%20%3C%3C%20%22After%20sort%20%3A%20%22%20%3C%3Cendl%3B%0A%20%20%20%20for%20(int%20i%20%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%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>utput:<\/p>\n<pre>1 3 4 8 10 10 \r\n<\/pre>\n<p><strong>Time Complexity<\/strong> : O(n<sup>2<\/sup>)<br \/>\nWorst Case : O(n<sup>2<\/sup>)<br \/>\nAverage Case: O(n<sup>2<\/sup>)<br \/>\nBest Case : O(n<sup>2<\/sup>)<\/p>\n<p>This sorting algorithm is best suited for situations where memory write or swap operations are costly.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Cycle Sort &#8211; Searching and sorting &#8211; Cycle sort is an in-place sorting Algorithm,unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,83508,71670],"tags":[70030,72197,70892,72177,71121,71135,72174,72205,71146,72176,72199,72183,72172,72203,72196,72201,71144,70895,70969,72186,72189,72182,70075,72191,72179,72181,72180,72184,72178,72200,72204,72202,72198,70718,72173,71175,71695,70020,71161,71149,70967,71156,72187,71142,72190,71159,72195,72185,72175,72188,70759,72192,72194,72193],"class_list":["post-25216","post","type-post","status-publish","format-standard","hentry","category-coding","category-cycle-sort","category-searching-and-sorting","tag-all-sorting-algorithms","tag-best-sorter","tag-best-sorting-algorithm","tag-best-sport","tag-bubble-sort-algorithm","tag-bubble-sort-algorithm-in-data-structure","tag-cell-cycle","tag-cell-cycle-facs","tag-comparison-of-sorting-algorithms","tag-cube-formula","tag-curly-extensions","tag-cx-x","tag-cycle-cycle","tag-cycle-flower","tag-cycling-thermals","tag-cyclone-ii","tag-different-sorting-algorithms","tag-fastest-sorting-algorithm","tag-java-sorting-algorithms","tag-life-cycle-of-a-plant","tag-life-cycle-of-flowering-plants","tag-life-cycle-of-plants","tag-linear-sort","tag-list-sort","tag-phases-of-cell-cycle","tag-plant-cycle","tag-plant-life","tag-plant-life-cycle","tag-plant-life-cycle-for-kids","tag-plant-life-cycle-for-preschool","tag-plant-life-cycle-preschool","tag-plants-and-life","tag-plants-for-life","tag-searching-and-sorting-algorithms","tag-sickle-cell","tag-sort-example","tag-sorted","tag-sorting-algorithms","tag-sorting-algorithms-comparison","tag-sorting-algorithms-in-data-structures","tag-sorting-algorithms-java","tag-sorting-algorithms-with-examples","tag-sorting-and-searching-algorithms","tag-sorting-in-data-structure","tag-sorting-methods","tag-sorting-program","tag-sorting-types","tag-sortings","tag-sport-bike","tag-testosterone-cycle","tag-topological-sort","tag-topological-sort-algorithm","tag-topological-sort-example","tag-visual-algo"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25216","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=25216"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25216\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25216"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25216"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25216"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}