Sorting on two-dimensional processor arrays
2d odd-even transposition sort
The simplest algorithm for sorting two-dimensional arrays is 2d odd-even transposition sort. Unfortunately, it has a time complexity of Θ(n2), which is slow.
The idea of odd-even transposition sort is generalized to two-dimensional arrays in a straightforward way. Figure 1 shows the two steps of one-dimensional odd-even transposition sort that are repeated in alternating order.
|Figure 1: One-dimensional odd-even transposition sort|
In two-dimensional odd-even transposition sort, the elements are not just compared with their right and left neighbours, but also with their upper and lower neighbours. The sorting direction in the array is snake-like. Figure 2 shows the four steps of two-dimensional odd-even transposition sort that are repeated in round-robin order.
|Figure 2: Two-dimensional odd-even transposition sort|
In the following algorithm, with oets step a step of odd-even transposition sort is denoted.
|Algorithhm 2d odd-even transposition sort|
|Input:||unsorted n × n-array|
|Output:||the array sorted in snake-like order|
The sorting direction of the rows must be alternating, i.e. even rows from left to right and odd rows from right to left.
In the following simulation of algorithm 2d odd-even transposition sort the input is an array of 0's (white) and 1's (gray). The simulation shows the crucial point of the algorithm: It sorts a random input of 0's and 1's remarkably fast (click on the array to start). However, in the worst case, it is slow (click again). Actually, the time complexity in the worst case is Θ(n2), due to a behavior known as sand dune effect. The sand dune effect occurs also with random inputs of values drawn from a larger set than just the two values 0 and 1 (click again).
|Next: [Shearsort] or|
|H.W. Lang Hochschule Flensburg email@example.com Impressum © Created: 29.11.2004 Updated: 05.06.2016|