Rosetta Code

Sort stability: Difference between revisions

Page Discussion

Sort stability (view source)

Revision as of 17:49, 4 April 2024

50 bytes removed ,  1 month ago
→‎{{header|REXX}}: replace the wrong program
(added Arturo)
(→‎{{header|REXX}}: replace the wrong program)
 
(4 intermediate revisions by 3 users 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,738 ⟶ 1,806:
=={{header|TXR}}==
 
TXR provides a number of sorting functions. <code>sort</code> and <code>nsort</code> (destructive variant) are not stable for vectors and strings, but are stable for lists.
Straight from the TXR documentation about the <code>sort</code> function:
 
The functions <code>ssort</code> and <code>snsort</code> counterparts are stable for all sequence kinds.
<i>The <code>sort</code> function is stable for sequences which are lists. This means that the original order of items which are considered identical is preserved. For strings and vectors, <code>sort</code> is not stable.</i>
 
In addition, there are caching variants of all these functions: <code>csort</code>, <code>cnsort</code>, <code>cssort</code> and <code>csnsort</code>. They respectively have the same stability properties as their counterparts without the leading <code>c</code>.
 
TXR Lisp originally had one sorting function called <code>sort</code>, which was destructive, like the <code>sort</code> in Common Lisp. That function was renamed to <code>nsort</code>, and <code>sort</code> became the name of a non-destructive function. That happened in TXR 238, released in May, 2020.
 
=={{header|Wren}}==
Line 1,747 ⟶ 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"] ]
Line 1,790 ⟶ 1,862:
[US, New York]
</pre>
 
=={{header|XPL0}}==
There is no built-in sort routine in XPL0. The 32-bit versions are
distributed with xpllib, which provides an integer sort routine. This
uses the Quicksort algorithm, which is unstable.
 
=={{header|zkl}}==
Walterpachl
2,289

edits

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