Dan Bron wrote:
>
> Can you implement Gnome Sort in a cute or elegant fashion?
>
> http://www.cs.vu.nl/~dick/gnomesort.html
>
> -Dan
>
Sure Dan,
Here is the Parallel Gnomes Sort:
Imagine a row of N/2 gnomes working in two shifts, such that each gnome
stands between two flowers, no two gnomes having a common flower,
Here is the picture:
9 G 8 7 G 6 5 G4 3 G 2 1 G 0
Now they all simultaneously swap the flowers according to their height:
8 G 9 6 G 7 4 G 5 2 G 3 0 G 1
Then they all together step one step to the right (the last gnome
rests now):
8 9 G 6 7 G 4 5 G 2 3 G 0 1
and repeat the process until no gnome swaps any flowers.
Working in parallel like this, they'll sort all the flowers in at most N
shifts,
so this is an O(N) sorting algorithm on N/2 gnomes, i.e processors.
J implementation:
g =: ((<.,>.){.),}...@]
shift1 =: g`,/
shift2 =: ,`g/
PGSort=:shi...@shift1^:(>....@-:@#)
PGSortSee=:shi...@shift1^:(i.@>:@>....@-:@#)
PGSort 3873 209370 738 3 2947 57398 3745 1
1 3 738 2947 3745 3873 57398 209370
PGSortSee 3873 209370 738 3 2947 57398 3745 1
3873 209370 738 3 2947 57398 3745 1
3873 3 209370 738 2947 1 57398 3745
3 738 3873 1 209370 2947 3745 57398
3 1 738 2947 3873 3745 209370 57398
1 3 738 2947 3745 3873 57398 209370
I've another, longer but more explicitly parallel version of this sort.
--
View this message in context:
http://www.nabble.com/Gnome-sort-tp24360048s24193p24365238.html
Sent from the J Programming mailing list archive at Nabble.com.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
