(28S) Sorting lists
12-12-2013, 02:26 PM (This post was last modified: 06-15-2017 01:59 PM by Gene.)
Post: #1
 Damien Junior Member Posts: 29 Joined: Dec 2013
(28S) Sorting lists
Hi everyone,

This small program takes a list in the stack and returns the sorted list using the bubble sort algorithm.

Code:
 « DUP SIZE   IF DUP 1 > THEN 2      FOR i 1 i 1 -       FOR j DUP j GET OVER j 1 + GET          IF DUP2 > THEN ROT j ROT PUT j 1 + ROT PUT         ELSE DROP2 END       NEXT     - 1 STEP   ELSE DROP END  »
'T.BUL'
Bubble sort is not very efficient as sorting method, but the algorithm is simple to understand.

Another method more efficient is the selection sort:
Code:
 « DUP SIZE   IF DUP 1 > THEN 2     FOR i DUP 1 GET 1 → aide k        « 2 i FOR j DUP j GET IF DUP aide > THEN          'aide' STO j 'k' STO ELSE DROP END          NEXT k OVER i GET PUT i aide PUT         »      -1 STEP   ELSE DROP   END  »
'T.SEL'

One more, with insertion method this time !
Code:
 « DUP SIZE   IF DUP 1 > THEN → n    « 2 n FOR i DUP i GET i 1 -         → aide j         « WHILE DUP j 1 MAX GET aide > j 1 ≥ AND            REPEAT j 1 - 'j' STO            END            IF j i 1 - < THEN DUP 1 j SUB aide +              OVER j 1 + i 1 - SUB + OVER i 1 + n SUB +              SWAP DROP            END         »      NEXT     »    ELSE DROP END  »
'T.INS'

Damien.
02-16-2014, 08:19 PM (This post was last modified: 02-16-2014 08:25 PM by C.Ret.)
Post: #2
 C.Ret Member Posts: 61 Joined: Dec 2013
RE: [HP 28S] Sorting lists
(12-12-2013 02:26 PM)Damien Wrote:  [...]Bubble sort is not very efficient as sorting method, but the algorithm is simple to understand.

That's right. And another advantage of this sorting method with any RPL calculator is that it can easely be organize into the stack using the appropriate ROLL and ROLLD instructions. The 'bubbles' are pop up the stack with a SWAP after each comparison.

The following code sorts a list the same way your code do it, but in a shorter and simpler way.
Code:
 « LIST→ → n                             @ n is size of the list   « IF n 1 > THEN                                n 2 FOR i                                  2 i START              i ROLL                     @ pick-up i-th element fromthe stack/list              IF DUP2 < THEN SWAP END    @ swap element after comparison          NEXT          i ROLLD                        @ "selected" element bubble back into stack        -1 STEP     END                                     n →LIST                             @ rebuilt list from stack   » »
On HP-28S execution speed is greatly increase due to fewer instructions in the core loop and no list processing instruction PUT / GET.

But I am unable to say if this code is neither a true bubble sort, selection or insertion sort algorithm!?
Perhaps may we call it the Rolling Stack Sorting Algorithm?
02-17-2014, 09:29 PM (This post was last modified: 02-17-2014 09:31 PM by Thomas Klemm.)
Post: #3
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
RE: [HP 28S] Sorting lists
From W.C. Wickes' paper "RPL: A Mathematical Control Language":

Cheers
Thomas

Attached File(s) Thumbnail(s)

 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)