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.

Pages: 1 2

3 Responses to “Two Swaps”

  1. matthew said

    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)
    
  2. Informatimago said

    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))
    
  3. matthew said

    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");
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: