# How to sort an array using minimum number of writes?

My friend was asked a question in his interview:

The interviewer gave him an array of unsorted numbers and asked him to sort. The restriction is that the number of writes should be minimized while there is no limitation on the number of reads.

• The correct answer is to use cycle sort. Every permutation (sorted or unsorted arrangement) is a product of cycles. You can go through and rotate the cycles one element to get everything in its proper place. This requires exactly the minimal number of writes, which is even better than selection sort, which swaps elements out unnecessarily, writing nearly twice as many times as cycle sort. See my answer below for horribly inefficient code, a link to better code, and a link to Wikipedia for an explanation of cycle notation. Oct 4, 2010 at 4:06
• For a clearer, better-thought-out, and well-tested version of the cycle sort algorithm than below, see en.wikipedia.org/wiki/Cycle_sort Oct 4, 2010 at 20:22

Selection sort is not the right algorithm here. Selection sort will swap values, making up to two writes per selection, giving a maximum of 2n writes per sort.

An algorithm that's twice as good as selection sort is "cycle" sort, which does not swap. Cycle sort will give a maximum of n writes per sort. The number of writes is absolutely minimized. It will only write a number once to its final destination, and only then if it's not already there.

It is based on the idea that all permutations are products of cycles and you can simply cycle through each cycle and write each element to its proper place once.

``````import java.util.Random;
import java.util.Collections;
import java.util.Arrays;

public class CycleSort {
public static final <T extends Comparable<T>> int cycleSort(final T[] array) {
int writes = 0;

// Loop through the array to find cycles to rotate.
for (int cycleStart = 0; cycleStart < array.length - 1; cycleStart++) {
T item = array[cycleStart];

// Find where to put the item.
int pos = cycleStart;
for (int i = cycleStart + 1; i < array.length; i++)
if (array[i].compareTo(item) < 0) pos++;

// If the item is already there, this is not a cycle.
if (pos == cycleStart) continue;

// Otherwise, put the item there or right after any duplicates.
while (item.equals(array[pos])) pos++;
{
final T temp = array[pos];
array[pos] = item;
item = temp;
}
writes++;

// Rotate the rest of the cycle.
while (pos != cycleStart) {
// Find where to put the item.
pos = cycleStart;
for (int i = cycleStart + 1; i < array.length; i++)
if (array[i].compareTo(item) < 0) pos++;

// Put the item there or right after any duplicates.
while (item.equals(array[pos])) pos++;
{
final T temp = array[pos];
array[pos] = item;
item = temp;
}
writes++;
}
}
return writes;
}

public static final void main(String[] args) {
final Random rand = new Random();

final Integer[] array = new Integer[8];
for (int i = 0; i < array.length; i++) { array[i] = rand.nextInt(8); }

for (int iteration = 0; iteration < 10; iteration++) {
System.out.printf("array: %s ", Arrays.toString(array));
final int writes = cycleSort(array);
System.out.printf("sorted: %s writes: %d\n", Arrays.toString(array), writes);
Collections.shuffle(Arrays.asList(array));
}
}
}
``````

A few example runs :

