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
```

```
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);
```

```
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);
```

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

Read and post comments, or share through