(28S) Sorting lists

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