Cycle sort

Unlike nearly every other sort, items are never written elsewhere in the array simply to push them out of the way of the action. Each value is either written zero times, if it is already in its correct position, or written one time to its correct position. This matches the minimal number of overwrites required for a completed in-place sort.

Minimizing the number of writes is useful when making writes to some huge data set is very expensive, such as with EEPROMs like Flash memory where each write reduces the lifespan of the memory.

Algorithm

To illustrate the idea of cycle sort, consider a list with distinct elements. Given an element ${\displaystyle x}$, we can find the index at which it will occur in the sorted list by simply counting the number of elements in the entire list that are smaller than ${\displaystyle x}$. Now

1. If the element is already at the correct position, do nothing.
2. If it is not, we will write it to its intended position. That position is inhabited by a different element ${\displaystyle y}$, which we then have to move to its correct position. This process of displacing elements to their correct positions continues until an element is moved to the original position of ${\displaystyle x}$. This completes a cycle.

Repeating this process for every element sorts the list, with a single writing operation if and only if an element is not already at its correct position. While computing the correct positions takes ${\displaystyle O(n)}$ time for every single element, thus resulting in a quadratic time algorithm, the number of writing operations is minimized.

Implementation

To create a working implementation from the above outline, two issues need to be addressed:

1. When computing the correct positions, we have to make sure not to double-count the first element of the cycle.
2. If there are duplicate elements present, when we try to move an element ${\displaystyle x}$ to its correct position, that position might already be inhabited by an ${\displaystyle x}$. Simply swapping these would cause the algorithm to cycle indefinitely. Instead, we have to insert the element after any of its duplicates.

The following Python implementation performs cycle sort on an array, counting the number of writes to that array that were needed to sort it.

Python

