How to sort an array using minimum number of writes?

Question

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.

Answer 1

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

Answer 2

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 Θ(n²) 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.