```array: [3, 2, 6, 1, 3, 1, 4, 4] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6
array: [1, 3, 4, 1, 3, 2, 4, 6] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 4
array: [3, 3, 1, 1, 4, 4, 2, 6] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6
array: [1, 1, 3, 2, 4, 3, 6, 4] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6
array: [3, 2, 3, 4, 6, 4, 1, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7
array: [6, 2, 4, 3, 1, 3, 4, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 6
array: [6, 3, 2, 4, 3, 1, 4, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 5
array: [4, 2, 6, 1, 1, 4, 3, 3] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7
array: [4, 3, 3, 1, 2, 4, 6, 1] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7
array: [1, 6, 4, 2, 4, 1, 3, 3] sorted: [1, 1, 2, 3, 3, 4, 4, 6] writes: 7
```
```array: [5, 1, 2, 3, 4, 3, 7, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 5
array: [5, 1, 7, 3, 2, 3, 4, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 6
array: [4, 0, 3, 1, 5, 2, 7, 3] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 8
array: [4, 0, 7, 3, 5, 1, 3, 2] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7
array: [3, 4, 2, 7, 5, 3, 1, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7
array: [0, 5, 3, 2, 3, 7, 1, 4] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 6
array: [1, 4, 3, 7, 2, 3, 5, 0] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7
array: [1, 5, 0, 7, 3, 3, 4, 2] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7
array: [0, 5, 7, 3, 3, 4, 2, 1] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 4
array: [7, 3, 1, 0, 3, 5, 4, 2] sorted: [0, 1, 2, 3, 3, 4, 5, 7] writes: 7
```
• Does it work for : `{3,12,5,8,11,7,9,2}` , I tried the code and it's not working ! Oct 15, 2013 at 18:47
• I got `array: [3, 12, 5, 8, 11, 7, 9, 2] sorted: [2, 3, 5, 7, 8, 9, 11, 12] writes: 7` Oct 21, 2013 at 23:04
• Do the writes to cycleStart and i and pos not count as writes? If so, why not? Apr 15, 2017 at 12:23
• @user2108462 All writes are counted, which can be verified by debug printing (`System.out.print(“write,”);`j right after an element in `array` is assigned to and debug printing (`System.out.println(“counted”);`) right after `writes` is incremented. Jun 5, 2018 at 19:25
• Although we don’t need to swap like selection sort, but every time we need to write to a temp variable, isn’t it equivalent to a swap, but we just didn’t write to the original array. So why is write count reduced?
– HKIT
Jul 31, 2022 at 14:29

If the array is shorter (ie less than about 100 elements) a Selection sort is often the best choice if you also want to reduce the number of writes.

From wikipedia:

Another key difference is that selection sort always performs Θ(n) swaps, while insertion sort performs Θ(n2) swaps in the average and worst cases. Because swaps require writing to the array, selection sort is preferable if writing to memory is significantly more expensive than reading. This is generally the case if the items are huge but the keys are small. Another example where writing times are crucial is an array stored in EEPROM or Flash. There is no other algorithm with less data movement.

For larger arrays/lists Quicksort and friends will provide better performance, but may still likely need more writes than a selection sort.

If you're interested this is a fantastic sort visualization site that allows you to watch specific sort algorithms do their job and also "race" different sort algorithms against each other.

• +1 - Selection sort is the answer. There is no other possible sort that can have as few writes as this, because if you do not place the k'th item in the k'th spot, you'll have an extra write to do to get it in the right spot later. Sep 2, 2010 at 14:43
• @Rex Other answers may have fewer reads, and the same number of writes. Sep 2, 2010 at 16:05
• Selection sort is not the best. Selection sort swaps, which means that before it writes element A to its correct place, it reads element B from that place and writes it to where element A used to be, even if that's not where element B is supposed to end up. This results in unnecessary writes! See my answer for a horribly time-inefficient sort that nonetheless makes absolutely no unnecessary writes. Oct 4, 2010 at 3:30
• Selection sort requires writes to the loop counter, does it not? Wouldn't that make it O(n^2) writes? Apr 15, 2017 at 12:26

You can use a very naive algorithm that satisfies what you need.

The algorithm should look like this:

``````i = 0

do
search for the minimum in range [i..n)
swap a[i] with a[minPos]
i = i + 1
repeat until i = n.
``````

The search for the minimum can cost you almost nothing, the swap costs you 3 writes, the i++ costs you 1..

This is named selection sort as stated by ash. (Sorry, I didn't knew it was selection sort :( )

• Also known as selection sort. See my answer.
– Ash
Sep 2, 2010 at 3:00
• Yes, after posted my answer I took a look at yours and noticed it was the same thing that I've posted. Sorry for that :( Sep 2, 2010 at 3:03
• No problems, nice clear example. Check out the 2nd link in my answer, very cool (to me at least).
– Ash
Sep 2, 2010 at 3:05
• Searching for the minimum in range [i..n) would require writes to a loop counter wouldn't it? Apr 15, 2017 at 12:25

One option for large arrays is as follows (assuming n elements):

1. Initialize an array with n elements numbered 0..n-1
2. Sort the array using any sorting algorithm. As the comparison function, compare the elements in the input set with the corresponding numbers (eg, to compare 2 and 4, compare the 2nd and 4th elements in the input set). This turns the array from step 1 into a permutation that represents the sorted order of the input set.
3. Iterate through the elements in the permutation, writing out the blocks in the order specified by the array. This requires exactly n writes, the minimum.

To sort in-place, in step 3 you should instead identify the cycles in the permutation, and 'rotate' them as necessary to result in sorted order.

• This is nice and simple, but one improvement: if some items are already in their final places, you don't have to overwrite them with themselves, so you can actually make less than n writes in some cases. Oct 4, 2010 at 6:58

The ordering I meant in O(n) is like the selection sort(the previous post) useful when you have a small range of keys (or you are ordering numbers between 2 ranges)

If you have a number array where numbers will be between -10 and 100, then you can create an array of 110 and be sure that all numbers will fit in there, if you consider repeated numbers the idea is the same, but you will have lists instead of numbers in the sorted array

the pseudo-idea is like this

``````N: max value of your array
tosort //array to be sorted
sorted = int[N]

for i = 0 to length(tosort)
do
sorted[tosort[i]]++;
end

finalarray = int[length(tosort)]

k = 0
for i = 0 to N
do
if ( sorted[i] > 0 )
finalarray[k] = i
k++;
endif
end
``````

finalarray will have the final sorted array and you will have o(N) write operations, where N is the range of the array. Once again, this is useful when using keys inside a specific range, but perhaps its your case.

Best regards and good luck!
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}