Anonymous user
Sort stability: Difference between revisions
no edit summary
No edit summary |
|||
Line 542:
=={{header|Lua}}==
The built-in function table.sort is not guaranteed stable.
=={{header|M2000 Interpreter}}==
M2000 has two types of Inventories, objects using a hash algorithm, the normal with unique keys, so a sort statement on this object use quicksort, and a second type, the "queue" type, which can get same keys, and has stable sort.
Here is the stable sort
<lang M2000 Interpreter>
Module Stable {
Inventory queue alfa
Stack New {
Data "UK", "London","US", "New York","US", "Birmingham", "UK","Birmingham"
While not empty {
Append alfa, Letter$:=letter$
}
}
sort alfa
k=Each(alfa)
Document A$
NL$={
}
While k {
A$= Eval$(k, k^)+" "+eval$(k)+NL$
}
Clipboard A$ ' write to clipboard
Report A$
}
Call Stable
</lang>
Output:
UK London
UK Birmingham
US New York
US Birmingham
We can sort in on key only. Lets make keys with two fields (based on fields lengths, except for last one)
<lang M2000 Interpreter>
Module Stable1 {
Inventory queue alfa
Stack New {
Data "UK London","US New York","US Birmingham", "UK Birmingham"
While not empty {
Append alfa, Letter$
}
}
sort alfa
k=Each(alfa)
Document A$
NL$={
}
While k {
A$= Eval$(k, k^)+NL$
}
Clipboard A$ ' write to clipboard
Report A$
}
Call Stable1
</lang>
Output:
UK Birmingham
UK London
US Birmingham
US New York
Now second column is sorting (but it is one column all, no two columns). So lets see the unstable sort. Because all keys now are unique we just remove queue from Inventory definition.
<lang M2000 Interpreter>
Module Stable2 {
Inventory alfa
Stack New {
Data "UK London","US New York","US Birmingham", "UK Birmingham"
While not empty {
Append alfa, Letter$
}
}
sort alfa
k=Each(alfa)
Document A$
NL$={
}
While k {
A$= Eval$(k, k^)+NL$
}
Clipboard A$ ' write to clipboard
Report A$
}
Call Stable2
</lang>
Output:
UK Birmingham
UK London
US Birmingham
US New York
So now we see that using unique keys in either type of inventories we get same output.
By default in inventory queue numbers in keys (in any position) are sorted as numbers.
We can use '''sort alfa as number''' for normal inventory, or ''sort alfa as text''
For ascending/descending sort we can use sort descending alfa as number
If we delete a key in normal inventory we miss the sort order. We can't delete keys in queue inventories, but we can drop from the last append a number of keys. Also Exist() function in queue inventories always find the last entry (for same keys), until that dropped, so with next use of Exist(pointer_to_inventory, key_case_sensitive$) we find the previous one. We can use keys as numbers, but they stored as strings.
=={{header|Mathematica}}==
| |||