<span id="mwPQ"></span><span class="linenos" data-line="1" id="mwPg"></span><span class="k" id="mwPw">def</span><span class="w" id="mwQA"> </span><span class="nf" id="mwQQ">cycle_sort</span><span class="p" id="mwQg">(</span><span class="n" id="mwQw">array</span><span class="p" id="mwRA">)</span> <span class="o" id="mwRQ">-></span> <span class="nb" id="mwRg">int</span><span class="p" id="mwRw">:</span> <span class="linenos" data-line="2" id="mwSA"></span><span class="w" id="mwSQ"> </span><span class="sd" id="mwSg">"""Sort an array in place and return the number of writes."""</span> <span class="linenos" data-line="3" id="mwSw"></span> <span class="n" id="mwTA">writes</span> <span class="o" id="mwTQ">=</span> <span class="mi" id="mwTg">0</span> <span class="linenos" data-line="4" id="mwTw"></span> <span class="linenos" data-line="5" id="mwUA"></span> <span class="c1" id="mwUQ"># Loop through the array to find cycles to rotate.</span> <span class="linenos" data-line="6" id="mwUg"></span> <span class="c1" id="mwUw"># Note that the last item will already be sorted after the first n-1 cycles.</span> <span class="linenos" data-line="7" id="mwVA"></span> <span class="k" id="mwVQ">for</span> <span class="n" id="mwVg">cycle_start</span> <span class="ow" id="mwVw">in</span> <span class="nb" id="mwWA">range</span><span class="p" id="mwWQ">(</span><span class="mi" id="mwWg">0</span><span class="p" id="mwWw">,</span> <span class="nb" id="mwXA">len</span><span class="p" id="mwXQ">(</span><span class="n" id="mwXg">array</span><span class="p" id="mwXw">)</span> <span class="o" id="mwYA">-</span> <span class="mi" id="mwYQ">1</span><span class="p" id="mwYg">):</span> <span class="linenos" data-line="8" id="mwYw"></span> <span class="n" id="mwZA">item</span> <span class="o" id="mwZQ">=</span> <span class="n" id="mwZg">array</span><span class="p" id="mwZw">[</span><span class="n" id="mwaA">cycle_start</span><span class="p" id="mwaQ">]</span> <span class="linenos" data-line="9" id="mwag"></span> <span class="linenos" data-line="10" id="mwaw"></span> <span class="c1" id="mwbA"># Find where to put the item.</span> <span class="linenos" data-line="11" id="mwbQ"></span> <span class="n" id="mwbg">pos</span> <span class="o" id="mwbw">=</span> <span class="n" id="mwcA">cycle_start</span> <span class="linenos" data-line="12" id="mwcQ"></span> <span class="k" id="mwcg">for</span> <span class="n" id="mwcw">i</span> <span class="ow" id="mwdA">in</span> <span class="nb" id="mwdQ">range</span><span class="p" id="mwdg">(</span><span class="n" id="mwdw">cycle_start</span> <span class="o" id="mweA">+</span> <span class="mi" id="mweQ">1</span><span class="p" id="mweg">,</span> <span class="nb" id="mwew">len</span><span class="p" id="mwfA">(</span><span class="n" id="mwfQ">array</span><span class="p" id="mwfg">)):</span> <span class="linenos" data-line="13" id="mwfw"></span> <span class="k" id="mwgA">if</span> <span class="n" id="mwgQ">array</span><span class="p" id="mwgg">[</span><span class="n" id="mwgw">i</span><span class="p" id="mwhA">]</span> <span class="o" id="mwhQ"><</span> <span class="n" id="mwhg">item</span><span class="p" id="mwhw">:</span> <span class="linenos" data-line="14" id="mwiA"></span> <span class="n" id="mwiQ">pos</span> <span class="o" id="mwig">+=</span> <span class="mi" id="mwiw">1</span> <span class="linenos" data-line="15" id="mwjA"></span> <span class="linenos" data-line="16" id="mwjQ"></span> <span class="c1" id="mwjg"># If the item is already there, this is not a cycle.</span> <span class="linenos" data-line="17" id="mwjw"></span> <span class="k" id="mwkA">if</span> <span class="n" id="mwkQ">pos</span> <span class="o" id="mwkg">==</span> <span class="n" id="mwkw">cycle_start</span><span class="p" id="mwlA">:</span> <span class="linenos" data-line="18" id="mwlQ"></span> <span class="k" id="mwlg">continue</span> <span class="linenos" data-line="19" id="mwlw"></span> <span class="linenos" data-line="20" id="mwmA"></span> <span class="c1" id="mwmQ"># Otherwise, put the item there or right after any duplicates.</span> <span class="linenos" data-line="21" id="mwmg"></span> <span class="k" id="mwmw">while</span> <span class="n" id="mwnA">item</span> <span class="o" id="mwnQ">==</span> <span class="n" id="mwng">array</span><span class="p" id="mwnw">[</span><span class="n" id="mwoA">pos</span><span class="p" id="mwoQ">]:</span> <span class="linenos" data-line="22" id="mwog"></span> <span class="n" id="mwow">pos</span> <span class="o" id="mwpA">+=</span> <span class="mi" id="mwpQ">1</span> <span class="linenos" data-line="23" id="mwpg"></span> <span class="linenos" data-line="24" id="mwpw"></span> <span class="n" id="mwqA">array</span><span class="p" id="mwqQ">[</span><span class="n" id="mwqg">pos</span><span class="p" id="mwqw">],</span> <span class="n" id="mwrA">item</span> <span class="o" id="mwrQ">=</span> <span class="n" id="mwrg">item</span><span class="p" id="mwrw">,</span> <span class="n" id="mwsA">array</span><span class="p" id="mwsQ">[</span><span class="n" id="mwsg">pos</span><span class="p" id="mwsw">]</span> <span class="linenos" data-line="25" id="mwtA"></span> <span class="n" id="mwtQ">writes</span> <span class="o" id="mwtg">+=</span> <span class="mi" id="mwtw">1</span> <span class="linenos" data-line="26" id="mwuA"></span> <span class="linenos" data-line="27" id="mwuQ"></span> <span class="c1" id="mwug"># Rotate the rest of the cycle.</span> <span class="linenos" data-line="28" id="mwuw"></span> <span class="k" id="mwvA">while</span> <span class="n" id="mwvQ">pos</span> <span class="o" id="mwvg">!=</span> <span class="n" id="mwvw">cycle_start</span><span class="p" id="mwwA">:</span> <span class="linenos" data-line="29" id="mwwQ"></span> <span class="c1" id="mwwg"># Find where to put the item.</span> <span class="linenos" data-line="30" id="mwww"></span> <span class="n" id="mwxA">pos</span> <span class="o" id="mwxQ">=</span> <span class="n" id="mwxg">cycle_start</span> <span class="linenos" data-line="31" id="mwxw"></span> <span class="k" id="mwyA">for</span> <span class="n" id="mwyQ">i</span> <span class="ow" id="mwyg">in</span> <span class="nb" id="mwyw">range</span><span class="p" id="mwzA">(</span><span class="n" id="mwzQ">cycle_start</span> <span class="o" id="mwzg">+</span> <span class="mi" id="mwzw">1</span><span class="p" id="mw0A">,</span> <span class="nb" id="mw0Q">len</span><span class="p" id="mw0g">(</span><span class="n" id="mw0w">array</span><span class="p" id="mw1A">)):</span> <span class="linenos" data-line="32" id="mw1Q"></span> <span class="k" id="mw1g">if</span> <span class="n" id="mw1w">array</span><span class="p" id="mw2A">[</span><span class="n" id="mw2Q">i</span><span class="p" id="mw2g">]</span> <span class="o" id="mw2w"><</span> <span class="n" id="mw3A">item</span><span class="p" id="mw3Q">:</span> <span class="linenos" data-line="33" id="mw3g"></span> <span class="n" id="mw3w">pos</span> <span class="o" id="mw4A">+=</span> <span class="mi" id="mw4Q">1</span> <span class="linenos" data-line="34" id="mw4g"></span> <span class="linenos" data-line="35" id="mw4w"></span> <span class="c1" id="mw5A"># Put the item there or right after any duplicates.</span> <span class="linenos" data-line="36" id="mw5Q"></span> <span class="k" id="mw5g">while</span> <span class="n" id="mw5w">item</span> <span class="o" id="mw6A">==</span> <span class="n" id="mw6Q">array</span><span class="p" id="mw6g">[</span><span class="n" id="mw6w">pos</span><span class="p" id="mw7A">]:</span> <span class="linenos" data-line="37" id="mw7Q"></span> <span class="n" id="mw7g">pos</span> <span class="o" id="mw7w">+=</span> <span class="mi" id="mw8A">1</span> <span class="linenos" data-line="38" id="mw8Q"></span> <span class="n" id="mw8g">array</span><span class="p" id="mw8w">[</span><span class="n" id="mw9A">pos</span><span class="p" id="mw9Q">],</span> <span class="n" id="mw9g">item</span> <span class="o" id="mw9w">=</span> <span class="n" id="mw-A">item</span><span class="p" id="mw-Q">,</span> <span class="n" id="mw-g">array</span><span class="p" id="mw-w">[</span><span class="n" id="mw_A">pos</span><span class="p" id="mw_Q">]</span> <span class="linenos" data-line="39" id="mw_g"></span> <span class="n" id="mw_w">writes</span> <span class="o" id="mwAQA">+=</span> <span class="mi" id="mwAQE">1</span> <span class="linenos" data-line="40" id="mwAQI"></span> <span class="linenos" data-line="41" id="mwAQM"></span> <span class="k" id="mwAQQ">return</span> <span class="n" id="mwAQU">writes</span>

