Sort stability: Difference between revisions
Content added Content deleted
(adding gap, but not sure !) |
(→{{header|GAP}}: more readable I hope) |
||
Line 83: | Line 83: | ||
=={{header|GAP}}== |
=={{header|GAP}}== |
||
<lang gap># According to section 21.18 of the reference manual, Sort is not stable |
<lang gap># According to section 21.18 of the reference manual, Sort is not stable (it's a Shell sort). |
||
# However, SortingPerm is stable. We will see it on an example, showing indexes of elements after the sort. |
|||
⚫ | |||
# "BBBABBBAABBBAAAABBAABBAAABBABBABABABABAB" |
|||
n := 20; |
|||
⚫ | |||
⚫ | |||
# (1,19,8,2,20,9,3,21,30,35,16,7,24,11,26,32,36,38,39,18,29,34,37,17,28,13,4)(5,22,31,14)(6,23,10,25,12, |
|||
# "AABABBBABBABAABABBAB" |
|||
# 27,33,15) |
|||
⚫ | |||
# [ 4, 8, 9, 13, 14, 15, 16, 19, 20, 23, 24, 25, 28, 31, 33, 35, 37, 39, 1, 2, 3, 5, 6, 7, 10, 11, 12, |
|||
# 17, 18, 21, 22, 26, 27, 29, 30, 32, 34, 36, 38, 40 ] |
|||
⚫ | |||
# So it looks like the sorting algorithm used is indeed stable. It may be useful to investigate GAP source code.</lang> |
|||
# (3,10,15,17,18,19,9,14,7,13,6,12,16,8,4)(5,11) |
|||
a := Permuted(L, p);; |
|||
⚫ | |||
PrintArray(TransposedMat(List([1 .. n], i -> [a[i], b[i]]))); |
|||
# [ [ 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B', 'B' ], |
|||
# [ 1, 2, 4, 8, 11, 13, 14, 16, 19, 3, 5, 6, 7, 9, 10, 12, 15, 17, 18, 20 ] ]</lang> |
|||
=={{header|Go}}== |
=={{header|Go}}== |