Joseph K. Myers

Monday, August 8, 2005

Iterative methods for sorting

An iterative method is an algorithm which need not produce sorted order within a single step. However, by repeatedly applying the same algorithm a finite number of times, sorted order can be obtained.

An example is one which is similar to shell sort.

/* pairsort.js */

function pairsort(a) {

var records = [], ncompare = 0, nswap = 0, recswaps = [], i;

function compare(x, y) {
ncompare++;
return x < y;
}

function swap(i, j) {
var x = a[i];
a[i] = a[j];
a[j] = x;
recswaps[nswap++] = [i,j];
/* it's important to tell you that
these records are later used,
and the assumption is made that
a record [i, j] has i < j. */
}

function pairsort0(start, end) {
var i, j;
for (i=start, j=end-1; i<j; i++,j--) {
records[records.length] = [i, j];
if (compare(a[j], a[i]))
swap(i, j);
}
j++;
if (j-start > 1)
pairsort0(start, j);
if (end-i > 1)
pairsort0(i, end);
}

pairsort0(0, a.length);

records.nswap = nswap;
records.ncompare = ncompare;
records.swaps = recswaps;

var furthestswap = 0;
for (i=0; i<recswaps.length; i++)
if (recswaps[i][1] - recswaps[i][0] > furthestswap)
furthestswap = recswaps[i][1] - recswaps[i][0];

records.furthestswap = furthestswap;

return records;
/* allows us to analyze the sort */
}

For instance, if we take the out-of-order array:

and we apply pairsort to it, the algorithm deterministically applies a set of 24 comparisons (and swaps if necessary) which are shown below.

When we apply the algorithm one time, to apply that set of steps, this is called an iteration. Here is the result of the first iteration.

When we apply precisely the same list of comparisons, the result is here:

Finally, after one more iteration, the array will be entirely in order.

Modeling the problem in a different way

Since for a certain array size N, the steps of this iterative method are precisely determined, it is of interest to know whether any other order of the same steps would also construct a workable iterative algorithm.

It would be very easy to write a function which used not its own algorithm, but a given list of steps, and apply them in the order given. After testing the function, we could then reverse the given order of the steps and examine the results.

/* applysteps.js */

function applysteps(a, rec) {

var ncompare = 0, nswap = 0, i;

function compare(x, y) {
ncompare++;
return x < y;
}

function swap(i, j) {
var x = a[i];
a[i] = a[j];
a[j] = x;
nswap++;
}

for (i=0; i<rec.length; i++)
if (compare(a[rec[i][1]], a[rec[i][0]]))
swap(rec[i][0], rec[i][1]);

rec.nswap = nswap;
rec.ncompare = ncompare;

}

Now we apply the same steps to the same input.

The result is identical, and the two iterations which follow are also the same, and likewise will conclude with the array being sorted. Thus, we know that our step-application function works.

Making the modification

Now what happens if the order of the steps is reversed? We will apply the same 24 steps, but apply them in the opposite order.

As we see, the result is also an iterative method for sorting the array. We can see that this one happens to use more iterations, four total, to sort the array.

When we generalize this idea, finding the optimal algorithm for sorting using iterative methods becomes an inverse problem of rearranging the starting product (the fixed set of steps) of any initial iterative method into a more efficient method.

For instance, each step of the method applied has a certain level of "depth" (level of recursion) when it is applied. If we rearranged the order of steps so that those with higher depth were applied first, this would be largely the opposite of our original algorithm. This is what we tried to do by reversing the order of steps.

Now, if we randomly reorganize the steps, we can see what happens:

We can do it again, making more changes, and see what happens:

The reasons this function shows these properties are that exchanges only bring out-of-order elements with respect to each other (a[j] < a[i], where j > i) into order with respect to each other, and if no exchanges are made, then the array is in order. This latter criterion means that it is an overall exhaustive comparison--meaning that if every subcomparison evaluates to be true, then the array must be in order.

The simplest exhaustive comparison which shows that an array is in order takes n-1 steps, and compares all elements to element following themselves.

