Skip to content

Instantly share code, notes, and snippets.

@kazk

kazk/sort5.swift

Last active August 29, 2015 14:16
Show Gist options
  • Save kazk/093cbe242495a034ec99 to your computer and use it in GitHub Desktop.
Save kazk/093cbe242495a034ec99 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
sort5.swift
/// Sorts 5 inputs by 7 comparisons.
/// Uses Minimum-Comparison Sorting Algorithm (H. B. Demuth, 1956).
func sort5<T : Comparable>
(inout a: T, inout b: T, inout c: T, inout d: T, inout e: T)
{
// 1. Setup conditions. (3 comparisons)
// b → d
// ↑ ↑ a < b < d, c < d
// a c e
if b < a { (a, b) = (b, a) } // a < b
if d < c { (c, d) = (d, c) } // c < d
if d < b { (a, b, c, d) = (c, d, a, b) } // a < b < d
// 2. Insert e into the chain of a,b,d with a < b < d. (2 comparisons)
// 3. Insert c into the chain of a,b,d,e with c < d. (2 comparisons)
if e < b {
if e < a { // e < a < b < d
if c < a { // (c < e || e < c) < a < b < d
(a, b, c, d, e) = (c < e) ? (c, e, a, b, d) : (e, c, a, b, d)
} else { // e < a < (c < b || b < c) < d
(a, b, c, d, e) = (c < b) ? (e, a, c, b, d) : (e, a, b, c, d)
}
} else { // a < e < b < d
if c < e { // (a < c || c < a) < e < b < d
(a, b, c, d, e) = (c < a) ? (c, a, e, b, d) : (a, c, e, b, d)
} else { // a < e < (c < b || b < c) < d
(a, b, c, d, e) = (c < b) ? (a, e, c, b, d) : (a, e, b, c, d)
}
}
} else {
if e < d { // a < b < e < d
if c < b { // (c < a || a < c) < b < e < d
(a, b, c, d, e) = (c < a) ? (c, a, b, e, d) : (a, c, b, e, d)
} else { // a < b < (c < e || e < c) < d
(a, b, c, d, e) = (c < e) ? (a, b, c, e, d) : (a, b, e, c, d)
}
} else { // a < b < d < e
if c < b { // (c < a || a < c) < b < d < e
(a, b, c, d, e) = (c < a) ? (c, a, b, d, e) : (a, c, b, d, e)
}
// otherwise, a < b < c < d < e
}
}
}
public func sort5<T>
(inout a: T, inout b: T, inout c: T, inout d: T, inout e: T, isOrderedBefore: (T,T) -> Bool)
{
// 1. Setup conditions. (3 comparisons)
// b → d
// ↑ ↑ a < b < d, c < d
// a c e
if isOrderedBefore(b, a) { (a, b) = (b, a) } // a < b
if isOrderedBefore(d, c) { (c, d) = (d, c) } // c < d
if isOrderedBefore(d, b) { (a, b, c, d) = (c, d, a, b) } // a < b < d
// 2. Insert e into the chain of a,b,d with a < b < d. (2 comparisons)
// 3. Insert c into the chain of a,b,d,e with c < d. (2 comparisons)
if isOrderedBefore(e, b) {
if isOrderedBefore(e, a) { // e < a < b < d
if isOrderedBefore(c, a) { // (c < e || e < c) < a < b < d
(a, b, c, d, e) = isOrderedBefore(c, e) ? (c, e, a, b, d) : (e, c, a, b, d)
} else { // e < a < (c < b || b < c) < d
(a, b, c, d, e) = isOrderedBefore(c, b) ? (e, a, c, b, d) : (e, a, b, c, d)
}
} else { // a < e < b < d
if isOrderedBefore(c, e) { // (a < c || c < a) < e < b < d
(a, b, c, d, e) = isOrderedBefore(c, a) ? (c, a, e, b, d) : (a, c, e, b, d)
} else { // a < e < (c < b || b < c) < d
(a, b, c, d, e) = isOrderedBefore(c, b) ? (a, e, c, b, d) : (a, e, b, c, d)
}
}
} else {
if isOrderedBefore(e, d) { // a < b < e < d
if isOrderedBefore(c, b) { // (c < a || a < c) < b < e < d
(a, b, c, d, e) = isOrderedBefore(c, a) ? (c, a, b, e, d) : (a, c, b, e, d)
} else { // a < b < (c < e || e < c) < d
(a, b, c, d, e) = isOrderedBefore(c, e) ? (a, b, c, e, d) : (a, b, e, c, d)
}
} else { // a < b < d < e
if isOrderedBefore(c, b) { // (c < a || a < c) < b < d < e
(a, b, c, d, e) = isOrderedBefore(c, a) ? (c, a, b, d, e) : (a, c, b, d, e)
}
// otherwise, a < b < c < d < e
}
}
}
// MARK: -
// Minimum-Comparison Sorting Algorithm (H. B. Demuth, 1956)
//
// 1. Label first 4 elements, k1,k2,k3,k4. (3 Comparisons)
// Begin as if sorting 4 elements by merging.
// Compare k1,k2; k3,k4; then larger elements of these pairs.
//
// b → d
// ↑ ↑ (a < b < d && c < d, e = k5)
// a c e
//
// 2. Insert e into its proper place among a < b < d. (2 Comparisons)
// b → d
// ↑ ↑ (e < b && e < a)
// e → a c
//
// e → b → d
// ↑ ↑ (e < b && a < e)
// a c
//
// b → e → d
// ↑ ↑ (b < e && e < d)
// a c
//
// b → d → e
// ↑ ↑ (b < e && d < e)
// a c
//
// 3. Insert c among the remaining elements less than d. (2 Comparisons)
//
// ⎧ b → d
// ⎪ ↑ (c < a && c < e)
// ⎪ c → e → a
// ⎪
// ⎪ b → d
// ⎪ ↑ (c < a && e < c)
// ⎪ e → c → a
// b → d ⎪
// ↑ ↑ ⎨
// e → a c ⎪
// ⎪ c → b → d
// ⎪ ↑ (a < c && c < b)
// ⎪ e → a
// ⎪
// ⎪ b → c → d
// ⎪ ↑ (a < c && b < c)
// ⎪ e → a
// ⎩
//
// ⎧
// ⎪ e → b → d
// ⎪ ↑ (c < e && c < a)
// ⎪ c → a
// ⎪
// ⎪ c → e → b → d
// ⎪ ↑ (c < e && a < c)
// ⎪ a
// e → b → d ⎪
// ↑ ↑ ⎨
// a c ⎪
// ⎪ e → c → b → d
// ⎪ ↑ (e < c && c < b)
// ⎪ a
// ⎪
// ⎪ e → b → c → d
// ⎪ ↑ (e < c && b < c)
// ⎪ a
// ⎩
//
// ⎧
// ⎪ b → e → d
// ⎪ ↑ (c < b && c < a)
// ⎪ c → a
// ⎪
// ⎪ c → b → e → d
// ⎪ ↑ (c < b && a < c)
// ⎪ a
// b → e → d ⎪
// ↑ ↑ ⎨
// a c ⎪
// ⎪ b → c → e → d
// ⎪ ↑ (b < c && c < e)
// ⎪ a
// ⎪
// ⎪ b → e → c → d
// ⎪ ↑ (b < c && e < c)
// ⎪ a
// ⎩
//
// ⎧
// ⎪ b → d → e
// ⎪ ↑ (c < b && c < a)
// ⎪ c → a
// ⎪
// ⎪ c → b → d → e
// ⎪ ↑ (c < b && a < c)
// ⎪ a
// b → d → e ⎪
// ↑ ↑ ⎨
// a c ⎪
// ⎪ b → c → d → e
// ⎪ ↑ (b < c)
// ⎪ a
// ⎩
//
// About Directed Graph Diagram
// Convenient way to represent known ordering relations between elements.
// x -> y -> z
// x is known to be less than y iff there exists a path from x to y in the graph.
// MARK: - Sketch
/*
func minimumComparisonSort5<T : Comparable>
(inout k1: T, inout k2: T, inout k3: T, inout k4: T, inout k5: T)
{
// Label first 4 elements: a < b < d and c < d
// b → d
// ↑ ↑
// a c e
var (a, b) = k1 < k2 ? (k1, k2) : (k2, k1) // a < b
var (c, d) = k3 < k4 ? (k3, k4) : (k4, k3) // c < d
if d < b { (a, b, c, d) = (c, d, a, b) } // a < b < d, c < d
let e = k5
// Insert the fifth into its proper place among a < b < d
// then insert c among the remaining elements less than d
if e < b {
if e < a {
// b → d
// ↑ ↑
// e → a c
if c < a {
if c < e {
// b → d
// ↑
// c → e → a
(k1, k2, k3, k4, k5) = (c, e, a, b, d)
} else {
// b → d
// ↑
// e → c → a
(k1, k2, k3, k4, k5) = (e, c, a, b, d)
}
} else { // a < c
if c < b {
// c → b → d
// ↑
// e → a
(k1, k2, k3, k4, k5) = (e, a, c, b, d)
} else {
// b → c → d
// ↑
// e → a
(k1, k2, k3, k4, k5) = (e, a, b, c, d)
}
}
} else {
// e → b → d
// ↑ ↑
// a c
if c < e {
if c < a {
// e → b → d
// ↑
// c → a
(k1, k2, k3, k4, k5) = (c, a, e, b, d)
} else {
// c → e → b → d
// ↑
// a
(k1, k2, k3, k4, k5) = (a, c, e, b, d)
}
} else { // e < c
if c < b {
// e → c → b → d
// ↑
// a
(k1, k2, k3, k4, k5) = (a, e, c, b, d)
} else {
// e → b → c → d
// ↑
// a
(k1, k2, k3, k4, k5) = (a, e, b, c, d)
}
}
}
} else {
if e < d {
// b → e → d
// ↑ ↑
// a c
if c < b {
if c < a {
// b → e → d
// ↑
// c → a
(k1, k2, k3, k4, k5) = (c, a, b, e, d)
} else {
// c → b → e → d
// ↑
// a
(k1, k2, k3, k4, k5) = (a, c, b, e, d)
}
} else { // b < c
if c < e {
// b → c → e → d
// ↑
// a
(k1, k2, k3, k4, k5) = (a, b, c, e, d)
} else {
// b → e → c → d
// ↑
// a
(k1, k2, k3, k4, k5) = (a, b, e, c, d)
}
}
} else { // d < e
// b → d → e
// ↑ ↑
// a c
if c < b {
if c < a {
// b → d → e
// ↑
// c → a
(k1, k2, k3, k4, k5) = (c, a, b, d, e)
} else {
// c → b → d → e
// ↑
// a
(k1, k2, k3, k4, k5) = (a, c, b, d, e)
}
} else {
// b → c → d → e
// ↑
// a
(k1, k2, k3, k4, k5) = (a, b, c, d, e)
}
}
}
}
*/
// MARK: - Testing
// func testSort5() {
// func _bits5(i: Int) -> [Int] {
// let x = Int(i)
// return [
// (x >> 4) & 0b1, (x >> 3) & 0b1,
// (x >> 2) & 0b1, (x >> 1) & 0b1,
// (x >> 0) & 0b1
// ]
// }
//
// for i in 0..<(1 << 5) {
// let t = _bits5(i)
// assert(t.count == 5)
// var lhs = t
// sort5(&lhs[0], &lhs[1], &lhs[2], &lhs[3], &lhs[4])
// let rhs = sorted(t)
// assert(lhs == rhs)
// println("\(lhs) == \(rhs)")
// }
// }
// testSort5()
// MARK: - References
// http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list
//
// Optimal Non-oblivious Sorting
// [Web Exercises #5]: http://algs4.cs.princeton.edu/21elementary/
// > 1. Compare the first two numbers,
// > the second two numbers,
// > and the larger of the two groups,
// > and label them so that a < b < d and c < d.
// >
// > 2. Insert the remaining item e into its proper place in the chain a < b < d by
// > first comparing against b, then either a or d depending on the outcome.
// >
// > 3. Insert c into the proper place in the chain involving a, b, d, and e in the same manner.
// > (with c < d)
// > This uses 3 (first step) + 2 (second step) + 2 (third step) = 7 comparisons.
// > This method was first discovered by H. B. Demuth in 1956.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment