Efficient Sorting — Programuoki

Code

The harness and the verdict

Three files, as in lesson 7: the harness, the test, and two lines of main.go.

dcbench.go adds two commands. algo dc runs all four algorithms on the same order and prints the numbers; algo stable is the eight-row demonstration you will see in the next step.

As in lesson 7, every measurement checks the result first — isSortedByTitle. The speed of an incorrect sort means nothing.

dcsort_test.go — the verdict. Two of its tests are unusual:

TestQuickSortIsNotStable asserts a defect. It is the same shape as lesson 7's selection-sort test: if your quicksort ever comes out stable, the test will say so — and then it is worth checking what that cost.

TestNaivePivotIsQuadraticOnSortedInput asserts a worst case. Not "slow", but exactly n(n−1)/2. That line exists so the failure stays written down instead of being quietly fixed and forgotten.

dcbench.go CREATE

Create this file in ./

package main

import (
	"flag"
	"fmt"
	"sort"
	"time"

	"algo/metrics"
)

// cmdDC runs the divide-and-conquer sorts and reports counts and wall time.
func cmdDC(args []string) error {
	fs := flag.NewFlagSet("dc", flag.ContinueOnError)
	in := fs.String("in", "library.jsonl", "library file")
	order := fs.String("order", "shuffled", "shuffled | sorted | reverse | nearly")
	seed := fs.Int64("seed", 1, "seed for -order nearly")
	if err := fs.Parse(args); err != nil {
		return err
	}
	items, err := load(*in)
	if err != nil {
		return err
	}

	fmt.Printf("n = %d, order = %s\n\n", len(items), *order)
	fmt.Printf("%-22s %16s %16s %12s\n", "algorithm", "comparisons", "moves", "wall")

	run := func(name string, f func([]Item, *metrics.Counter, *metrics.Counter)) {
		data := prepare(items, *order, *seed)
		var cmp, mv metrics.Counter
		start := time.Now()
		f(data, &cmp, &mv)
		el := time.Since(start)
		ok := isSortedByTitle(data)
		mark := ""
		if !ok {
			mark = "  ** NOT SORTED **"
		}
		fmt.Printf("%-22s %16d %16d %12s%s\n", name, cmp.N(), mv.N(), el.Round(time.Microsecond), mark)
	}

	// Merge sort returns a new slice, so it gets its own wrapper.
	{
		data := prepare(items, *order, *seed)
		var cmp, mv metrics.Counter
		start := time.Now()
		out := MergeSort(data, &cmp, &mv)
		el := time.Since(start)
		mark := ""
		if !isSortedByTitle(out) {
			mark = "  ** NOT SORTED **"
		}
		fmt.Printf("%-22s %16d %16d %12s%s\n", "merge", cmp.N(), mv.N(), el.Round(time.Microsecond), mark)
	}
	run("quick (first pivot)", QuickSortNaive)
	run("quick (median-of-3)", QuickSortMedian3)
	run("quick (random)", QuickSortRandom)
	return nil
}

// cmdStable is the smallest example that makes stability visible.
//
// Sort by Rating first, then by Artist. A STABLE sort by Artist leaves the
// ratings in order inside each artist; an unstable one scrambles them.
func cmdStable(args []string) error {
	fs := flag.NewFlagSet("stable", flag.ContinueOnError)
	n := fs.Int("n", 8, "how many rows to show")
	if err := fs.Parse(args); err != nil {
		return err
	}
	// A deliberately tiny library: two artists, four ratings each.
	//
	// Title carries the ARTIST here, because your MergeSort and QuickSort sort
	// by Title — so this makes the second key the artist without needing a
	// second set of sort functions.
	mk := func(id int, artist string, rating int) Item {
		return Item{ID: id, Artist: artist, Title: artist, Rating: rating}
	}
	base := []Item{
		mk(1, "Nova", 10), mk(2, "Vega", 20), mk(3, "Nova", 30), mk(4, "Vega", 40),
		mk(5, "Nova", 50), mk(6, "Vega", 60), mk(7, "Nova", 70), mk(8, "Vega", 80),
	}
	if *n < len(base) {
		base = base[:*n]
	}

	byRating := func(items []Item) []Item {
		out := append([]Item(nil), items...)
		sort.SliceStable(out, func(i, j int) bool { return out[i].Rating < out[j].Rating })
		return out
	}
	show := func(label string, items []Item) {
		fmt.Printf("%-24s", label)
		for _, it := range items {
			fmt.Printf(" %s/%d", it.Artist[:1], it.Rating)
		}
		fmt.Println()
	}

	step1 := byRating(base)
	show("1. sorted by rating:", step1)

	// Now sort THAT by artist, two ways.
	var c1, m1 metrics.Counter
	stable := MergeSort(step1, &c1, &m1)
	show("2a. then by artist (merge):", stable)

	unstable := append([]Item(nil), step1...)
	var c2, m2 metrics.Counter
	QuickSortMedian3(unstable, &c2, &m2)
	show("2b. then by artist (quick):", unstable)

	fmt.Println()
	fmt.Println("read the ratings inside each artist:")
	fmt.Println("  merge keeps them ascending — the rating sort survived")
	fmt.Println("  quick scrambles them   — the rating sort was destroyed")
	return nil
}

dcsort_test.go CREATE

Create this file in ./

package main

import (
	"fmt"
	"math"
	"testing"

	"algo/metrics"
)

func sortedLibN(n int) []Item {
	s := make([]Item, n)
	for i := range s {
		s[i] = Item{ID: i + 1, Title: fmt.Sprintf("%06d", i)}
	}
	return s
}

func reverseLibN(n int) []Item {
	s := make([]Item, n)
	for i := range s {
		s[i] = Item{ID: i + 1, Title: fmt.Sprintf("%06d", n-i)}
	}
	return s
}

func TestDivideAndConquerSorts(t *testing.T) {
	for _, n := range []int{0, 1, 2, 3, 10, 257} {
		t.Run(fmt.Sprintf("merge n=%d", n), func(t *testing.T) {
			in := shuffledLib(n)
			var c, m metrics.Counter
			out := MergeSort(in, &c, &m)
			if len(out) != n {
				t.Fatalf("returned %d items, want %d", len(out), n)
			}
			if !isSortedByTitle(out) {
				t.Fatal("not sorted")
			}
			// MergeSort must NOT modify its input.
			if n > 2 && isSortedByTitle(in) {
				t.Error("the input was modified — MergeSort must return a new slice")
			}
		})
		for _, q := range []struct {
			name string
			fn   func([]Item, *metrics.Counter, *metrics.Counter)
		}{{"naive", QuickSortNaive}, {"median3", QuickSortMedian3}, {"random", QuickSortRandom}} {
			t.Run(fmt.Sprintf("quick-%s n=%d", q.name, n), func(t *testing.T) {
				data := shuffledLib(n)
				var c, m metrics.Counter
				q.fn(data, &c, &m)
				if !isSortedByTitle(data) {
					t.Fatal("not sorted")
				}
			})
		}
	}
}

// Merge sort is STABLE. Bubble and insertion were too (lesson 7); merge is the
// first O(n log n) sort that keeps the property.
func TestMergeSortIsStable(t *testing.T) {
	in := []Item{
		{ID: 1, Title: "b"}, {ID: 2, Title: "a"}, {ID: 3, Title: "b"},
		{ID: 4, Title: "a"}, {ID: 5, Title: "b"},
	}
	var c, m metrics.Counter
	out := MergeSort(in, &c, &m)
	want := []int{2, 4, 1, 3, 5}
	for i, id := range want {
		if out[i].ID != id {
			t.Fatalf("position %d has ID %d, want %d — not stable (got %v)", i, out[i].ID, id, ids(out))
		}
	}
}

// Quicksort is NOT stable, and this asserts the defect so it stays visible —
// the same shape as lesson 7's selection-sort test.
func TestQuickSortIsNotStable(t *testing.T) {
	data := []Item{
		{ID: 1, Title: "b"}, {ID: 2, Title: "a"}, {ID: 3, Title: "b"},
		{ID: 4, Title: "a"}, {ID: 5, Title: "b"}, {ID: 6, Title: "a"},
	}
	var c, m metrics.Counter
	QuickSortMedian3(data, &c, &m)
	if !isSortedByTitle(data) {
		t.Fatal("not sorted")
	}
	stable := []int{2, 4, 6, 1, 3, 5}
	same := true
	for i, id := range stable {
		if data[i].ID != id {
			same = false
		}
	}
	if same {
		t.Fatalf("quicksort came out stable (%v) — surprising; check what it cost", ids(data))
	}
	t.Logf("quicksort is NOT stable: got %v, a stable sort would give %v", ids(data), stable)
}