But using this form of comparsion as the basis for an iterative method (exchanging elements next to each other if they are out of order) takes a very large amount of time to produce sorted order.

Enhancing efficiency by eliminating unneeded steps

Now we analyze the iterations of the original algorithm. It is easy to make the observation that one iteration is sufficient to guarantee that the smallest element finds the first position. Thereafter, no future iterations need to compare with this element. The same is true for the largest element.

Therefore we decide to enhance our code to record extra data from the sorting process. For each iteration, we will record the swaps which actually occurred, and then we will find the largest distance between swapped elements.

So, we see:

This time, we are suspicious about the true bounds of the furthest swap depending on the number of iterations, and we want to know more than what is available from only one array.

Therefore we will use this as our array.

This, of course, indicates to us a confirmation of an important fact. We do not need to perform an "extra iteration" which has 0 swaps in order to know that our iterations have "converged" upon the sorted order. The iteration in which the furthest swap is equal to 1 has converged the array to sorted order. This saves us about (n log n)/2 steps.

But, now the point is to eliminate even more unnecessary steps.

It looks like the boundary for the second iteration is about n/2. In the first iteration, of course, the first element had a 50% chance of being larger than the last element, and so we cannot be certain of any boundary that is less than n. As a function of the i-th iteration, we could guess that the furthest element has a boundary of n/(2^(i-1)).

We need to do another test.

We observe as a side-note that this iteration actually converged when furthest swap = 2. Perhaps it makes sense that this would occur, because this method is indeed guaranteed to converge instantly when n <= 3. When data shows you an observation you would not have thought of, it is the time for thinking. Ingenuity is greater when assisted in this manner.

It seems directly then that the boundary of the furthest element must be ceil((n+1)/(2^(i-1))). Of course, we actually have to try it before we are convinced that our unproven second guess (our first guess was already shown to be wrong) is correct. But certainly some guess is correct, and we do know for certain that n-2*floor(log(n)/log(2)) is definitely a boundary on the second iteration, because of the same reason that the minimum and maximum are known to be in their proper places by the time that the second iteration is reached.

So then we come up with a way of determining how to choose this model for the problem given each value of N.

Modeling the problem in a deterministic fashion

Thus we are going to create another sorting algorithm which performs all iterations until the array is sorted. We will start out by sorting the original array, and see if the answer is correct.

/* pairsortrep.js */

function pairsortrep(a) {

var records = [], ncompare = 0, nswap = 0, recswaps = [], i;

var bound, iter, lowerbound;

function compare(x, y) {
ncompare++;
return x < y;
}

function swap(i, j) {
var x = a[i];
a[i] = a[j];
a[j] = x;
recswaps[nswap++] = [i,j];
/* it's important to tell you that
these records are later used,
and the assumption is made that
a record [i, j] has i < j. */
}

function pairsort0(start, end) {
var i, j;
for (i=start, j=end-1; i<j; i++,j--) {
if (j-i > bound)
continue;
if (j-i < lowerbound)
continue;
records[records.length] = [i, j];
if (compare(a[j], a[i]))
swap(i, j);
}
j++;
if (j-start > 1)
pairsort0(start, j);
if (end-i > 1)
pairsort0(i, end);
}

iter = 0;

do {
iter++;
bound = Math.ceil((a.length+1)/Math.pow(2, iter-1));
lowerbound = Math.floor(Math.log(bound/2)/Math.log(2));

ncompare = 0, nswap = 0;
recswaps = [];
records = [];

pairsort0(0, a.length);

records.bound = bound;
records.lowerbound = lowerbound;
records.nswap = nswap;
records.ncompare = ncompare;
records.swaps = recswaps;
records.iter = iter;

var furthestswap = 0;
for (i=0; i<recswaps.length; i++)
if (recswaps[i][1] - recswaps[i][0] > furthestswap)
furthestswap = recswaps[i][1] - recswaps[i][0];

records.furthestswap = furthestswap;

displayarray(a, records, 1);

} while (bound > 3);

return records;
/* allows us to analyze the sort */
}

Here is the result of sorting the original array.

Let's do it on the bigger one.