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.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: