+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (28S) Sorting lists (/thread-47.html)
(28S) Sorting lists - Damien - 12-12-2013 02:26 PM
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
»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
»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
»Damien.
RE: [HP 28S] Sorting lists - C.Ret - 02-16-2014 08:19 PM
(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
»
»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?
RE: [HP 28S] Sorting lists - Thomas Klemm - 02-17-2014 09:29 PM
From W.C. Wickes' paper "RPL: A Mathematical Control Language":
Cheers
Thomas