Rosetta Code

Sort stability: Difference between revisions

Page Discussion

Sort stability (view source)

Revision as of 17:49, 4 April 2024

796 bytes removed ,  2 months ago
→‎{{header|REXX}}: replace the wrong program
(→‎{{header|TXR}}: Update with new info.)
(→‎{{header|REXX}}: replace the wrong program)
 
(2 intermediate revisions by one other user not shown)
Line 1,532:
 
=={{header|REXX}}==
<syntaxhighlight lang="rexx"></syntaxhighlight>
Classic REXX has no built-in routines for sorting, so this programming example uses a classic ''bubble sort'' &nbsp; (which is stable).
<syntaxhighlight lang="rexx">/*REXX program sorts a (stemmed) array using a (stable) bubble─sort algorithm. */
call/* gen@replacing the wrong program published here earlier /*generate the array elements (strings)*/
call showgena 'before sort' /*showgenerate the before array elements. (strings)*/
call show 'before say copies('▒sort', 50) /*show the before array elements. /*show a separator line between shows. */
call stableSort
call bubbleSort # /*invoke the bubble sort. */
exit
call show ' after sort' /*show the after array elements. */
/*----------------------------------------------------------------------------*/
exit 0 /*stick a fork in it, we're all done. */
stableSort: procedure expose a.
/*──────────────────────────────────────────────────────────────────────────────────────*/
parse Value '' With l1 l2
bubbleSort: procedure expose @.; parse arg n; m= n-1 /*N: number of array elements. */
Do i=1 To a.0
do m=m for m by -1 until ok; ok= 1 /*keep sorting array until done.*/
parse Var a.i f1 f2
do j=1 for m; k= j+1; if @.j<=@.k then iterate /*Not out─of─order?*/
f2=translate(f2,'_',' ')
_= @.j; @.j= @.k; @.k= _ ok= 0 /*swap 2 elements; flag as ¬done*/
If pos(f1,l1)=0 Then l1=l1 f1
end /*j*/
If pos(f2,l2)=0 Then l2=l2 f2
end /*m*/; return
End
/*──────────────────────────────────────────────────────────────────────────────────────*/
l1=wordsort(l1)
gen@: @.=; @.1 = 'UK London'
l2=wordsort(l2)
@.2 = 'US New York'
Say ''
@.3 = 'US Birmingham'
Say 'sorted by country'
@.4 = 'UK Birmingham'
Do While l1<>''
do #=1 while @.#\=='' /*determine how many entries in list. */
Parse Var l1 f1s l1
end /*#*/; #= # - 1; return /*adjust for the DO loop index; return*/
Do i=1 To a.0
/*──────────────────────────────────────────────────────────────────────────────────────*/
parse Var a.i f1 f2
show: do j=1 for #; say ' element' right(j,length(#)) arg(1)":" @.j; end; return</syntaxhighlight>
If f1=f1s Then
Say a.i
End
End
Say ''
Say 'sorted by city'
Do While l2<>''
Parse Var l2 f2s l2
Do i=1 To a.0
parse Var a.i f1 f2
If translate(f2,'_',' ')=f2s Then
Say a.i
End
End
/*---------------------------------------------------------------------------------*/
gena: a.0=0
Call store 'UK London'
Call store 'US New York'
Call store 'US Birmingham'
Call store 'UK Birmingham'
Return
store:
z=a.0+1
a.z=arg(1)
a.0=z
Return
show:
Say arg(1)
do i=1 To a.0
say a.i
End
Return
 
wordsort: Procedure
/**********************************************************************
* Sort the list of words supplied as argument. Return the sorted list
**********************************************************************/
Parse Arg wl
wa.=''
wa.0=0
Do While wl<>''
Parse Var wl w wl
Do i=1 To wa.0
If wa.i>w Then Leave
End
If i<=wa.0 Then Do
Do j=wa.0 To i By -1
ii=j+1
wa.ii=wa.j
End
End
wa.i=w
wa.0=wa.0+1
End
swl=''
Do i=1 To wa.0
swl=swl wa.i
End
Return strip(swl)</syntaxhighlight>
{{out|output|text=&nbsp; when using the default list:}}
<pre>
K:\>rexx sso
element 1 before sort: UK London
element 2 before sort: US New York
UK London
element 3 before sort: US Birmingham
US New York
element 4 before sort: UK Birmingham
US Birmingham
▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
element 1 after sort: UK Birmingham
 
element 2 after sort: UK London
sorted by country
element 3 after sort: US Birmingham
UK London
element 4 after sort: US New York
UK Birmingham
US New York
US Birmingham
 
sorted by city
US Birmingham
UK Birmingham
UK London
US New York
</pre>
 
Line 1,703 ⟶ 1,771:
scala> cities.sortBy(_ substring 4)
res47: Seq[String] = ArrayBuffer(US Birmingham, UK Birmingham, UK London, US New York)</syntaxhighlight>
Besides that, there is the object <tt>scala.util.Sorting</tt>, which provides <tt>quickSort</tt> and <tt>stableSort</tt>. The former is only provided on <tt>Array</tt>, but the latter is provided over both <tt>Array</tt> and <tt>Seq</tt>. These sorts operate in-place, with the one over <tt>Seq</tt> returning a sorted <tt>Array</tt>. Here is one example:
<syntaxhighlight lang="scala">scala> val cityArray = cities.toArray
cityArray: Array[String] = Array(UK London, US New York, US Birmingham, UK Birmingham)
Line 1,751 ⟶ 1,819:
 
Below we illustrate the points made in the task description using the stable insertion sort.
<syntaxhighlight lang="ecmascriptwren">import "./sort" for Cmp, Sort
 
var data = [ ["UK", "London"], ["US", "New York"], ["US", "Birmingham"], ["UK", "Birmingham"] ]
Walterpachl
2,295

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/349666...363267"