On Monday 28 April 2008 08:26:02 Oleg Kobchenko wrote:
> I wanted to model bubble sort.
> Here's a first shot. Any improvements?
>
> ]C=. 10 [EMAIL PROTECTED] 10
> 6 5 9 2 4 9 0 7 0 4
> /:~ C
> 0 0 2 4 4 5 6 7 9 9
> <./ C
> 0
> (([ ,`(,~)@.> [EMAIL PROTECTED]) , [EMAIL PROTECTED])/ C
> 0 6 5 9 2 4 9 0 7 4
> (([ ,`(,~)@.> [EMAIL PROTECTED]) , [EMAIL PROTECTED])/^:_ C
> 0 0 2 4 4 5 6 7 9 9
I post this just for completeness.
Sorry if I missed something in the preceeding posts.
We had in 1996 some posts about Bubble sort on comp.lang.apl.
I did an educational example for a demonstration in schools and then
asked Roger and Ken about their opinion. See their answers below...
Enjoy,
JoHo
----- CITATION START -------------------------------------------------
J Bubble Sort (1/2)
Although bubble sort itself is inefficient and not really useful in J,
because there is the built in sort verb (Sort=: /:~), bubble sort can
reveal some interesting programming techniques in J.
By the way, the name "bubble sort" was first used by Kenneth E. Iverson in
"A Programming Language", Wiley, NY, 1962.
Many thanks to Roger and Ken for their marvelous contributions (part(2)).
In the following my solution - can be done better -> part (2).
For readability I use the standard names for J verbs (ProVerbs) defined in
the script primitiv.js . There are only forks used in my version.
BS0=: JoinSwitch INSERT POWER infinity
The main idea of BS0 is (INSERT POWER infinity), or shortly (/^:_).
The verb JoinSwitch is inserted repeatedly, until the result of the
insertion does not change any more, in other words, until it reaches a
limit. In this context the limit is the sorted list.
The verb JoinSwitch switches the leading items if necessary,
and accumulates the items from right to left.
Example:
JoinSwitch INSERT 0 333 22
0 JoinSwitch 333 JoinSwitch 22
0 JoinSwitch 22 333
0 22 333
BS0=: JoinSwitch INSERT POWER infinity
BS1=: JoinSwitch/^:_
NB. switch if left is greater than right
Switch =: (>/) |. ]
Switch =: (>INSERT) Rotate Right
Left_FirstRight=: [ , [EMAIL PROTECTED]
Left_FirstRight=: Left Append [EMAIL PROTECTED]
JoinSwitch=: [EMAIL PROTECTED] Append [EMAIL PROTECTED]
NB. pure J (can be generated using the fix adverb f.)
BS2=: BS0 f.
BS2=: ((>/) |. ])@([ , [EMAIL PROTECTED]) , [EMAIL PROTECTED])/^:_
NB. The 993337-th permutation of 0 1 2...8 9
]unsorted=: 993337 A. i.10
2 7 6 0 5 9 1 3 8 4
BS0 unsorted NB. Bubble sort
0 1 2 3 4 5 6 7 8 9
NB. To see the algorithm converging to the solution,
NB. ^:_ is replaced with ^:(0 1 2 3...)
JoinSwitch/^:(i.10) unsorted
2 7 6 0 5 9 1 3 8 4
0 2 7 6 1 5 9 3 4 8
0 1 2 7 6 3 5 9 4 8
0 1 2 3 7 6 4 5 9 8
0 1 2 3 4 7 6 5 8 9
0 1 2 3 4 5 7 6 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
NB. --- APPENDIX --------------------------------------
Left =: [ NB. 10 <= 10 [ 8888
Right =: ] NB. 8888 <= 10 ] 8888
Head =: {. NB. first element
Behead =: }. NB. drop first element
Append =: , NB. 999 2 3 4 <= 999 , 2 3 4
Rotate =: |. NB. 2 1 <= 1 |. 1 2
INSERT =: / NB. insert Adverb: 1+2+3 <= +/1 2 3
POWER =: ^: NB. conjunction: functional power
infinity=: _ NB. noun: infinity - it's a number
JoHo :)
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
J: Bubble Sort (2/2) Roger&Ken
(I'have sent again this posting, because the news server
of my provider chrashed.)
When I asked Roger Hui, if he would know a shorter solution for bubble
sort, he answered:
> As a matter of fact, yes.
BS2=: (((>/) |. ])@([ , [EMAIL PROTECTED]) , [EMAIL PROTECTED])/^:_ NB.
original version
r1 =: ((>/ |. ])@([ , [EMAIL PROTECTED]) , [EMAIL PROTECTED])/^:_
r2 =: ((>/ |. ])@(,{.) , [EMAIL PROTECTED])/^:_
r3 =: (((> |. ,) {.) , [EMAIL PROTECTED])/^:_
r4 =: ((|.^:(>/)@, {.) , [EMAIL PROTECTED])/^:_
r5 =: (<@i.@>:@(>{.) C. ,)/^:_
r6 =: (i.@(>{.) C. ,)/^:_
r7 =: /:~ NB. ha ha
<
It was quite interesting for me to work through the simplifications.
Especially the use of C. surprised me.
But not enough, Ken Iverson had also a couple of expressions:
k0=: (/:~@(,{.),[EMAIL PROTECTED])/^:_
k1=: ((>{.)|.,)/^:_
Roger Hui:
> The first k0 uses the primitive sort /:~ on two elements.
> The second k1 is my favorite. It engenders exactly the
> same data movement as my r6=: (i.@(>{.) C. ,)/^:_
> but is shorter still and more transparent, and re-introduces
> the rotate |. that you used in your original solution.
The main difference between BS2 and r6 is, that r6 and also k1
move a leading number, which is greater than the following,
to the end of the list.
] list=: ?10$15
7 12 0 0 7 10 0 5 1 6
g=: i.@(>{.) C. , NB. Roger's bubble verb
g/^:(i.10) list NB. g insert to the power 0 1 2...
7 12 0 0 7 10 0 5 1 6
0 0 0 1 6 5 10 7 12 7
0 0 0 1 5 7 7 12 10 6
0 0 0 1 5 6 10 12 7 7
0 0 0 1 5 6 7 7 12 10
0 0 0 1 5 6 7 7 10 12
0 0 0 1 5 6 7 7 10 12
...
JoinSwitch=: (((>/) |. ])@([ , [EMAIL PROTECTED]) , [EMAIL PROTECTED])
JoinSwitch/^:(i.10) list
7 12 0 0 7 10 0 5 1 6
0 7 12 0 0 7 10 1 5 6
0 0 7 12 0 1 7 10 5 6
0 0 0 7 12 1 5 7 10 6
0 0 0 1 7 12 5 6 7 10
0 0 0 1 5 7 12 6 7 10
0 0 0 1 5 6 7 12 7 10
0 0 0 1 5 6 7 7 12 10
0 0 0 1 5 6 7 7 10 12
0 0 0 1 5 6 7 7 10 12
JoHo :)
----- CITATION END -------------------------------------------------
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
