Post Reply 
(28S) Sorting lists
12-12-2013, 02:26 PM (This post was last modified: 06-15-2017 01:59 PM by Gene.)
Post: #1
(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.
Find all posts by this user
Quote this message in a reply
02-16-2014, 08:19 PM (This post was last modified: 02-16-2014 08:25 PM by C.Ret.)
Post: #2
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?
Find all posts by this user
Quote this message in a reply
02-17-2014, 09:29 PM (This post was last modified: 02-17-2014 09:31 PM by Thomas Klemm.)
Post: #3
RE: [HP 28S] Sorting lists
From W.C. Wickes' paper "RPL: A Mathematical Control Language":
[Image: attachment.php?aid=314]

Cheers
Thomas


Attached File(s) Thumbnail(s)
   
Find all posts by this user
Quote this message in a reply
Post Reply 




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