Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Comparison-optimal sorting algorithm for five elements, plus testing code. (via Knuth TAoCP Vol 3, 2nd ed, 5.3.1)
def swap(a, i, j)
t = a[i]
a[i] = a[j]
a[j] = t
end
def sort(a)
# Sort first two pairs
swap(a,0,1) if a[1] < a[0]
swap(a,2,3) if a[3] < a[2]
# Sort pairs by larger element
if a[3] < a[1]
a = a[2,2] + a[0,2] + a[4,1]
end
# A = [a,b,c,d,e] with a < b < d and c < d
# insert e into [a,b,d]
if ( a[4] < a[1] ) # e < b
if ( a[4] < a[0] ) # e < a
b = a[4,1] + a[0,2] + a[3,1] # B = [e,a,b,d]
else # e > a
b = a[0,1] + a[4,1] + a[1,1] + a[3,1] # B = [a,e,b,d]
end
else # e > b
if ( a[4] < a[3] ) # e < d
b = a[0,2] + a[4,1] + a[3,1] # B = [a,b,e,d]
else # e > d
b = a[0,2] + a[3,2] # B = [a,b,d,e]
end
end
# insert c into the first three elements of B
if a[2] < b[1]
if a[2] < b[0]
c = a[2,0] + b
else
c = b[0,1] + a[2,0] + b[1,3]
end
else
if a[2] < b[2]
c = b[0,2] + a[2,0] + b[2,2]
else
c = b[0,3] + a[2,0] + b[3,1]
end
end
return c
end
def is_sorted(a)
(0..a.size-2).each { |i|
return false if a[i] > a[i+1]
}
return true
end
[1,2,3,4,5].permutation.each { |p|
p1 = Array.new(p)
if !is_sorted(sort(p)) || !sort(p).size == p.size
puts "ERROR #{p1.to_s} --> #{sort(p1).to_s}"
end
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.