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

Navigation

Tagged as

Recent posts

Twitter's overrated dissemination capacity
(2023-04-02)

The hypocritical call to pause giant AI (2023-03-30)

AI deforests the knowledge’s ecosystem (2023-03-16)

How I fixed git-grep macOS UTF-8 support (2022-10-12)

The sorry state of software quality (2022-03-10)

Rather than alchemy, methodical troubleshooting (2021-11-27)

The Evolution of the Unix System Architecture (2021-06-18)

Reviving the 1973 Unix text to voice translator (2021-01-02)

Fast database UPDATE/DELETE operations (2020-12-10)

Raspberry Pi 400 vs ZX Spectrum (2020-11-02)

The hypocritical call to pause giant AI (2023-03-30)

AI deforests the knowledge’s ecosystem (2023-03-16)

How I fixed git-grep macOS UTF-8 support (2022-10-12)

The sorry state of software quality (2022-03-10)

Rather than alchemy, methodical troubleshooting (2021-11-27)

The Evolution of the Unix System Architecture (2021-06-18)

Reviving the 1973 Unix text to voice translator (2021-01-02)

Fast database UPDATE/DELETE operations (2020-12-10)

Raspberry Pi 400 vs ZX Spectrum (2020-11-02)

Last modified: Thursday, November 17, 2005 10:01 am

Unless otherwise expressly stated, all original material on this page created by Diomidis Spinellis is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.