Project P156
Comparator lab
Insertion, selection and bubble sort run with a head-to-head record that has a cycle and with sets compared by subset: different results for every input order, and an adjacent-pairs check that passes on results that are not in order.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-18
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
Three sorts - insertion, selection, bubble - run with comparisons that are not a total order: a head-to-head record with a cycle, and sets compared by "is a proper subset of".
main.eml- the menu, the record and the subset relation, one sort of the teams or the sets in a chosen order, and every order run through every sortorder.eml- the teams and their record, the sets and the subset test, the three sorts, the check of adjacent pairs and of every pair, and every order of a list
How each part works:
- As in the corpus case
non-transitive-comparator, A beats B, B beats C and C beats A, and D loses to every other team: every pair has a winner, so every sort finishes. Over the 24 orders the teams can come in, each sort returns 3 different results. The usual postcondition, adjacent pairs in order, passes on all 72 runs; the check of every pair passes on none - with a cycle no arrangement can. - As in the corpus case
partial-order-trap, {a} comes before {a,b} and {c} before {b,c}, and every other pair is incomparable. Insertion and selection always return an order with every pair in order, but which one is chosen by the input order: 6 different results each. - Bubble sort stops once every adjacent pair is in order. With a partial order that is not enough: on 10 of the 24 orders it leaves a subset after its superset - {a} {b,c} {a,b} {c} stays as it came - and the adjacent check passes on every one of them.
What is checked: menu choices 1 to 6; a sort of insertion, selection or bubble; the four teams A, B, C and D, or the four set numbers 1 to 4, each once. An empty answer cancels.
Sessions: sessions/basic.in gives: - the comparisons; ABCD through insertion, selection and bubble; every order of the teams; - the sets 1423 through bubble and insertion; every order of the sets.
sessions/bad-input.in gives: - menu choices 0 and x; - sorts: a cancel and quick; orders of teams: a cancel, ABC, ABCC and abcd; orders of sets: 1235 and 1123; a cancel for the sort of the sets.
Built on the verified corpus cases non-transitive-comparator (a three-cycle through three sorts, and the adjacent check that cannot tell them apart) and partial-order-trap (sorting sets by subset, the result an arrangement of the incomparable ones).
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== Comparator lab ==
Three sorts with comparisons that are not a total order: a cycle, and a subset relation.
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 0
Pick a number from 1 to 6.
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> x
Pick a number from 1 to 6.
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 2
sort (insertion, selection, bubble)>
Cancelled.
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 2
sort (insertion, selection, bubble)> quick
Type insertion, selection or bubble.
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 2
sort (insertion, selection, bubble)> insertion
teams in the order they come (e.g. ABCD)>
Cancelled.
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 2
sort (insertion, selection, bubble)> insertion
teams in the order they come (e.g. ABCD)> ABC
Type the four teams A, B, C and D, each once.
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 2
sort (insertion, selection, bubble)> insertion
teams in the order they come (e.g. ABCD)> ABCC
Type the four teams A, B, C and D, each once.
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 2
sort (insertion, selection, bubble)> insertion
teams in the order they come (e.g. ABCD)> abcd
Type the four teams A, B, C and D, each once.
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 4
sort (insertion, selection, bubble)> bubble
sets in the order they come, by number 1 to 4 (e.g. 1234)> 1235
Type the four set numbers 1 to 4, each once.
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 4
sort (insertion, selection, bubble)> bubble
sets in the order they come, by number 1 to 4 (e.g. 1234)> 1123
Type the four set numbers 1 to 4, each once.
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 4
sort (insertion, selection, bubble)>
Cancelled.
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 6
Bye.
What was typed (27 lines)
0
x
2
2
quick
2
insertion
2
insertion
ABC
2
insertion
ABCC
2
insertion
abcd
4
bubble
1235
4
bubble
1123
4
6
basic
interpreter: byte-equal== Comparator lab ==
Three sorts with comparisons that are not a total order: a cycle, and a subset relation.
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 1
The head-to-head record (the row beats the column):
A B C D
A - x . x
B . - x x
C x . - x
D . . . -
A beats B, B beats C, C beats A: a cycle, and every pair still has a winner.
The sets, one coming before another when it is a proper subset of it:
{a} comes before {a,b}
{c} comes before {b,c}
Every other pair is incomparable: neither comes first.
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 2
sort (insertion, selection, bubble)> insertion
teams in the order they come (e.g. ABCD)> ABCD
in: A B C D
out: C A B D
adjacent pairs in order: yes; every pair in order: no
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 2
sort (insertion, selection, bubble)> selection
teams in the order they come (e.g. ABCD)> ABCD
in: A B C D
out: C A B D
adjacent pairs in order: yes; every pair in order: no
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 2
sort (insertion, selection, bubble)> bubble
teams in the order they come (e.g. ABCD)> ABCD
in: A B C D
out: A B C D
adjacent pairs in order: yes; every pair in order: no
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 3
Every one of the 24 orders the teams can come in, through each sort:
sort different results adjacent pairs in order every pair in order
insertion 3 24 of 24 0 of 24
selection 3 24 of 24 0 of 24
bubble 3 24 of 24 0 of 24
insertion returns C A B D, B C A D, A B C D
selection returns C A B D, B C A D, A B C D
bubble returns A B C D, C A B D, B C A D
No order of the teams has every pair in order: the cycle allows none, and every sort still finishes.
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 4
sort (insertion, selection, bubble)> bubble
sets in the order they come, by number 1 to 4 (e.g. 1234)> 1423
in: {a} {b,c} {a,b} {c}
out: {a} {b,c} {a,b} {c}
adjacent pairs in order: yes; every pair in order: no
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 4
sort (insertion, selection, bubble)> insertion
sets in the order they come, by number 1 to 4 (e.g. 1234)> 1423
in: {a} {b,c} {a,b} {c}
out: {a} {c} {b,c} {a,b}
adjacent pairs in order: yes; every pair in order: yes
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 5
Every one of the 24 orders the sets can come in, through each sort:
sort different results adjacent pairs in order every pair in order
insertion 6 24 of 24 24 of 24
selection 6 24 of 24 24 of 24
bubble 14 24 of 24 14 of 24
bubble stops once every adjacent pair is in order: on 10 of the 24 orders it leaves a subset after its superset, and the adjacent check passes
A sort by a partial order returns whichever arrangement the input order leads it to; nothing raises.
1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit
choice> 6
Bye.
What was typed (19 lines)
1
2
insertion
ABCD
2
selection
ABCD
2
bubble
ABCD
3
4
bubble
1423
4
insertion
1423
5
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# P156 comparator lab: the head-to-head record and the subset relation,
# one sort of the teams or the sets in a chosen order, and every order run
# through every sort.
import order
def plain(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 pad(s, n):
s => out
while len(out) < n:
out + " " => out
return out
def shown(kind, x):
if kind == "teams":
return x
"{" => out
0 => i
for c in x:
if i > 0:
out + "," => out
out + c => out
i + 1 => i
return out + "}"
def line(kind, xs):
"" => out
for x in xs:
if out != "":
out + " " => out
out + shown(kind, x) => out
return out
def yes(b):
if b:
return "yes"
return "no"
def show_rules():
"The head-to-head record (the row beats the column):" ^0
(" " + pad("A", 4) + pad("B", 4) + pad("C", 4) + "D") ^0
for x in order.teams():
(" " + pad(x, 4)) => row
for y in order.teams():
if x == y:
"-" => c
elif order.beats(x, y):
"x" => c
else:
"." => c
if y == "D":
row + c => row
else:
row + pad(c, 4) => row
row ^0
" A beats B, B beats C, C beats A: a cycle, and every pair still has a winner." ^0
"The sets, one coming before another when it is a proper subset of it:" ^0
for x in order.sets():
for y in order.sets():
if order.subset(x, y):
(" " + shown("sets", x) + " comes before " + shown("sets", y)) ^0
" Every other pair is incomparable: neither comes first." ^0
def read_algo():
plain(input("sort (insertion, selection, bubble)> ")) => a
return a
def algo_ok(a):
return a == "insertion" or a == "selection" or a == "bubble"
def read_order(kind):
# the items in the order typed, or [] when not an order of them
if kind == "teams":
plain(input("teams in the order they come (e.g. ABCD)> ")) => t
else:
plain(input("sets in the order they come, by number 1 to 4 (e.g. 1234)> ")) => t
if t == "":
return ["cancel"]
if len(t) != 4:
return []
[] => out
for c in t:
if kind == "teams":
if c != "A" and c != "B" and c != "C" and c != "D":
return []
c => x
else:
if c < "1" or c > "4":
return []
order.sets()[int(c) - 1] => x
for y in out:
if y == x:
return []
out + [x] => out
return out
def one(kind):
read_algo() => a
if a == "":
"Cancelled." ^0
return
if not algo_ok(a):
"Type insertion, selection or bubble." ^0
return
read_order(kind) => xs
if len(xs) == 1:
"Cancelled." ^0
return
if len(xs) == 0:
if kind == "teams":
"Type the four teams A, B, C and D, each once." ^0
else:
"Type the four set numbers 1 to 4, each once." ^0
return
order.sort(a, kind, xs) => out
(" in: " + line(kind, xs)) ^0
(" out: " + line(kind, out)) ^0
(" adjacent pairs in order: " + yes(order.adjacent_ok(kind, out)) + "; every pair in order: " + yes(order.all_ok(kind, out))) ^0
def every(kind):
if kind == "teams":
order.teams() => base
else:
order.sets() => base
order.orders(base) => all
("Every one of the " + str(len(all)) + " orders the " + kind + " can come in, through each sort:") ^0
(" " + pad("sort", 11) + "different results adjacent pairs in order every pair in order") ^0
[] => notes
for a in ["insertion", "selection", "bubble"]:
[] => outs
0 => adj
0 => full
for xs in all:
order.sort(a, kind, xs) => out
line(kind, out) => s
False => have
for o in outs:
if o == s:
True => have
if not have:
outs + [s] => outs
if order.adjacent_ok(kind, out):
adj + 1 => adj
if order.all_ok(kind, out):
full + 1 => full
(" " + pad(a, 11) + pad(str(len(outs)), 20) + pad(str(adj) + " of " + str(len(all)), 26) + str(full) + " of " + str(len(all))) ^0
if kind == "teams":
"" => all_outs
for o in outs:
if all_outs == "":
o => all_outs
else:
all_outs + ", " + o => all_outs
notes + [" " + a + " returns " + all_outs] => notes
elif full < adj:
notes + [" " + a + " stops once every adjacent pair is in order: on " + str(adj - full) + " of the " + str(len(all)) + " orders it leaves a subset after its superset, and the adjacent check passes"] => notes
for n in notes:
n ^0
if kind == "teams":
"No order of the teams has every pair in order: the cycle allows none, and every sort still finishes." ^0
else:
"A sort by a partial order returns whichever arrangement the input order leads it to; nothing raises." ^0
"== Comparator lab ==" ^0
"Three sorts with comparisons that are not a total order: a cycle, and a subset relation." ^0
True => running
while running:
"" ^0
"1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit" ^0
plain(input("choice> ")) => choice
if choice == "1":
show_rules()
elif choice == "2":
one("teams")
elif choice == "3":
every("teams")
elif choice == "4":
one("sets")
elif choice == "5":
every("sets")
elif choice == "6":
False => running
else:
"Pick a number from 1 to 6." ^0
"Bye." ^0
Python projection (main.py)
import order
def plain(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 pad(s, n):
out = s
while len(out) < n:
out = out + " "
return out
def shown(kind, x):
if kind == "teams":
return x
out = "{"
i = 0
for c in x:
if i > 0:
out = out + ","
out = out + c
i = i + 1
return out + "}"
def line(kind, xs):
out = ""
for x in xs:
if out != "":
out = out + " "
out = out + shown(kind, x)
return out
def yes(b):
if b:
return "yes"
return "no"
def show_rules():
print("The head-to-head record (the row beats the column):")
print(" " + pad("A", 4) + pad("B", 4) + pad("C", 4) + "D")
for x in order.teams():
row = " " + pad(x, 4)
for y in order.teams():
if x == y:
c = "-"
elif order.beats(x, y):
c = "x"
else:
c = "."
if y == "D":
row = row + c
else:
row = row + pad(c, 4)
print(row)
print(" A beats B, B beats C, C beats A: a cycle, and every pair still has a winner.")
print("The sets, one coming before another when it is a proper subset of it:")
for x in order.sets():
for y in order.sets():
if order.subset(x, y):
print(" " + shown("sets", x) + " comes before " + shown("sets", y))
print(" Every other pair is incomparable: neither comes first.")
def read_algo():
a = plain(input("sort (insertion, selection, bubble)> "))
return a
def algo_ok(a):
return a == "insertion" or a == "selection" or a == "bubble"
def read_order(kind):
if kind == "teams":
t = plain(input("teams in the order they come (e.g. ABCD)> "))
else:
t = plain(input("sets in the order they come, by number 1 to 4 (e.g. 1234)> "))
if t == "":
return ["cancel"]
if len(t) != 4:
return []
out = []
for c in t:
if kind == "teams":
if c != "A" and c != "B" and c != "C" and c != "D":
return []
x = c
else:
if c < "1" or c > "4":
return []
x = order.sets()[int(c) - 1]
for y in out:
if y == x:
return []
out = out + [x]
return out
def one(kind):
a = read_algo()
if a == "":
print("Cancelled.")
return
if not algo_ok(a):
print("Type insertion, selection or bubble.")
return
xs = read_order(kind)
if len(xs) == 1:
print("Cancelled.")
return
if len(xs) == 0:
if kind == "teams":
print("Type the four teams A, B, C and D, each once.")
else:
print("Type the four set numbers 1 to 4, each once.")
return
out = order.sort(a, kind, xs)
print(" in: " + line(kind, xs))
print(" out: " + line(kind, out))
print(" adjacent pairs in order: " + yes(order.adjacent_ok(kind, out)) + "; every pair in order: " + yes(order.all_ok(kind, out)))
def every(kind):
if kind == "teams":
base = order.teams()
else:
base = order.sets()
all = order.orders(base)
print("Every one of the " + str(len(all)) + " orders the " + kind + " can come in, through each sort:")
print(" " + pad("sort", 11) + "different results adjacent pairs in order every pair in order")
notes = []
for a in ["insertion", "selection", "bubble"]:
outs = []
adj = 0
full = 0
for xs in all:
out = order.sort(a, kind, xs)
s = line(kind, out)
have = False
for o in outs:
if o == s:
have = True
if not have:
outs = outs + [s]
if order.adjacent_ok(kind, out):
adj = adj + 1
if order.all_ok(kind, out):
full = full + 1
print(" " + pad(a, 11) + pad(str(len(outs)), 20) + pad(str(adj) + " of " + str(len(all)), 26) + str(full) + " of " + str(len(all)))
if kind == "teams":
all_outs = ""
for o in outs:
if all_outs == "":
all_outs = o
else:
all_outs = all_outs + ", " + o
notes = notes + [" " + a + " returns " + all_outs]
elif full < adj:
notes = notes + [" " + a + " stops once every adjacent pair is in order: on " + str(adj - full) + " of the " + str(len(all)) + " orders it leaves a subset after its superset, and the adjacent check passes"]
for n in notes:
print(n)
if kind == "teams":
print("No order of the teams has every pair in order: the cycle allows none, and every sort still finishes.")
else:
print("A sort by a partial order returns whichever arrangement the input order leads it to; nothing raises.")
print("== Comparator lab ==")
print("Three sorts with comparisons that are not a total order: a cycle, and a subset relation.")
running = True
while running:
print("")
print("1) the comparisons 2) sort the teams 3) every order of the teams 4) sort the sets 5) every order of the sets 6) quit")
choice = plain(input("choice> "))
if choice == "1":
show_rules()
elif choice == "2":
one("teams")
elif choice == "3":
every("teams")
elif choice == "4":
one("sets")
elif choice == "5":
every("sets")
elif choice == "6":
running = False
else:
print("Pick a number from 1 to 6.")
print("Bye.")
order.eml
eml# P156 comparator lab - three sorts run with comparisons that are not a
# total order. As in the corpus case non-transitive-comparator, a
# head-to-head record with a cycle (A beats B, B beats C, C beats A) gives
# every pair a definite answer, so every sort finishes, and the order it
# returns depends on the algorithm and the order the items came in; the
# usual check, adjacent pairs in order, can pass on all of them. As in the
# corpus case partial-order-trap, sets compared by "is a proper subset of"
# leave most pairs incomparable, and the sorted list is an arrangement of
# the incomparable ones chosen by the input order alone.
def teams():
return ["A", "B", "C", "D"]
def beats(x, y):
# the head-to-head record: A beats B, B beats C, C beats A; D loses to
# every other team
if x == y:
return False
if y == "D":
return True
if x == "D":
return False
return (x == "A" and y == "B") or (x == "B" and y == "C") or (x == "C" and y == "A")
def sets():
return ["a", "ab", "c", "bc"]
def subset(x, y):
# x is a proper subset of y; a set is a string of distinct letters
if len(x) >= len(y):
return False
for c in x:
False => found
for d in y:
if c == d:
True => found
if not found:
return False
return True
def before(kind, x, y):
# x must come before y
if kind == "teams":
return beats(x, y)
return subset(x, y)
def insertion(kind, xs):
[] => out
for x in xs:
[] => merged
False => placed
for y in out:
if not placed and before(kind, x, y):
merged + [x] => merged
True => placed
merged + [y] => merged
if not placed:
merged + [x] => merged
merged => out
return out
def selection(kind, xs):
xs => left
[] => out
while len(left) > 0:
0 => best
1 => i
while i < len(left):
if before(kind, left[i], left[best]):
i => best
i + 1 => i
out + [left[best]] => out
[] => rest
0 => j
for x in left:
if j != best:
rest + [x] => rest
j + 1 => j
rest => left
return out
def bubble(kind, xs):
xs => a
True => swapped
while swapped:
False => swapped
[] => b
0 => i
while i < len(a):
if i + 1 < len(a) and before(kind, a[i + 1], a[i]):
b + [a[i + 1], a[i]] => b
i + 2 => i
True => swapped
else:
b + [a[i]] => b
i + 1 => i
b => a
return a
def sort(algo, kind, xs):
if algo == "insertion":
return insertion(kind, xs)
if algo == "selection":
return selection(kind, xs)
return bubble(kind, xs)
def adjacent_ok(kind, xs):
# no item comes right after one it should come before
0 => i
while i + 1 < len(xs):
if before(kind, xs[i + 1], xs[i]):
return False
i + 1 => i
return True
def all_ok(kind, xs):
# no item comes anywhere after one it should come before
0 => i
while i < len(xs):
i + 1 => j
while j < len(xs):
if before(kind, xs[j], xs[i]):
return False
j + 1 => j
i + 1 => i
return True
def orders(xs):
# every order of the items
if len(xs) <= 1:
return [xs]
[] => out
0 => i
for x in xs:
[] => rest
0 => j
for y in xs:
if j != i:
rest + [y] => rest
j + 1 => j
for p in orders(rest):
out + [[x] + p] => out
i + 1 => i
return out
Python projection (order.py)
def teams():
return ["A", "B", "C", "D"]
def beats(x, y):
if x == y:
return False
if y == "D":
return True
if x == "D":
return False
return x == "A" and y == "B" or x == "B" and y == "C" or x == "C" and y == "A"
def sets():
return ["a", "ab", "c", "bc"]
def subset(x, y):
if len(x) >= len(y):
return False
for c in x:
found = False
for d in y:
if c == d:
found = True
if not found:
return False
return True
def before(kind, x, y):
if kind == "teams":
return beats(x, y)
return subset(x, y)
def insertion(kind, xs):
out = []
for x in xs:
merged = []
placed = False
for y in out:
if not placed and before(kind, x, y):
merged = merged + [x]
placed = True
merged = merged + [y]
if not placed:
merged = merged + [x]
out = merged
return out
def selection(kind, xs):
left = xs
out = []
while len(left) > 0:
best = 0
i = 1
while i < len(left):
if before(kind, left[i], left[best]):
best = i
i = i + 1
out = out + [left[best]]
rest = []
j = 0
for x in left:
if j != best:
rest = rest + [x]
j = j + 1
left = rest
return out
def bubble(kind, xs):
a = xs
swapped = True
while swapped:
swapped = False
b = []
i = 0
while i < len(a):
if i + 1 < len(a) and before(kind, a[i + 1], a[i]):
b = b + [a[i + 1], a[i]]
i = i + 2
swapped = True
else:
b = b + [a[i]]
i = i + 1
a = b
return a
def sort(algo, kind, xs):
if algo == "insertion":
return insertion(kind, xs)
if algo == "selection":
return selection(kind, xs)
return bubble(kind, xs)
def adjacent_ok(kind, xs):
i = 0
while i + 1 < len(xs):
if before(kind, xs[i + 1], xs[i]):
return False
i = i + 1
return True
def all_ok(kind, xs):
i = 0
while i < len(xs):
j = i + 1
while j < len(xs):
if before(kind, xs[j], xs[i]):
return False
j = j + 1
i = i + 1
return True
def orders(xs):
if len(xs) <= 1:
return [xs]
out = []
i = 0
for x in xs:
rest = []
j = 0
for y in xs:
if j != i:
rest = rest + [y]
j = j + 1
for p in orders(rest):
out = out + [[x] + p]
i = i + 1
return out