Two Swaps
October 23, 2015
This is the kind of brain-teaser interview question that I really don’t like. The answer is simple: use two comparisons to find the smallest item, and swap it into the first position of the array. Then use a third comparison on the two remaining elements and swap if necessary. The “trick” is that it is normal to think about reducing comparisons rather than reducing swaps, and your mind is “thinking comparisons” instead of “thinking swaps,” at least if your mind works the same way as my mind. Here’s the program:
(define (two-swaps a b c)
(define-syntax swap!
(syntax-rules ()
((swap! x y)
(let ((z x))
(set! x y)
(set! y z)))))
(if (< a b)
(if (< a c)
(swap! a a)
(swap! a c))
(if (< b c)
(swap! a b)
(swap! a c)))
(if (< b c)
(swap! b b)
(swap! b c))
(list a b c))
Note that swap! must be a macro. We did swaps in the two cases where nothing gets swapped, just to show that the algorithm always performs three comparisons and two swaps regardless of the input. Here are the six possible inputs:
> (two-swaps 1 2 3) (1 2 3) > (two-swaps 1 3 2) (1 2 3) > (two-swaps 2 1 3) (1 2 3) > (two-swaps 2 3 1) (1 2 3) > (two-swaps 3 1 2) (1 2 3) > (two-swaps 3 2 1) (1 2 3)
You can run the program at http://ideone.com/PX18Ar.
If we put the outermost elements in order first, we then just need one more swap to position the centre element:
def swap(a,i,j): a[i],a[j] = a[j],a[i] def sort3(a): if a[0] > a[2]: swap(a,0,2) if a[0] > a[1]: swap(a,0,1) elif a[1] > a[2]: swap(a,1,2) def unsort3(a,n): swap(a,0,n%3) n //= 3 swap(a,1,1+n%2) for i in range(0,6): a = [1,2,3] unsort3(a,i) b = list(a) sort3(a) print(b,a)In Common Lisp; we use symbol-macrolet to define aliases to the places
in the vector:
(defun two-swap-sort-vector-3 (v) (symbol-macrolet ((a (aref v 0)) (b (aref v 1)) (c (aref v 2))) (if (< a c) (if (< a b) (if (< b c) ;; < ;; < < ;; 1 2 3 --> 0 nil ;; < < ;; < > < < ;; 1 3 2 --> 1 2 3 (rotatef b c)) ;; < < ;; > < < < ;; 2 1 3 --> 1 2 3 (rotatef a b)) (if (< a b) ;; > < < ;; < > > < < < ;; 2 3 1 --> 2 1 3 --> 1 2 3 (progn (rotatef b c) (rotatef a b)) (if (< b c) ;; > < < ;; > < < > < < ;; 3 1 2 --> 1 3 2 --> 1 2 3 (progn (rotatef a b) (rotatef b c)) ;; > < ;; > > < < ;; 3 2 1 --> 1 2 3 (rotatef a c)))) v))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:
static inline void sort3(int &A, int &B, int &C) { int a = A, c = C; if (a > c) { int t = a; a = c; c = t; // swap } int b = B; if (a > b) { A = b; B = a; C = c; } else { A = a; if (b > c) { B = c; C = b; } else { C = c; // B is unchanged } } }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):
static inline void sort3(int &A, int &B, int &C) { int a,b,c; // Temporary registers asm volatile ("ldr %[a], %[A]\r\n" "ldr %[c], %[C]\r\n" "cmp %[a], %[c]\r\n" "movgt %[b], %[a]\r\n" // Use b as temporary "movgt %[a], %[c]\r\n" "movgt %[c], %[b]\r\n" "ldr %[b], %[B]\r\n" // Now get the real b "cmp %[a], %[b]\r\n" "strgt %[b], %[A]\r\n" "strgt %[a], %[B]\r\n" "strgt %[c], %[C]\r\n" "bgt L%=\r\n" // Auto generated label "cmp %[b], %[c]\r\n" "str %[a], %[A]\r\n" "strgt %[c], %[B]\r\n" "strgt %[b], %[C]\r\n" "strle %[c], %[C]\r\n" "L%=:" : [A]"+m"(A), [B]"+m"(B), [C]"+m"(C), [a]"=&r"(a), [b]"=&r"(b), [c]"=&r"(c) :: "cc"); }