Project P072
Table sorter
A table sorted by several columns, each up or down, by one stable sort or one pass per column; a stable and an unstable sort side by side; and the comparisons selection, insertion, merge and quicksort make on random, sorted, reversed and repetitive lists.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-14
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
A table of eight people sorted by several columns, each up or down. A stable and an unstable sort shown side by side, sorted the same but with ties in different orders. And the comparisons that selection, insertion, merge and quicksort make on up to 200 numbers in four kinds of order.
main.eml- the menu, reading sort keys, and showing tables and countssorting.eml- the multi-column sort, sorting one column at a time, the unstable sort, the four counting sorts, and the test numbers
How each part works:
- Sorting by "team, score desc": insertion sort where a row moves left only past rows it goes strictly before, deciding by the first column where the two differ. Rows equal on every column keep their order, so the sort is stable. Every sort works on a copy, as the corpus case
sort-stability-witnesswarns: without one, a sort writing through its indices would change its own input. - One column at a time: the same order comes from one stable sort per column, the LAST column first. Each pass keeps the order the earlier passes made among its ties. The program checks this every time.
- Stable or not: the same insertion sort with >= instead of > in its guard still sorts, but it moves rows past equal ones too and reverses every group of ties. That one character is the corpus case's point.
- Counts: selection sort always makes n(n-1)/2 comparisons. Insertion makes n - 1 on a list in order and n(n-1)/2 on one in reverse. Merge sort never needs more than n log2 n. Quicksort is the corpus case
quicksort-recursive, partitioning around the last element. On a list already in order (or in reverse) every pivot is an end value, and it makes n(n-1)/2 comparisons, as many as selection sort. - Test numbers: "random" and "few" (only 5 different values) come from a linear congruential generator with the constants of Numerical Recipes, using its top 16 bits, since the low bits of such a generator repeat quickly.
What is checked: menu choices 1 to 6; sort keys from name, team, year and score, each once, each optionally followed by asc or desc, separated by commas; a column name; 2 to 200 numbers; random, sorted, reversed or few. An empty answer cancels.
Sessions: sessions/basic.in gives: - the table, then sorted by team and score down, and the same order from one pass per column; - the stable and unstable sorts by score on that table: 6 of 8 rows in different places; - back to the first order, then sorted by year down and name; - the counts for 200 numbers sorted and random, 50 reversed, and 100 with few values.
sessions/bad-input.in gives: - menu choices 0 and x; - the keys "colour", "team up", "team, team" and "team,", then a cancel; - the column colour, then name, where nothing ties; - 1, 201 and abc numbers, and the order "shuffled", then a cancel.
Built on the verified corpus cases sort-stability-witness (stable against unstable insertion sort, checked by what an order check cannot see) and quicksort-recursive (Lomuto partition, in place).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Table sorter ==
Sort a table by several columns, see what a stable sort keeps, and count comparisons.
1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit
choice> 0
Pick a number from 1 to 6.
1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit
choice> x
Pick a number from 1 to 6.
1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit
choice> 2
sort by (like: team, score desc)> colour
Columns are name, team, year and score, each once, then asc or desc, separated by commas.
sort by (like: team, score desc)> team up
Columns are name, team, year and score, each once, then asc or desc, separated by commas.
sort by (like: team, score desc)> team, team
Columns are name, team, year and score, each once, then asc or desc, separated by commas.
sort by (like: team, score desc)> team,
Columns are name, team, year and score, each once, then asc or desc, separated by commas.
sort by (like: team, score desc)>
Cancelled.
1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit
choice> 3
column> colour
Columns are name, team, year and score.
column> name
stable (> in the guard) unstable (>= in the guard)
Ana Ana Ana Ana
Ben Ben Ben Ben
Chloe Chloe Chloe Chloe
Dev Dev Dev Dev
Eli Eli Eli Eli
Fay Fay Fay Fay
Gus Gus Gus Gus
Hana Hana Hana Hana
No two rows share a name, so the two orders are the same.
1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit
choice> 4
how many numbers (2 to 200)> 1
Type a whole number from 2 to 200.
how many numbers (2 to 200)> 201
Type a whole number from 2 to 200.
how many numbers (2 to 200)> abc
Type a whole number from 2 to 200.
how many numbers (2 to 200)> 50
order (random, sorted, reversed, few)> shuffled
Type random, sorted, reversed or few.
order (random, sorted, reversed, few)>
Cancelled.
1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit
choice> 6
Bye.
What was typed (19 lines)
0
x
2
colour
team up
team, team
team,
3
colour
name
4
1
201
abc
50
shuffled
6
basic
interpreter: byte-equal== Table sorter ==
Sort a table by several columns, see what a stable sort keeps, and count comparisons.
1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit
choice> 1
name team year score
Ana red 2019 88
Ben blue 2021 92
Chloe red 2020 92
Dev green 2019 75
Eli blue 2019 88
Fay green 2021 92
Gus red 2021 75
Hana blue 2020 81
1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit
choice> 2
sort by (like: team, score desc)> team, score desc
name team year score
Ben blue 2021 92
Eli blue 2019 88
Hana blue 2020 81
Fay green 2021 92
Dev green 2019 75
Chloe red 2020 92
Ana red 2019 88
Gus red 2021 75
Sorting by score (down), then by team - one stable sort each, last column first - gives the same order.
1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit
choice> 3
column> score
stable (> in the guard) unstable (>= in the guard)
Dev 75 Gus 75
Gus 75 Dev 75
Hana 81 Hana 81
Eli 88 Ana 88
Ana 88 Eli 88
Ben 92 Chloe 92
Fay 92 Fay 92
Chloe 92 Ben 92
Both are sorted by score, but 6 rows are in different places: the stable sort keeps equal rows in the order the table had them, the other reverses them.
1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit
choice> 5
Back to the order the table started in.
1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit
choice> 2
sort by (like: team, score desc)> year desc, name
name team year score
Ben blue 2021 92
Fay green 2021 92
Gus red 2021 75
Chloe red 2020 92
Hana blue 2020 81
Ana red 2019 88
Dev green 2019 75
Eli blue 2019 88
Sorting by name, then by year (down) - one stable sort each, last column first - gives the same order.
1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit
choice> 4
how many numbers (2 to 200)> 200
order (random, sorted, reversed, few)> sorted
200 numbers, sorted:
selection 19900 comparisons
insertion 199
merge 732
quicksort 19900
All four give the same sorted list.
n(n-1)/2 = 19900: selection sort always makes exactly that many.
1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit
choice> 4
how many numbers (2 to 200)> 200
order (random, sorted, reversed, few)> random
200 numbers, random:
selection 19900 comparisons
insertion 9990
merge 1288
quicksort 1857
All four give the same sorted list.
n(n-1)/2 = 19900: selection sort always makes exactly that many.
1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit
choice> 4
how many numbers (2 to 200)> 50
order (random, sorted, reversed, few)> reversed
50 numbers, reversed:
selection 1225 comparisons
insertion 1225
merge 153
quicksort 1225
All four give the same sorted list.
n(n-1)/2 = 1225: selection sort always makes exactly that many.
1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit
choice> 4
how many numbers (2 to 200)> 100
order (random, sorted, reversed, few)> few
100 numbers, few:
selection 4950 comparisons
insertion 1961
merge 515
quicksort 1149
All four give the same sorted list.
n(n-1)/2 = 4950: selection sort always makes exactly that many.
1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit
choice> 6
Bye.
What was typed (21 lines)
1
2
team, score desc
3
score
5
2
year desc, name
4
200
sorted
4
200
random
4
50
reversed
4
100
few
6
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P072 table sorter: a small table sorted by several columns, each up or
# down; what a stable sort keeps that an unstable one loses; and how many
# comparisons selection, insertion, merge and quicksort make.
import sorting
def trim(s):
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def number(s):
if len(s) == 0 or len(s) > 4:
return -1
0 => n
for c in s:
if not (c >= "0" and c <= "9"):
return -1
n * 10 + int(c) => n
return n
def pad(s, n):
while len(s) < n:
s + " " => s
return s
def lpad(s, n):
while len(s) < n:
" " + s => s
return s
def column(name):
if name == "name":
return 0
if name == "team":
return 1
if name == "year":
return 2
if name == "score":
return 3
return -1
def words(s):
# Split on spaces.
[] => out
"" => w
for c in s + " ":
if c == " ":
if w != "":
out + [w] => out
"" => w
else:
w + c => w
return out
def keys_of(s):
# "team, score desc" -> [[1, False], [3, True]]; [] if not understood.
[] => out
0 => i
while i <= len(s):
i => j
while j < len(s) and s[j] != ",":
j + 1 => j
words(s[i:j]) => w
if len(w) == 0 or len(w) > 2 or column(w[0]) == -1:
return []
False => down
if len(w) == 2:
if w[1] == "desc":
True => down
elif w[1] != "asc":
return []
for k in out:
if k[0] == column(w[0]):
return []
out + [[column(w[0]), down]] => out
j + 1 => i
return out
def show(rows):
" name team year score" ^0
for r in rows:
(" " + pad(r[0], 8) + pad(r[1], 8) + str(r[2]) + lpad(str(r[3]), 7)) ^0
def key_text(k):
["name", "team", "year", "score"] => names
if k[1]:
return names[k[0]] + " (down)"
return names[k[0]]
def sort_table(rows):
while True:
trim(input("sort by (like: team, score desc)> ")) => s
if s == "":
"Cancelled." ^0
return rows
keys_of(s) => keys
if len(keys) > 0:
sorting.sort_rows(rows, keys) => out
show(out)
if len(keys) > 1:
"" => order
len(keys) - 1 => k
while k >= 0:
if order != "":
order + ", then by " => order
order + key_text(keys[k]) => order
k - 1 => k
if sorting.sort_passes(rows, keys) == out:
("Sorting by " + order + " - one stable sort each, last column first - gives the same order.") ^0
else:
("Sorting by " + order + " gives a different order.") ^0
return out
"Columns are name, team, year and score, each once, then asc or desc, separated by commas." ^0
def stability(rows):
while True:
trim(input("column> ")) => s
if s == "":
"Cancelled." ^0
return
column(s) => col
if col >= 0:
sorting.sort_rows(rows, [[col, False]]) => good
sorting.by_column_unstable(rows, col) => bad
" stable (> in the guard) unstable (>= in the guard)" ^0
for i in [0:len(rows) - 1]:
(" " + pad(good[i][0], 8) + pad(str(good[i][col]), 22) + pad(bad[i][0], 8) + str(bad[i][col])) ^0
0 => moved
for i in [0:len(rows) - 1]:
if good[i][0] != bad[i][0]:
moved + 1 => moved
if moved == 0:
("No two rows share a " + s + ", so the two orders are the same.") ^0
else:
("Both are sorted by " + s + ", but " + str(moved) + " rows are in different places: the stable sort keeps equal rows in the order the table had them, the other reverses them.") ^0
return
"Columns are name, team, year and score." ^0
def counts():
while True:
trim(input("how many numbers (2 to 200)> ")) => s
if s == "":
"Cancelled." ^0
return
number(s) => n
if n >= 2 and n <= 200:
while True:
trim(input("order (random, sorted, reversed, few)> ")) => order
if order == "":
"Cancelled." ^0
return
if order == "random" or order == "sorted" or order == "reversed" or order == "few":
sorting.numbers(n, order, n) => xs
sorting.selection_count(xs) => a
sorting.insertion_count(xs) => b
sorting.merge_count(xs) => c
sorting.quick_count(xs) => d
(str(n) + " numbers, " + order + ":") ^0
(" selection " + lpad(str(a[1]), 7) + " comparisons") ^0
(" insertion " + lpad(str(b[1]), 7)) ^0
(" merge " + lpad(str(c[1]), 7)) ^0
(" quicksort " + lpad(str(d[1]), 7)) ^0
if a[0] == b[0] and b[0] == c[0] and c[0] == d[0]:
"All four give the same sorted list." ^0
# n (n - 1) is below 40,000 here, so the division is exact
("n(n-1)/2 = " + str(int(n * (n - 1) / 2)) + ": selection sort always makes exactly that many.") ^0
return
"Type random, sorted, reversed or few." ^0
"Type a whole number from 2 to 200." ^0
[
["Ana", "red", 2019, 88],
["Ben", "blue", 2021, 92],
["Chloe", "red", 2020, 92],
["Dev", "green", 2019, 75],
["Eli", "blue", 2019, 88],
["Fay", "green", 2021, 92],
["Gus", "red", 2021, 75],
["Hana", "blue", 2020, 81],
] => start
start => rows
"== Table sorter ==" ^0
"Sort a table by several columns, see what a stable sort keeps, and count comparisons." ^0
True => running
while running:
"" ^0
"1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit" ^0
trim(input("choice> ")) => choice
if choice == "1":
show(rows)
elif choice == "2":
sort_table(rows) => rows
elif choice == "3":
stability(rows)
elif choice == "4":
counts()
elif choice == "5":
start => rows
"Back to the order the table started in." ^0
elif choice == "6":
False => running
else:
"Pick a number from 1 to 6." ^0
"Bye." ^0
Python projection (main.py)
import sorting
def trim(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def number(s):
if len(s) == 0 or len(s) > 4:
return -1
n = 0
for c in s:
if not (c >= "0" and c <= "9"):
return -1
n = n * 10 + int(c)
return n
def pad(s, n):
while len(s) < n:
s = s + " "
return s
def lpad(s, n):
while len(s) < n:
s = " " + s
return s
def column(name):
if name == "name":
return 0
if name == "team":
return 1
if name == "year":
return 2
if name == "score":
return 3
return -1
def words(s):
out = []
w = ""
for c in s + " ":
if c == " ":
if w != "":
out = out + [w]
w = ""
else:
w = w + c
return out
def keys_of(s):
out = []
i = 0
while i <= len(s):
j = i
while j < len(s) and s[j] != ",":
j = j + 1
w = words(s[i:j])
if len(w) == 0 or len(w) > 2 or column(w[0]) == -1:
return []
down = False
if len(w) == 2:
if w[1] == "desc":
down = True
elif w[1] != "asc":
return []
for k in out:
if k[0] == column(w[0]):
return []
out = out + [[column(w[0]), down]]
i = j + 1
return out
def show(rows):
print(" name team year score")
for r in rows:
print(" " + pad(r[0], 8) + pad(r[1], 8) + str(r[2]) + lpad(str(r[3]), 7))
def key_text(k):
names = ["name", "team", "year", "score"]
if k[1]:
return names[k[0]] + " (down)"
return names[k[0]]
def sort_table(rows):
while True:
s = trim(input("sort by (like: team, score desc)> "))
if s == "":
print("Cancelled.")
return rows
keys = keys_of(s)
if len(keys) > 0:
out = sorting.sort_rows(rows, keys)
show(out)
if len(keys) > 1:
order = ""
k = len(keys) - 1
while k >= 0:
if order != "":
order = order + ", then by "
order = order + key_text(keys[k])
k = k - 1
if sorting.sort_passes(rows, keys) == out:
print("Sorting by " + order + " - one stable sort each, last column first - gives the same order.")
else:
print("Sorting by " + order + " gives a different order.")
return out
print("Columns are name, team, year and score, each once, then asc or desc, separated by commas.")
def stability(rows):
while True:
s = trim(input("column> "))
if s == "":
print("Cancelled.")
return
col = column(s)
if col >= 0:
good = sorting.sort_rows(rows, [[col, False]])
bad = sorting.by_column_unstable(rows, col)
print(" stable (> in the guard) unstable (>= in the guard)")
for i in range(0, len(rows)):
print(" " + pad(good[i][0], 8) + pad(str(good[i][col]), 22) + pad(bad[i][0], 8) + str(bad[i][col]))
moved = 0
for i in range(0, len(rows)):
if good[i][0] != bad[i][0]:
moved = moved + 1
if moved == 0:
print("No two rows share a " + s + ", so the two orders are the same.")
else:
print("Both are sorted by " + s + ", but " + str(moved) + " rows are in different places: the stable sort keeps equal rows in the order the table had them, the other reverses them.")
return
print("Columns are name, team, year and score.")
def counts():
while True:
s = trim(input("how many numbers (2 to 200)> "))
if s == "":
print("Cancelled.")
return
n = number(s)
if n >= 2 and n <= 200:
while True:
order = trim(input("order (random, sorted, reversed, few)> "))
if order == "":
print("Cancelled.")
return
if order == "random" or order == "sorted" or order == "reversed" or order == "few":
xs = sorting.numbers(n, order, n)
a = sorting.selection_count(xs)
b = sorting.insertion_count(xs)
c = sorting.merge_count(xs)
d = sorting.quick_count(xs)
print(str(n) + " numbers, " + order + ":")
print(" selection " + lpad(str(a[1]), 7) + " comparisons")
print(" insertion " + lpad(str(b[1]), 7))
print(" merge " + lpad(str(c[1]), 7))
print(" quicksort " + lpad(str(d[1]), 7))
if a[0] == b[0] and b[0] == c[0] and c[0] == d[0]:
print("All four give the same sorted list.")
print("n(n-1)/2 = " + str(int(n * (n - 1) / 2)) + ": selection sort always makes exactly that many.")
return
print("Type random, sorted, reversed or few.")
print("Type a whole number from 2 to 200.")
start = [["Ana", "red", 2019, 88], ["Ben", "blue", 2021, 92], ["Chloe", "red", 2020, 92], ["Dev", "green", 2019, 75], ["Eli", "blue", 2019, 88], ["Fay", "green", 2021, 92], ["Gus", "red", 2021, 75], ["Hana", "blue", 2020, 81]]
rows = start
print("== Table sorter ==")
print("Sort a table by several columns, see what a stable sort keeps, and count comparisons.")
running = True
while running:
print("")
print("1) table 2) sort 3) stable or not 4) count comparisons 5) back to the first order 6) quit")
choice = trim(input("choice> "))
if choice == "1":
show(rows)
elif choice == "2":
rows = sort_table(rows)
elif choice == "3":
stability(rows)
elif choice == "4":
counts()
elif choice == "5":
rows = start
print("Back to the order the table started in.")
elif choice == "6":
running = False
else:
print("Pick a number from 1 to 6.")
print("Bye.")
sorting.eml
eml# P072 table sorter - sorting rows by several columns, what stability
# means, and how many comparisons four sorts make.
def copy_of(xs):
# The corpus case sort-stability-witness: `xs => out` would bind the
# same list, and a sort writing through its indices would change its
# own input. So a sort works on a copy.
[0] * len(xs) => out
for i in [0:len(xs) - 1]:
xs[i] => out[i]
return out
def before(a, b, keys):
# True when row a goes strictly before row b. keys is a list of
# [column, descending]; the first column where they differ decides.
for k in keys:
a[k[0]] => x
b[k[0]] => y
if x != y:
if k[1]:
return x > y
return x < y
return False
def sort_rows(rows, keys):
# Insertion sort on all the keys at once. A row moves left only past
# rows it goes strictly before, so rows equal on every key keep their
# order: the sort is stable.
copy_of(rows) => out
for i in [1:len(out) - 1]:
out[i] => x
i - 1 => j
while j >= 0 and before(x, out[j], keys):
out[j] => out[j + 1]
j - 1 => j
x => out[j + 1]
return out
def sort_passes(rows, keys):
# The same order by one stable sort per key, the LAST key first: each
# pass keeps the order the earlier passes made among its ties.
rows => out
len(keys) - 1 => k
while k >= 0:
sort_rows(out, [keys[k]]) => out
k - 1 => k
return out
def by_column_unstable(rows, col):
# Insertion sort with >= instead of > in the guard: it still sorts, but
# it moves a row past EQUAL rows too, reversing ties.
copy_of(rows) => out
for i in [1:len(out) - 1]:
out[i] => x
i - 1 => j
while j >= 0 and out[j][col] >= x[col]:
out[j] => out[j + 1]
j - 1 => j
x => out[j + 1]
return out
# The counting sorts: each returns [sorted copy, comparisons made].
def selection_count(xs):
copy_of(xs) => a
0 => c
for i in [0:len(a) - 2]:
i => m
for j in [i + 1:len(a) - 1]:
c + 1 => c
if a[j] < a[m]:
j => m
a[i] => t
a[m] => a[i]
t => a[m]
return [a, c]
def insertion_count(xs):
copy_of(xs) => a
0 => c
for i in [1:len(a) - 1]:
a[i] => x
i - 1 => j
True => going
while going and j >= 0:
c + 1 => c
if a[j] > x:
a[j] => a[j + 1]
j - 1 => j
else:
False => going
x => a[j + 1]
return [a, c]
def merge_count(xs):
# Top-down merge sort; the counter is a one-element list so the halves
# can add to it.
[0] => c
return [merge_sorted(xs, c), c[0]]
def merge_sorted(xs, c):
if len(xs) <= 1:
return copy_of(xs)
int(len(xs) / 2) => h
merge_sorted(xs[0:h], c) => left
merge_sorted(xs[h:len(xs)], c) => right
[0] * len(xs) => out
0 => i
0 => j
0 => k
while i < len(left) and j < len(right):
c[0] + 1 => c[0]
if right[j] < left[i]:
right[j] => out[k]
j + 1 => j
else:
left[i] => out[k]
i + 1 => i
k + 1 => k
while i < len(left):
left[i] => out[k]
i + 1 => i
k + 1 => k
while j < len(right):
right[j] => out[k]
j + 1 => j
k + 1 => k
return out
def quick_count(xs):
# The corpus case quicksort-recursive: Lomuto partition around the last
# element. On a list already in order every pivot is the largest, so it
# makes n(n-1)/2 comparisons, as many as selection sort.
copy_of(xs) => a
[0] => c
quick(a, 0, len(a) - 1, c)
return [a, c[0]]
def quick(a, lo, hi, c):
if lo < hi:
a[hi] => pivot
lo - 1 => i
for j in [lo:hi - 1]:
c[0] + 1 => c[0]
if a[j] <= pivot:
i + 1 => i
a[i] => t
a[j] => a[i]
t => a[j]
a[i + 1] => t
a[hi] => a[i + 1]
t => a[hi]
quick(a, lo, i, c)
quick(a, i + 2, hi, c)
def numbers(n, order, seed):
# n test numbers: "random" from a linear congruential generator (the
# constants of Numerical Recipes, mod 2^32), "sorted", "reversed", or
# "few" (random, but only 5 different values). The low bits of such a
# generator repeat quickly, so the value is taken from the top 16 bits;
# x / 65536 divides by a power of two below 2^53, which is exact.
[0] * n => out
seed => x
for i in [0:n - 1]:
(1664525 * x + 1013904223) % 4294967296 => x
if order == "sorted":
i + 1 => out[i]
elif order == "reversed":
n - i => out[i]
elif order == "few":
int(x / 65536) % 5 => out[i]
else:
int(x / 65536) % 1000 => out[i]
return out
Python projection (sorting.py)
def copy_of(xs):
out = [0] * len(xs)
for i in range(0, len(xs)):
out[i] = xs[i]
return out
def before(a, b, keys):
for k in keys:
x = a[k[0]]
y = b[k[0]]
if x != y:
if k[1]:
return x > y
return x < y
return False
def sort_rows(rows, keys):
out = copy_of(rows)
for i in range(1, len(out)):
x = out[i]
j = i - 1
while j >= 0 and before(x, out[j], keys):
out[j + 1] = out[j]
j = j - 1
out[j + 1] = x
return out
def sort_passes(rows, keys):
out = rows
k = len(keys) - 1
while k >= 0:
out = sort_rows(out, [keys[k]])
k = k - 1
return out
def by_column_unstable(rows, col):
out = copy_of(rows)
for i in range(1, len(out)):
x = out[i]
j = i - 1
while j >= 0 and out[j][col] >= x[col]:
out[j + 1] = out[j]
j = j - 1
out[j + 1] = x
return out
def selection_count(xs):
a = copy_of(xs)
c = 0
for i in range(0, len(a) - 2+1):
m = i
for j in range(i + 1, len(a)):
c = c + 1
if a[j] < a[m]:
m = j
t = a[i]
a[i] = a[m]
a[m] = t
return [a, c]
def insertion_count(xs):
a = copy_of(xs)
c = 0
for i in range(1, len(a)):
x = a[i]
j = i - 1
going = True
while going and j >= 0:
c = c + 1
if a[j] > x:
a[j + 1] = a[j]
j = j - 1
else:
going = False
a[j + 1] = x
return [a, c]
def merge_count(xs):
c = [0]
return [merge_sorted(xs, c), c[0]]
def merge_sorted(xs, c):
if len(xs) <= 1:
return copy_of(xs)
h = int(len(xs) / 2)
left = merge_sorted(xs[0:h], c)
right = merge_sorted(xs[h:len(xs)], c)
out = [0] * len(xs)
i = 0
j = 0
k = 0
while i < len(left) and j < len(right):
c[0] = c[0] + 1
if right[j] < left[i]:
out[k] = right[j]
j = j + 1
else:
out[k] = left[i]
i = i + 1
k = k + 1
while i < len(left):
out[k] = left[i]
i = i + 1
k = k + 1
while j < len(right):
out[k] = right[j]
j = j + 1
k = k + 1
return out
def quick_count(xs):
a = copy_of(xs)
c = [0]
quick(a, 0, len(a) - 1, c)
return [a, c[0]]
def quick(a, lo, hi, c):
if lo < hi:
pivot = a[hi]
i = lo - 1
for j in range(lo, hi):
c[0] = c[0] + 1
if a[j] <= pivot:
i = i + 1
t = a[i]
a[i] = a[j]
a[j] = t
t = a[i + 1]
a[i + 1] = a[hi]
a[hi] = t
quick(a, lo, i, c)
quick(a, i + 2, hi, c)
def numbers(n, order, seed):
out = [0] * n
x = seed
for i in range(0, n):
x = (1664525 * x + 1013904223) % 4294967296
if order == "sorted":
out[i] = i + 1
elif order == "reversed":
out[i] = n - i
elif order == "few":
out[i] = int(x / 65536) % 5
else:
out[i] = int(x / 65536) % 1000
return out