The next implementation written in C++ simply performs cyclic array sorting.

<span id="mwAQo"></span><span class="linenos" data-line="1" id="mwAQs"></span><span class="k" id="mwAQw">template</span><span class="w" id="mwAQ0"> </span><span class="o" id="mwAQ4"><</span><span class="k" id="mwAQ8">typename</span><span class="w" id="mwARA"> </span><span class="nc" id="mwARE">type_array</span><span class="o" id="mwARI">></span> <span class="linenos" data-line="2" id="mwARM"></span><span class="kt" id="mwARQ">void</span><span class="w" id="mwARU"> </span><span class="n" id="mwARY">cycle_sort</span><span class="p" id="mwARc">(</span><span class="n" id="mwARg">type_array</span><span class="w" id="mwARk"> </span><span class="o" id="mwARo">*</span><span class="n" id="mwARs">Array</span><span class="p" id="mwARw">,</span><span class="w" id="mwAR0"> </span><span class="kt" id="mwAR4">int</span><span class="w" id="mwAR8"> </span><span class="n" id="mwASA">array_size</span><span class="p" id="mwASE">)</span> <span class="linenos" data-line="3" id="mwASI"></span><span class="p" id="mwASM">{</span> <span class="linenos" data-line="4" id="mwASQ"></span><span class="w" id="mwASU"> </span><span class="k" id="mwASY">for</span><span class="w" id="mwASc"> </span><span class="p" id="mwASg">(</span><span class="kt" id="mwASk">int</span><span class="w" id="mwASo"> </span><span class="n" id="mwASs">cycle_start</span><span class="w" id="mwASw"> </span><span class="o" id="mwAS0">=</span><span class="w" id="mwAS4"> </span><span class="mi" id="mwAS8">0</span><span class="p" id="mwATA">;</span><span class="w" id="mwATE"> </span><span class="n" id="mwATI">cycle_start</span><span class="w" id="mwATM"> </span><span class="o" id="mwATQ"><</span><span class="w" id="mwATU"> </span><span class="n" id="mwATY">array_size</span><span class="w" id="mwATc"> </span><span class="o" id="mwATg">-</span><span class="w" id="mwATk"> </span><span class="mi" id="mwATo">1</span><span class="p" id="mwATs">;</span><span class="w" id="mwATw"> </span><span class="n" id="mwAT0">cycle_start</span><span class="o" id="mwAT4">++</span><span class="p" id="mwAT8">)</span> <span class="linenos" data-line="5" id="mwAUA"></span><span class="w" id="mwAUE"> </span><span class="p" id="mwAUI">{</span> <span class="linenos" data-line="6" id="mwAUM"></span><span class="w" id="mwAUQ"> </span><span class="n" id="mwAUU">type_array</span><span class="w" id="mwAUY"> </span><span class="n" id="mwAUc">item</span><span class="w" id="mwAUg"> </span><span class="o" id="mwAUk">=</span><span class="w" id="mwAUo"> </span><span class="n" id="mwAUs">Array</span><span class="p" id="mwAUw">[</span><span class="n" id="mwAU0">cycle_start</span><span class="p" id="mwAU4">];</span> <span class="linenos" data-line="7" id="mwAU8"></span> <span class="linenos" data-line="8" id="mwAVA"></span><span class="w" id="mwAVE"> </span><span class="kt" id="mwAVI">int</span><span class="w" id="mwAVM"> </span><span class="n" id="mwAVQ">pos</span><span class="w" id="mwAVU"> </span><span class="o" id="mwAVY">=</span><span class="w" id="mwAVc"> </span><span class="n" id="mwAVg">cycle_start</span><span class="p" id="mwAVk">;</span> <span class="linenos" data-line="9" id="mwAVo"></span><span class="w" id="mwAVs"> </span><span class="k" id="mwAVw">for</span><span class="w" id="mwAV0"> </span><span class="p" id="mwAV4">(</span><span class="kt" id="mwAV8">int</span><span class="w" id="mwAWA"> </span><span class="n" id="mwAWE">i</span><span class="w" id="mwAWI"> </span><span class="o" id="mwAWM">=</span><span class="w" id="mwAWQ"> </span><span class="n" id="mwAWU">cycle_start</span><span class="w" id="mwAWY"> </span><span class="o" id="mwAWc">+</span><span class="w" id="mwAWg"> </span><span class="mi" id="mwAWk">1</span><span class="p" id="mwAWo">;</span><span class="w" id="mwAWs"> </span><span class="n" id="mwAWw">i</span><span class="w" id="mwAW0"> </span><span class="o" id="mwAW4"><</span><span class="w" id="mwAW8"> </span><span class="n" id="mwAXA">array_size</span><span class="p" id="mwAXE">;</span><span class="w" id="mwAXI"> </span><span class="n" id="mwAXM">i</span><span class="o" id="mwAXQ">++</span><span class="p" id="mwAXU">)</span> <span class="linenos" data-line="10" id="mwAXY"></span><span class="w" id="mwAXc"> </span><span class="k" id="mwAXg">if</span><span class="w" id="mwAXk"> </span><span class="p" id="mwAXo">(</span><span class="n" id="mwAXs">Array</span><span class="p" id="mwAXw">[</span><span class="n" id="mwAX0">i</span><span class="p" id="mwAX4">]</span><span class="w" id="mwAX8"> </span><span class="o" id="mwAYA"><</span><span class="w" id="mwAYE"> </span><span class="n" id="mwAYI">item</span><span class="p" id="mwAYM">)</span> <span class="linenos" data-line="11" id="mwAYQ"></span><span class="w" id="mwAYU"> </span><span class="n" id="mwAYY">pos</span><span class="w" id="mwAYc"> </span><span class="o" id="mwAYg">+=</span><span class="w" id="mwAYk"> </span><span class="mi" id="mwAYo">1</span><span class="p" id="mwAYs">;</span> <span class="linenos" data-line="12" id="mwAYw"></span><span class="w" id="mwAY0"> </span><span class="k" id="mwAY4">if</span><span class="w" id="mwAY8"> </span><span class="p" id="mwAZA">(</span><span class="n" id="mwAZE">pos</span><span class="w" id="mwAZI"> </span><span class="o" id="mwAZM">==</span><span class="w" id="mwAZQ"> </span><span class="n" id="mwAZU">cycle_start</span><span class="p" id="mwAZY">)</span> <span class="linenos" data-line="13" id="mwAZc"></span><span class="w" id="mwAZg"> </span><span class="k" id="mwAZk">continue</span><span class="p" id="mwAZo">;</span> <span class="linenos" data-line="14" id="mwAZs"></span><span class="w" id="mwAZw"> </span><span class="k" id="mwAZ0">while</span><span class="w" id="mwAZ4"> </span><span class="p" id="mwAZ8">(</span><span class="n" id="mwAaA">item</span><span class="w" id="mwAaE"> </span><span class="o" id="mwAaI">==</span><span class="w" id="mwAaM"> </span><span class="n" id="mwAaQ">Array</span><span class="p" id="mwAaU">[</span><span class="n" id="mwAaY">pos</span><span class="p" id="mwAac">])</span> <span class="linenos" data-line="15" id="mwAag"></span><span class="w" id="mwAak"> </span><span class="n" id="mwAao">pos</span><span class="w" id="mwAas"> </span><span class="o" id="mwAaw">+=</span><span class="w" id="mwAa0"> </span><span class="mi" id="mwAa4">1</span><span class="p" id="mwAa8">;</span> <span class="linenos" data-line="16" id="mwAbA"></span> <span class="linenos" data-line="17" id="mwAbE"></span><span class="w" id="mwAbI"> </span><span class="n" id="mwAbM">std</span><span class="o" id="mwAbQ">::</span><span class="n" id="mwAbU">swap</span><span class="p" id="mwAbY">(</span><span class="n" id="mwAbc">Array</span><span class="p" id="mwAbg">[</span><span class="n" id="mwAbk">pos</span><span class="p" id="mwAbo">],</span><span class="w" id="mwAbs"> </span><span class="n" id="mwAbw">item</span><span class="p" id="mwAb0">);</span> <span class="linenos" data-line="18" id="mwAb4"></span> <span class="linenos" data-line="19" id="mwAb8"></span><span class="w" id="mwAcA"> </span><span class="k" id="mwAcE">while</span><span class="w" id="mwAcI"> </span><span class="p" id="mwAcM">(</span><span class="n" id="mwAcQ">pos</span><span class="w" id="mwAcU"> </span><span class="o" id="mwAcY">!=</span><span class="w" id="mwAcc"> </span><span class="n" id="mwAcg">cycle_start</span><span class="p" id="mwAck">)</span> <span class="linenos" data-line="20" id="mwAco"></span><span class="w" id="mwAcs"> </span><span class="p" id="mwAcw">{</span> <span class="linenos" data-line="21" id="mwAc0"></span><span class="w" id="mwAc4"> </span><span class="n" id="mwAc8">pos</span><span class="w" id="mwAdA"> </span><span class="o" id="mwAdE">=</span><span class="w" id="mwAdI"> </span><span class="n" id="mwAdM">cycle_start</span><span class="p" id="mwAdQ">;</span> <span class="linenos" data-line="22" id="mwAdU"></span><span class="w" id="mwAdY"> </span><span class="k" id="mwAdc">for</span><span class="w" id="mwAdg"> </span><span class="p" id="mwAdk">(</span><span class="kt" id="mwAdo">int</span><span class="w" id="mwAds"> </span><span class="n" id="mwAdw">i</span><span class="w" id="mwAd0"> </span><span class="o" id="mwAd4">=</span><span class="w" id="mwAd8"> </span><span class="n" id="mwAeA">cycle_start</span><span class="w" id="mwAeE"> </span><span class="o" id="mwAeI">+</span><span class="w" id="mwAeM"> </span><span class="mi" id="mwAeQ">1</span><span class="p" id="mwAeU">;</span><span class="w" id="mwAeY"> </span><span class="n" id="mwAec">i</span><span class="w" id="mwAeg"> </span><span class="o" id="mwAek"><</span><span class="w" id="mwAeo"> </span><span class="n" id="mwAes">array_size</span><span class="p" id="mwAew">;</span><span class="w" id="mwAe0"> </span><span class="n" id="mwAe4">i</span><span class="o" id="mwAe8">++</span><span class="p" id="mwAfA">)</span> <span class="linenos" data-line="23" id="mwAfE"></span><span class="w" id="mwAfI"> </span><span class="k" id="mwAfM">if</span><span class="w" id="mwAfQ"> </span><span class="p" id="mwAfU">(</span><span class="n" id="mwAfY">Array</span><span class="p" id="mwAfc">[</span><span class="n" id="mwAfg">i</span><span class="p" id="mwAfk">]</span><span class="w" id="mwAfo"> </span><span class="o" id="mwAfs"><</span><span class="w" id="mwAfw"> </span><span class="n" id="mwAf0">item</span><span class="p" id="mwAf4">)</span> <span class="linenos" data-line="24" id="mwAf8"></span><span class="w" id="mwAgA"> </span><span class="n" id="mwAgE">pos</span><span class="w" id="mwAgI"> </span><span class="o" id="mwAgM">+=</span><span class="w" id="mwAgQ"> </span><span class="mi" id="mwAgU">1</span><span class="p" id="mwAgY">;</span> <span class="linenos" data-line="25" id="mwAgc"></span><span class="w" id="mwAgg"> </span><span class="k" id="mwAgk">while</span><span class="w" id="mwAgo"> </span><span class="p" id="mwAgs">(</span><span class="n" id="mwAgw">item</span><span class="w" id="mwAg0"> </span><span class="o" id="mwAg4">==</span><span class="w" id="mwAg8"> </span><span class="n" id="mwAhA">Array</span><span class="p" id="mwAhE">[</span><span class="n" id="mwAhI">pos</span><span class="p" id="mwAhM">])</span> <span class="linenos" data-line="26" id="mwAhQ"></span><span class="w" id="mwAhU"> </span><span class="n" id="mwAhY">pos</span><span class="w" id="mwAhc"> </span><span class="o" id="mwAhg">+=</span><span class="w" id="mwAhk"> </span><span class="mi" id="mwAho">1</span><span class="p" id="mwAhs">;</span> <span class="linenos" data-line="27" id="mwAhw"></span> <span class="linenos" data-line="28" id="mwAh0"></span><span class="w" id="mwAh4"> </span><span class="n" id="mwAh8">std</span><span class="o" id="mwAiA">::</span><span class="n" id="mwAiE">swap</span><span class="p" id="mwAiI">(</span><span class="n" id="mwAiM">Array</span><span class="p" id="mwAiQ">[</span><span class="n" id="mwAiU">pos</span><span class="p" id="mwAiY">],</span><span class="w" id="mwAic"> </span><span class="n" id="mwAig">item</span><span class="p" id="mwAik">);</span> <span class="linenos" data-line="29" id="mwAio"></span><span class="w" id="mwAis"> </span><span class="p" id="mwAiw">}</span> <span class="linenos" data-line="30" id="mwAi0"></span><span class="w" id="mwAi4"> </span><span class="p" id="mwAi8">}</span> <span class="linenos" data-line="31" id="mwAjA"></span><span class="p" id="mwAjE">}</span>