blog dds: 2005-11-17 — How to Sort Three Numbers

Quick: how do you sort three numbers in ascending order?

Here is an excerpt from the first page returned by Google.


! -------------------------------------------------------
! This program reads in three INTEGERs and displays them
! in ascending order.
! -------------------------------------------------------

PROGRAM  Order
   IMPLICIT  NONE

   INTEGER  :: a, b, c

   READ(*,*)  a, b, c

   IF (a < b) THEN                 ! a < b here
      IF (a < c) THEN              !   a < c     : a the smallest
         IF (b < c) THEN           !      b < c  : a < b < c
            WRITE(*,*)  a, b, c
         ELSE                      !      c <= b : a < c <= b
            WRITE(*,*)  a, c, b
         END IF
      ELSE                         !   a >= c    : c <= a < b
         WRITE(*,*) c, a, b
      END IF
   ELSE                            ! b <= a here
      IF (b < c) THEN              !   b < c     : b the smallest
         IF (a < c) THEN           !     a < c   : b <= a < c
            WRITE(*,*)  b, a, c
         ELSE                      !     a >= c  : b < c <= a
            WRITE(*,*)  b, c, a
         END IF
      ELSE                         !   c <= b    : c <= b <= a
         WRITE(*,*)  c, b, a
      END IF
   END IF

END PROGRAM  Order

Ouch! Can we do better? Sure, look at this:


int a, b, c;

#define swap(x, y) do {int tmp; tmp = x; x = y; y = tmp; } while (0)

if (b < a) swap(b, a);
if (c < b) swap(c, b);
if (b < a) swap(b, a);

How about sorting four numbers? Here is the solution:


if (b < a) swap(b, a);
if (c < b) swap(c, b);
if (d < c) swap(d, c);
if (b < a) swap(b, a);
if (c < b) swap(c, b);
if (b < a) swap(b, a);

The above code is probably at the limit of being inefficient; for more numbers we should call a sorting function, like the C library's qsort().

Nevertheless, there's still one more question: How do we come up with the above solutions, and how do we know they are correct?

The answer is also simple, and it is called abstract interepretation. We simply write a program that performs the bubble sort algorithm (this is how the above code snippets work), but we substitute the loop's innermost statement with a print statement. Here is the code:


main()
{
	int i, j;
	const int n = 4;

	for (i = 0; i < n - 1; i++)
		for (j = 0; j < n - 1 - i; j++)
			printf("if (%c < %c) swap(%c, %c);\n",
			    'a' + j + 1, 'a' + j, 'a' + j + 1, 'a' + j);
}