// MERGE SORT'S CEILING. n*ceil(log2 n) is the bound; a correct merge sort is
// comfortably under it on every input, INCLUDING the sorted and reverse cases
// that destroy a naive quicksort.
func TestMergeSortIsNLogNOnEveryInput(t *testing.T) {
	const n = 1024
	ceiling := int64(float64(n) * math.Ceil(math.Log2(n)))
	for _, tc := range []struct {
		name string
		in   []Item
	}{
		{"shuffled", shuffledLib(n)},
		{"sorted", sortedLibN(n)},
		{"reverse", reverseLibN(n)},
	} {
		t.Run(tc.name, func(t *testing.T) {
			var c, m metrics.Counter
			MergeSort(tc.in, &c, &m)
			if c.N() > ceiling {
				t.Errorf("%d comparisons, ceiling n*ceil(log2 n) = %d", c.N(), ceiling)
			}
		})
	}
}

// THE BLOW-UP, ASSERTED. A first-element pivot on sorted input is not "a bit
// slower" — it is exactly the quadratic count, the same n(n-1)/2 as lesson 7's
// elementary sorts. This test exists so the failure mode cannot be forgotten.
func TestNaivePivotIsQuadraticOnSortedInput(t *testing.T) {
	const n = 512
	want := int64(n * (n - 1) / 2)
	var c, m metrics.Counter
	QuickSortNaive(sortedLibN(n), &c, &m)
	if c.N() != want {
		t.Errorf("comparisons on sorted input = %d, want exactly %d (the quadratic count)", c.N(), want)
	}
}

// And the fix, asserted for the case it actually fixes.
func TestMedian3RescuesSortedInput(t *testing.T) {
	const n = 512
	quadratic := int64(n * (n - 1) / 2)
	var c, m metrics.Counter
	QuickSortMedian3(sortedLibN(n), &c, &m)
	if c.N() > quadratic/10 {
		t.Errorf("median-of-three on sorted input used %d comparisons; expected far below %d", c.N(), quadratic/10)
	}
}

main.go MODIFY 6 lines changed

Edit this file in ./

package main

import (
	"fmt"
	"os"
)

func usage() {
	fmt.Fprint(os.Stderr, `algo — your library workbench

  algo gen  [-n N] [-seed S] [-o FILE] [-sorted|-reverse|-shuffled] [-dup-rate R]
  algo find -title TITLE [-in FILE]
  algo load [-in FILE]
  algo stats -growth [-n N]
  algo playlist -from I -to J [-in FILE]
  algo history [-n N] [-in FILE]
  algo queue [-n N]
  algo walk [-depth D] [-branch B] [-per P]
  algo depth -n N [-iterative]
  algo sweep [-scattered]
  algo std [-n N]
  algo sort [-algo A] [-order O] [-in FILE]
  algo dc [-order O] [-in FILE]
  algo stable [-n N]
`)
}

func main() {
	if len(os.Args) < 2 {
		usage()
		os.Exit(2)
	}
	var err error
	switch os.Args[1] {
	case "gen":
		err = cmdGen(os.Args[2:])
	case "find":
		err = cmdFind(os.Args[2:])
	case "load":
		err = cmdLoad(os.Args[2:])
	case "stats":
		err = cmdStats(os.Args[2:])
	case "playlist":
		err = cmdPlaylist(os.Args[2:])
	case "history":
		err = cmdHistory(os.Args[2:])
	case "queue":
		err = cmdQueue(os.Args[2:])
	case "walk":
		err = cmdWalk(os.Args[2:])
	case "depth":
		err = cmdDepth(os.Args[2:])
	case "sweep":
		err = cmdSweep(os.Args[2:])
	case "std":
		err = cmdStd(os.Args[2:])
	case "sort":
		err = cmdSort(os.Args[2:])
	case "dc":
		err = cmdDC(os.Args[2:])
	case "stable":
		err = cmdStable(os.Args[2:])
	default:
		usage()
		os.Exit(2)
	}
	if err != nil {
		fmt.Fprintln(os.Stderr, "algo:", err)
		os.Exit(1)
	}
}