I/P: n elements are placed in m*m grid(n=m*m assured).
O/P: Elements sorted in snake like order.
i.e., if grid is like
a11 a12 a13 a1m
a21 a22 a23 a2m
am1 am2 amm
Then aij <aik(for 1≤j<k≤m if i is odd)
if I is even then aij > aik for 1≤j<k≤m
Analogy of the algorithm:
in each step we will have two phases:
1) row sort:
For all rows in parallel,
Sort row in the basis of its row number
if the row number is odd sort it in increasing order(i.e., for 1≤j<k≤m then
aij<aik)
if the row number is even sort in decreasing order(i.e., if 1≤j<k≤m then
aij>aik)
2)column sort:
For all column in paralle,Sort all column in increasing order. For 1≤j<k≤m
aji<aki.
Repeat this procedure log2n times.
a)Formal algorithm:
for k = 1 to log₂(n) do
for each row i in parallel do
if i is even then
sort row i in ascending order (left → right)
else
sort row i in descending order (right → left)
for each column j in parallel do
sort column j in ascending order (top → bottom)
Important point is we can use any algorithm in the sorting of row and
collumn
But the assumption that is all the rows are completed its sort simulteneously
and the same for column as well.
b)Work and span of the algorithm.
Since we have the freedom to choose any algorithm in the sorting of the row
and column
Assume we have the algorithm A that sorts p [Link] work for sorting is
W(p) and span/depth is D(p).
each row and column contains p = √n elements so,
Work per row/column sort = W(√n)
Depth per row/column sort=D(√n)
Since row sorts is carried out for all rows in parallel.
We have to use algorithm A number of rows(√n) time in parallel.
And similar for all columns.
So work for each stage will be 2·√n · W(√n) = Θ(√n · W(√n))
Since all row sort is carried out simultaneously
depth for row sort is D(√n).
similarly for column sort D(√n).
so depth for each phase is 2·D(√n)=Θ(D(√n)).
We are doing this two phases log₂(n) times
so work for total shear sort=Θ(√n · W(√n) · log n)
depth for shear sort=Θ(D(√n) · log n).
Correctness:
If we can prove the correctness for the input containing only 0s and 1s then
this algorithm is correct for all the inputs.
A row is called clean if it contains only 0s or only 1s.
A row is called dirty if it contains both 0s and 1s.
We try to prove this thing: After each complete phase (row sort followed by column sort),
the number of dirty rows decreases by at least a factor of 2.
Proof:
After row sorting phase, within each row, all 0s and 1s are grouped together.
After column sorting phase, Each column is sorted in ascending order. Therefore:
All 0s move toward the top of the column
All 1s move toward the bottom
Since column sorting is applied simultaneously to all columns:
Upper rows receive more 0s
Lower rows receive more 1s
many rows become entirely filled with 0s or 1s, i.e., they become clean.
Any dirty row must contain both 0s and 1s. After column sorting, either its 0s are pushed
upward or its 1s are pushed downward, reducing its mixed nature. This gives that at least half
of the dirty rows become clean after one full phase.
if dk denotes the number of dirty rows after the k-th phase then,
dk+1≤dk/2.
At start the number of dirty rows is at-most m. after k phases.
after k=⌈log2m⌉ phases,
dk≤m/2k
dk≤1
i.e., at-most 1 row will be dirty .
and that can be sorted in the last row sort.
All rows are sorted in the snake like order.
So after O(log n) phases grid is sorted in the snake like order that implies
the correctness of shear sort in all inputs.