Two Swaps
October 23, 2015
Today we have one of those tricky interview questions that are easy once you know the answer:
You are given an array of three elements, in some random order. You must sort the array into increasing order, but may only use two swaps. How can you do it?
Your task is to write a program that sorts a three-element array with only two swaps. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
If we put the outermost elements in order first, we then just need one more swap to position the centre element:
In Common Lisp; we use symbol-macrolet to define aliases to the places
in the vector:
Here’s a minimal version that only does one true swap, the rest of the sorting is done when copying the data back from local registers to memory:
This reflects what happens with real processors where we need to copy from memory before processing (and copy back afterwards). Here’s an equivalent function written as inline ARM assembler (just been playing with a new Raspberry Pi). Makes nice use of conditional instructions (eg. “movgt” means do a move but only when the last comparison was greater):