(28S) Sorting lists

[Damien]

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.

[C.Ret]

(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?

[Thomas Klemm]

From W.C. Wickes' paper "RPL: A Mathematical Control Language":


Cheers
Thomas