Sort Four

April 11, 2017

Today’s exercise involves sorting:

Write a program that takes exactly four items as input and returns them in sorted order.

Your task is to write a program that sorts exactly four items; can you do it using only five comparisons? 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.

Advertisements

Pages: 1 2

10 Responses to “Sort Four”

  1. Milbrae said

    Like this?

    >>> def sort4(a, b, c, d):
    	return sorted([a, b, c, d])
    
    >>> print (sort4(2, 4, 1, 3))
    [1, 2, 3, 4]
    
  2. Pavel Tumilovich said

    Two versions using Clojure:

    (defn four-sort1
      [a b c d]
      (sort [a b c d]))
    
    (defn swap
      [x y]
      [(min x y) (max x y)])
    
    (defn four-sort2
      [a b c d]
      (let [[x y] (swap a b)
            [z m] (swap c d)
            [l y2] (swap x z)
            [z2 h] (swap y m)
            [i1 i2] (swap y2 z2)]
        [l i1 i2 h]))
    
  3. Jussi Piitulainen said

    Here’s a depth-3 Parallel Fouring Machine program, P, tested with an interpreter written in Python (see below). Parallel Fouring Machine programs are binary trees of commands that act on four registers so that each command sorts both the two indicated registers and the two complementary registers, in parallel, and they continue to the left branch if either pair was swapped, else to right.

    from itertools import permutations
    P = ((0, 1), ((0, 2), ((0, 3), (), ()),
                          ((0, 3), (), ())),
                 ((0, 2), ((0, 3), (), ()),
                          ((0, 3), (), ())))
    
    for D in permutations(range(4)):
        print(D, '=>', F(P, D))
    else:
        print((3,1,4,1), '=>', F(P, (3,1,4,1)))
    

    Clearly this program P always executes the same three parallel comparisons, so it corresponds to six sequential comparisons. Is off by one close enough? (I was not able to generate even all depth-4 Sequential Fouring Machine programs, let alone enough of the required depth-5. It was a combinatorial explosion, and I had no ideas to prune the search space. So I went on to discover the Parallel Fouring Machine instead. For the Journal of Negative Results, maybe.)

    Here’s the interpreter, F, in Python.

    def F(P, D):
        while P: P, D = op(P, D)
        return D
    
    # complementary pairs
    comp = { (0,1) : (2,3), (0,2) : (1,3), (0,3) : (1,2) }
    
    def op(P, D):
        '''Sorts both the pair indicated by the top opcode, and the
        complementary pair. Continues to the left branch if either pair
        was swapped, else continues to the right branch.'''
    
        O, L, R = P
        j, k = O
        u , w = comp[O]
        S = {}
        if D[j] > D[k]: S.update({j:k, k:j})
        if D[u] > D[w]: S.update({u:w, w:u})
        if S:
            return L, tuple(D[S.get(t, t)] for t in range(4))
        else:
            return R, D
    

    There are only 36 depth-3 Parallel Fouring Machine programs that always sort the four registers. Some might contain the clue to the 5-step sequential sorting problem, if they were investigated more closely.

  4. For such a small number of items to sort, we will avoid memory writes, by expanding the decision tree, and keeping the four elements in registers until it’s time to store them in the resulting sorted vector. Between 4 and 5 tests are needed to reach the leaves of the decision tree (on average for equiprobable permutations: 4.5).

    
    ;; Common Lisp
    
    (defun sort-4 (lessp a b c d)
      (if (funcall lessp a b)
          (if (funcall lessp c d)
              (if (funcall lessp a c)
                  (if (funcall lessp b d)
                      (if (funcall lessp b c)
                          (vector a b c d) 
                          (vector a c b d))
                      (vector a c d b))
                  (if (funcall lessp b d)
                      (vector c a b d)
                      (if (funcall lessp a d)
                          (vector c a d b) 
                          (vector c d a b))))
              (if (funcall lessp a d)
                  (if (funcall lessp b c)
                      (if (funcall lessp b d)
                          (vector a b d c) 
                          (vector a d b c)) 
                      (vector a d c b)) 
                  (if (funcall lessp b c)
                      (vector d a b c)
                      (if (funcall lessp a c)
                          (vector d a c b) 
                          (vector d c a b)))))
          (if (funcall lessp c d)
              (if (funcall lessp b c)
                  (if (funcall lessp a d)
                      (if (funcall lessp a c)
                          (vector b a c d) 
                          (vector b c a d))
                      (vector b c d a)) 
                  (if (funcall lessp a d)
                      (vector c b a d)
                      (if (funcall lessp b d)
                          (vector c b d a) 
                          (vector c d b a))))
              (if (funcall lessp b d)
                  (if (funcall lessp a c)
                      (if (funcall lessp a d)
                          (vector b a d c) 
                          (vector b d a c)) 
                      (vector b d c a)) 
                  (if (funcall lessp a c)
                      (vector d b a c)
                      (if (funcall lessp b c)
                          (vector d b c a) 
                          (vector d c b a)))))))
    
    (assert (every (lambda (v)
                     (equalp (sort-4 (function <) (aref v 0) (aref v 1) (aref v 2) (aref v 3))
                             #(1 2 3 4)))
                   '(#(1 2 3 4) 
                     #(2 1 3 4) 
                     #(2 3 1 4) 
                     #(2 3 4 1) 
                     #(1 3 2 4) 
                     #(3 1 2 4) 
                     #(3 2 1 4) 
                     #(3 2 4 1) 
                     #(1 3 4 2) 
                     #(3 1 4 2) 
                     #(3 4 1 2) 
                     #(3 4 2 1) 
                     #(1 2 4 3) 
                     #(2 1 4 3) 
                     #(2 4 1 3) 
                     #(2 4 3 1) 
                     #(1 4 2 3) 
                     #(4 1 2 3) 
                     #(4 2 1 3) 
                     #(4 2 3 1) 
                     #(1 4 3 2) 
                     #(4 1 3 2) 
                     #(4 3 1 2) 
                     #(4 3 2 1))))
    
  5. Mike said
    def sort4(a,b,c,d):
        if b < a: a,b = b,a
        if d < c: c,d = d,c
        
        # at this point, we know the min value is either a or c
        # and the max value is either b or d
        
        if c < a: a,c = c,a
        if d < b: b,d = d,b
            
        # now, the min is a and the max is b
        # all that remains is to sort the middle two values
        
        if c < b: b,c = c,b
            
        return a,b,c,d
    
  6. Jussi Piitulainen said

    @Mike, I should have had the courage :) Here’s an interpreter for a simpler Fouring Machine whose six opcodes just sort a pair of registers without branching anywhere. A program is a sequence of opcodes.

    def F(P, D):
        for O in P: D = op(O, D)
        return D
    
    def op(O, D):
        j, k = O
        S = {j:k, k:j} if D[j] > D[k] else {}
        return tuple(D[S.get(t, t)] for t in range(4)) if S else D
    

    It’s a combinatorial piece of cake to generate a 5-command solution now. There are 12. Here’s one, which turns out to be precisely your (Mike’s) solution.

    from itertools import permutations
    P = ((0, 1), (2, 3), (0, 2), (1, 3), (1, 2))
    for D in permutations(range(4)):
        print(D, '=>', F(P, D))
    else:
        print((3,1,4,1), '=>', F(P, (3,1,4,1)))
    

    One could write a compiler to get a Python (or Scheme (or C (or why not some assembler))) program.

  7. Jussi Piitulainen said

    This is Scheme.

    ;; library - should be imported from a library
    
    (define (fold op init args)
      (if (pair? args)
          (fold op (op init (car args)) (cdr args))
          init))
    
    (define (pipe . ops)
      (define (pipe op then)
        (lambda args
          (call-with-values
              (lambda () (apply op args))
            then)))
      (fold pipe values ops))
    
    ;; program : 3 1 4 1 => 1 1 3 4
    
    (define sort4
      (let-syntax ((on (syntax-rules (=>)
                         ((on cond in => out)
                          (lambda in (if cond (values . out) (values . in)))))))
        (let ((ab (on (< b a) (a b c d) => (b a c d)))
              (ac (on (< c a) (a b c d) => (c b a d)))
              (bc (on (< c b) (a b c d) => (a c b d)))
              (bd (on (< d b) (a b c d) => (a d c b)))
              (cd (on (< d c) (a b c d) => (a b d c))))
          (pipe ab cd ac bd bc))))
    
    ;; test
    
    (call-with-values (lambda () (sort4 3 1 4 1)) (pipe list display)) (newline)
    (call-with-values (lambda () (sort4 1 4 1 5)) (pipe list display)) (newline)
    (call-with-values (lambda () (sort4 4 1 5 9)) (pipe list display)) (newline)
    (call-with-values (lambda () (sort4 1 5 9 2)) (pipe list display)) (newline)
    (call-with-values (lambda () (sort4 5 9 2 6)) (pipe list display)) (newline)
    
  8. This scheme version is nice, but scheme compilers won’t be able to avoid the fifth comparison, when it’s useless. You will get exactly 5 comparison, why the Common Lisp expanded version has 4.5 comparisons on average.

  9. MUMP V1:

    SORT4 ;New routine
    1 (N1,N2,N3,N4) ;
    N ARR,I
    ; When the numbers are placed into the array “ARR”, they are automatically placed in sorted order
    F I=N1,N2,N3,N4 S ARR(I)=””
    ; Write the numbers starting at the least
    S I=”” F S I=$O(ARR(I)) Q:I=”” W !,I
    Q

    MCL> D 1^SORT4(99,87,65,7)

    7
    65
    87
    99

  10. Daniel said

    Here’s a solution in x86 assembly.

    /* sort4.s */
    
    .globl sort4
    
    # void sort4(int* array);
    sort4:
      pushl %ebp
      movl %esp, %ebp
      # Save non-volatile registers
      pushl %ebx
      pushl %edi
      
      movl 8(%ebp), %eax
      
      movl (%eax), %ebx
      movl 4(%eax), %ecx
      movl 8(%eax), %edx
      movl 12(%eax), %edi
    
    cmp1:
      cmpl %ebx, %ecx
      jge cmp2
      xchgl %ebx, %ecx
    cmp2:
      cmpl %edx, %edi
      jge cmp3
      xchgl %edx, %edi
    cmp3:
      cmpl %ebx, %edx
      jge cmp4
      xchgl %ebx, %edx
    cmp4:
      cmpl %ecx, %edi
      jge cmp5
      xchgl %ecx, %edi
    cmp5:
      cmpl %ecx, %edx
      jge done
      xchgl %ecx, %edx
    
    done:
      movl %ebx, (%eax)
      movl %ecx, 4(%eax)
      movl %edx, 8(%eax)
      movl %edi, 12(%eax)
    
      # Restore non-volatile registers
      popl %edi
      popl %ebx
    
      movl %ebp, %esp
      popl %ebp
      ret
    

    Here’s a C program that calls the function.

    /* main.c */
    
    #include <stdio.h>
    
    void sort4(int* array);
    
    static void print_array(int* array) {
      printf("[");
      for (int i = 0; i < 4; ++i) {
        if (i > 0) printf(", ");
        printf("%d", array[i]);
      }
      printf("]");
    }
    
    int main(int argc, char* argv[]) {
      int array[] = {4, 7, 1, 6};
    
      printf("array: ");
      print_array(array);
      printf("\n");
    
      sort4(array);
    
      printf("sorted: ");
      print_array(array);
      printf("\n");
    }
    

    Example usage:

    $ as --32 -o sort4.o sort4.s
    $ gcc -m32 main.c sort4.o -o main
    $ ./main
    

    Output:

    array: [4, 7, 1, 6]
    sorted: [1, 4, 6, 7]
    

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: