This is a kind of bubble sort algorithm, but it is not a sort algorithm unless an extra operation is added. It is less efficient than the bubble sort. But it gives a little bit practical algorithm to solve the 15 puzzle.
We shall explain it by an example of sorting the array of type int, a[0], a[1], ..., a[N-1] in non-decreasing order.
Algorithm. If there is an i with i ≥ 2 and "a[i-2] > a[i] or a[i-1] > a[i]", then let a[i] leap the two elements a[i-2] and a[i-1].
The code of the operation is as the following.
if (a[i-2] > a[i] || a[i-1] > a[i]) {
int tmp = a[i];
a[i] = a[i-1], a[i-1] = a[i-2], a[i-2] = tmp;
}
It is well-known that the inversion number inv of a[ ] is calculated by the following code.
int inv = 0;
for (j = 1; j < N; j++) {
for (i = 0; i < j; i++) {
if (a[i] > a[j]) {
inv++;
}
}
}
It can be calculated by the following code, too.
int inv2 = 0;
for (j = 1; j < N; j++) {
n = 0;
for (i = 0; i < j; i++) {
if (a[i] > a[j]) {
n++;
}
}
inv2 += n;
}
The operation above does not increase the inversion number. If a[ ] is a permutation of 0, 1, 2, ..., N-1, then the operation above does not change the inversion number modulo 2. Therefore, it is not a sort algorithm.
Definition. The triple inversion number trinv of a[ ] is calculated by the following code.
int trinv = 0;
for (k = 2; k < N; k++) {
for (j = 1; j < k; j++) {
for (i = 0; i < j; i++) {
if (a[i] <= a[k] && a[j] > a[k] || a[i] > a[k] && a[j] <= a[k]) {
trinv++;
}
}
}
}
It can be calculated by the following code, too.
int trinv = 0;
for (k = 2; k < N; k++) {
int less_equal = 0;
int greater = 0;
for (j = 0; j < k; j++) {
if (a[j] <= a[k]) {
less_equal++;
} else {
greater++;
}
}
trinv += less_equal * greater;
}
A sample program testing the above. The array is initialized by the rand() function. The seed is the current time.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 32
int a[N];
int main() {
int i, j, k, n;
int inv, inv2, trinv, trinv2;
srand((unsigned)time(NULL));
for (i = 0; i < N; i++) {
a[i] = rand() % 16;
}
for (i = 0; i < N; i++) {
printf("%x", a[i]);
}
putchar('\n');
inv = 0;
for (j = 1; j < N; j++) {
for (i = 0; i < j; i++) {
if (a[i] > a[j]) {
inv++;
}
}
}
printf("%d ", inv);
inv2 = 0;
for (j = 1; j < N; j++) {
n = 0;
for (i = 0; i < j; i++) {
if (a[i] > a[j]) {
n++;
}
}
inv2 += n;
}
printf("%d ", inv2);
trinv = 0;
for (k = 2; k < N; k++) {
for (j = 1; j < k; j++) {
for (i = 0; i < j; i++) {
if (a[i] <= a[k] && a[j] > a[k] || a[i] > a[k] && a[j] <= a[k]) {
trinv++;
}
}
}
}
printf("%d ", trinv);
trinv2 = 0;
for (k = 2; k < N; k++) {
int less_equal = 0;
int greater = 0;
for (j = 0; j < k; j++) {
if (a[j] <= a[k]) {
less_equal++;
} else {
greater++;
}
}
trinv2 += less_equal * greater;
}
printf("%d ", trinv2);
putchar('\n');
}
Proposition. If the operation above does not decrease the inversion number, then it decreases the triple inversion number.
Proof. These are two cases: (i) a[i-2] < a[i] && a[i-1] > a[i], and (ii) a[i-2] > a[i] && a[i-1] < a[i].
Case (i). Put as follows.
Recall the second definition of the triple inversion number. The contribution of the three elements a[i-2], a[i-1], a[i] to the triple inversion number before the operation is equal to:
After the operation, it is equal to:
"before" - "after" is equal to - Sle + Mle + Mgt + 1 - Lgt. Since Mle + Mgt is equal to j-3 and Sle + Lgt is equal to or less than j-3, therefore it is positive.
Case (ii). Put as follows.
After the operation, it is equal to:
The rest is same as in case (i). [Q.E.D.]
Therefore, the operation above decreases the inversion number or the triple inversion number. Hence, we cannot apply this operation forever. If the inversion number is positive, then we can apply the operation unless the case the inversion number is equal to 1 and a[0] > a[1].
The following is a sample program of this sort algorithm.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 64
int a[N];
int main() {
int i, j, k, n;
int inv, trinv;
srand((unsigned)time(NULL));
for (i = 0; i < N; i++) {
a[i] = rand() % 16;
}
while (1) {
inv = 0;
for (j = 1; j < N; j++) {
for (i = 0; i < j; i++) {
if (a[i] > a[j]) {
inv++;
}
}
}
trinv = 0;
for (k = 2; k < N; k++) {
for (j = 1; j < k; j++) {
for (i = 0; i < j; i++) {
if (a[i] <= a[k] && a[j] > a[k] || a[i] > a[k] && a[j] <= a[k]) {
trinv++;
}
}
}
}
printf("inv. %5d: 3inv. %5d: ", inv, trinv);
for (i = 0; i < N; i++) {
printf("%x", a[i]);
}
putchar('\n');
for (i = N - 1; i >= 2; i--) {
if (a[i-2] > a[i] || a[i-1] > a[i]) {
int tmp = a[i];
a[i] = a[i-1], a[i-1] = a[i-2], a[i-2] = tmp; break; /* for */
}
}
if (i == 1) {
break; /* while */
}
}
}
For the relation to the 15 puzzle, see «a simple proof on the solvability of the 15 puzzle (and the extended ones)».