Sorting on two-dimensional processor arrays
A very simple algorithm for sorting two-dimensional arrays is shearsort [SchS 89]. It just sorts the rows and the columns of the array in turn. However, it has a time complexity of Θ(n log(n)), which is not optimal.
|Output:||the array sorted in snake-like order|
Sorting the rows in alternating direction means that even rows are sorted from left to right and odd rows from right to left.
The correctness of shearsort is shown using the 0-1-principle [Knu 73]. The 0-1-principle states the following: If a comparator network sorts every sequence of 0's and 1's, then it sorts every sequence of arbitrary values. Without loss of generality, we may therefore restrict the proof to input sequences consisting of 0's and 1's.
Definition: A row is called clean, if it consists of 0's only or 1's only, otherwise it is called dirty.
Definition: A maximal connected region along the sorting order that starts with a 1 and ends with a 0 is called an unsorted zone.
After sorting the rows in the first step, there are n/2 rows that are sorted from left to right and n/2 rows that are sorted from right to left. When sorting the columns, every two of these rows are combined to at least one clean row (Figure 1). Thus, after the first iteration the array consist of some clean 0-rows, some clean 1-rows and an unsorted zone in between consisting of at most n/2 rows.
In the second iteration, every two rows of the unsorted zone are again combined to at least one clean row. Thus, after the second iteration the unsorted zone consists of at most n/4 rows, and so on.
After log(n) steps, there is at most one dirty row. In the additional last step this row is sorted, and the whole array is sorted.
|Figure 1: Every two rows that are sorted in alternating direction|
are combined to at least one clean row (0's white, 1's gray)
Sorting a row of length n with odd-even transposition sort takes n steps. Since the algorithm performs log(n) iterations, it requires n log(n) steps for row sorting plus n steps for the additional row sorting operation.
In each iteration, the height of the unsorted zone decreases by a factor of 2. This means that the columns contain an unsorted zone of decreasing length. Sorting a column that contains an unsorted zone of length k takes k steps of odd-even transposition sort. Therefore, the algorithm requires
n + n/2 + n/4 + ... + 2 = 2n – 2
steps for column sorting.
Altogether, shearsort has a time complexity of n (log(n) + 3) – 2 Θ(n log(n)) steps.
In the following simulation of shearsort a 32×32-array of 0's and 1's is sorted in row-major order. First, a random input is shown (click to start), and then the worst case is shown (click a second time).
|[Knu 73]||D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)|
|[SchS 89]||I.D. Scherson, S. Sen: Parallel sorting in two-dimensional VLSI models of computation. IEEE Transactions on Computers C-38, 2, 238-249 (1989)|
|H.W. Lang Hochschule Flensburg firstname.lastname@example.org Impressum © Created: 29.11.2004 Updated: 05.06.2016|