October 23, 2015 9:00 AM
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.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
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)By matthew on October 23, 2015 at 9:51 AM
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))By Informatimago on October 23, 2015 at 8:43 PM
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"); }By matthew on October 23, 2015 at 10:19 PM