Elementary Sorting — Programuoki

Code

The harness and the verdict

Three files in one step. Two of them you are given complete — they are not the exercise.

sortbench.go — the measuring harness. prepare puts the data in the requested order (shuffled, sorted, reverse, nearly), and cmdSort runs the chosen algorithms and prints the numbers.

One thing in it matters:

if !isSortedByTitle(data) {
    return fmt.Errorf("%s did NOT sort the data", name)
}

Every measurement checks the result first. The speed of an incorrect sort means nothing — and an incorrect sort often looks fast, precisely because it did less work. In lesson 6 the same principle was phrased as "prove they are the same function first".

sort_test.go — the verdict. You do not write it; you pass it.

And main.go — two lines, as usual.

What the test demands

Four groups:

It sorts — including n = 0, 1, 2 and 3. An empty slice and a one-element slice must pass without any special-case branches in your code.
Stability — bubble and insertion. Checked through the IDs, because only they reveal which items moved past which.
Instability — selection. This test asserts a defect, so that it stays visible.
Exact counts — n−1, n(n−1)/2, and the quadratic ceiling.

If the test passes, your three functions are correct and have the correct cost.

sortbench.go CREATE

Create this file in ./

package main

import (
	"flag"
	"fmt"
	"math/rand"
	"sort"
	"time"

	"algo/metrics"
)

// prepare returns a copy of items in the requested order.
//
//	shuffled — as generated
//	sorted   — ascending by Title (the BEST case for insertion sort)
//	reverse  — descending (the WORST case)
//	nearly   — sorted, then 1% of positions swapped at random
func prepare(items []Item, order string, seed int64) []Item {
	out := append([]Item(nil), items...)
	switch order {
	case "sorted":
		sort.Slice(out, func(i, j int) bool { return out[i].Title < out[j].Title })
	case "reverse":
		sort.Slice(out, func(i, j int) bool { return out[i].Title > out[j].Title })
	case "nearly":
		sort.Slice(out, func(i, j int) bool { return out[i].Title < out[j].Title })
		rng := rand.New(rand.NewSource(seed))
		swaps := len(out) / 100
		for k := 0; k < swaps; k++ {
			a, b := rng.Intn(len(out)), rng.Intn(len(out))
			out[a], out[b] = out[b], out[a]
		}
	}
	return out
}

var sorters = map[string]func([]Item, *metrics.Counter, *metrics.Counter){
	"bubble":    BubbleSort,
	"selection": SelectionSort,
	"insertion": InsertionSort,
}

func cmdSort(args []string) error {
	fs := flag.NewFlagSet("sort", flag.ContinueOnError)
	in := fs.String("in", "library.jsonl", "library file")
	algo := fs.String("algo", "all", "bubble | selection | insertion | all")
	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
	}

	names := []string{"bubble", "selection", "insertion"}
	if *algo != "all" {
		if _, ok := sorters[*algo]; !ok {
			return fmt.Errorf("unknown -algo %q", *algo)
		}
		names = []string{*algo}
	}

	fmt.Printf("n = %d, order = %s\n\n", len(items), *order)
	fmt.Printf("%-12s %16s %16s %12s\n", "algorithm", "comparisons", "swaps", "wall")
	for _, name := range names {
		data := prepare(items, *order, *seed)
		var cmp, swap metrics.Counter
		start := time.Now()
		sorters[name](data, &cmp, &swap)
		el := time.Since(start)
		if !isSortedByTitle(data) {
			return fmt.Errorf("%s did NOT sort the data", name)
		}
		fmt.Printf("%-12s %16d %16d %12s\n", name, cmp.N(), swap.N(), el.Round(time.Microsecond))
	}
	return nil
}

func isSortedByTitle(items []Item) bool {
	for i := 1; i < len(items); i++ {
		if items[i-1].Title > items[i].Title {
			return false
		}
	}
	return true
}

sort_test.go CREATE

Create this file in ./

package main

import (
	"fmt"
	"testing"

	"algo/metrics"
)

type sorter struct {
	name string
	fn   func([]Item, *metrics.Counter, *metrics.Counter)
}

func allSorters() []sorter {
	return []sorter{
		{"bubble", BubbleSort},
		{"selection", SelectionSort},
		{"insertion", InsertionSort},
	}
}

func shuffledLib(n int) []Item {
	s := make([]Item, n)
	for i := range s {
		// A deterministic scramble: no rand, so every run is identical.
		s[i] = Item{ID: i + 1, Title: fmt.Sprintf("%05d", (i*7919)%n)}
	}
	return s
}

func TestSortsProduceSortedOutput(t *testing.T) {
	for _, s := range allSorters() {
		t.Run(s.name, func(t *testing.T) {
			for _, n := range []int{0, 1, 2, 3, 10, 257} {
				data := shuffledLib(n)
				var c, w metrics.Counter
				s.fn(data, &c, &w)
				for i := 1; i < len(data); i++ {
					if data[i-1].Title > data[i].Title {
						t.Fatalf("n=%d: not sorted at %d", n, i)
					}
				}
			}
		})
	}
}

// STABILITY, and the fact that ONE OF THE THREE DOES NOT HAVE IT.
//
// A stable sort keeps equal Titles in their original relative order — visible
// only by watching the IDs. Bubble and insertion are stable: they only ever
// swap NEIGHBOURS, so two equal items can never cross.
//
// Selection sort is not, and cannot be made so without giving up the thing it
// is good at. It swaps across arbitrary distances, and that long-range swap can
// throw an equal item over another. That is the trade: the fewest swaps of the
// three, paid for with the order of equal keys.
func TestBubbleAndInsertionAreStable(t *testing.T) {
	build := func() []Item {
		return []Item{
			{ID: 1, Title: "b"}, {ID: 2, Title: "a"}, {ID: 3, Title: "b"},
			{ID: 4, Title: "a"}, {ID: 5, Title: "b"},
		}
	}
	want := []int{2, 4, 1, 3, 5} // the a's in order 2,4; then the b's in order 1,3,5
	for _, s := range []sorter{{"bubble", BubbleSort}, {"insertion", InsertionSort}} {
		t.Run(s.name, func(t *testing.T) {
			data := build()
			var c, w metrics.Counter
			s.fn(data, &c, &w)
			for i, id := range want {
				if data[i].ID != id {
					t.Fatalf("position %d has ID %d, want %d — not stable (got %v)",
						i, data[i].ID, id, ids(data))
				}
			}
		})
	}
}

// This one asserts the DEFECT, so it stays visible. If you ever make selection
// sort stable, this test tells you — and you should then check what it cost.
func TestSelectionSortIsNotStable(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"},
	}
	var c, w metrics.Counter
	SelectionSort(data, &c, &w)
	stable := []int{2, 4, 1, 3, 5}
	same := true
	for i, id := range stable {
		if data[i].ID != id {
			same = false
		}
	}
	if same {
		t.Fatalf("selection sort came out stable (%v) — surprising; check what it cost in swaps", ids(data))
	}
	t.Logf("selection sort is NOT stable: got %v, a stable sort would give %v", ids(data), stable)
}

func ids(items []Item) []int {
	out := make([]int, len(items))
	for i, it := range items {
		out[i] = it.ID
	}
	return out
}

// THE COUNTS ARE THE SPECIFICATION. These are not approximate: each algorithm
// has an exact comparison count on sorted input, and no algorithm may exceed
// the quadratic ceiling on any input.
func TestComparisonCountsAreExact(t *testing.T) {
	const n = 100
	ceiling := int64(n * (n - 1) / 2)

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

	t.Run("insertion on sorted input does exactly n-1", func(t *testing.T) {
		var c, w metrics.Counter
		InsertionSort(sortedLib(), &c, &w)
		if c.N() != n-1 {
			t.Errorf("comparisons = %d, want %d", c.N(), n-1)
		}
		if w.N() != 0 {
			t.Errorf("swaps = %d, want 0 — sorted input needs no movement", w.N())
		}
	})

	t.Run("selection always does exactly n(n-1)/2", func(t *testing.T) {
		var c, w metrics.Counter
		SelectionSort(sortedLib(), &c, &w)
		if c.N() != ceiling {
			t.Errorf("comparisons on SORTED input = %d, want %d — selection sort has no best case", c.N(), ceiling)
		}
	})

	t.Run("selection does at most n-1 swaps", func(t *testing.T) {
		var c, w metrics.Counter
		SelectionSort(shuffledLib(n), &c, &w)
		if w.N() > n-1 {
			t.Errorf("swaps = %d, want at most %d", w.N(), n-1)
		}
	})

	t.Run("nobody exceeds the quadratic ceiling", func(t *testing.T) {
		for _, s := range allSorters() {
			var c, w metrics.Counter
			s.fn(shuffledLib(n), &c, &w)
			if c.N() > ceiling {
				t.Errorf("%s: %d comparisons, ceiling is %d", s.name, c.N(), ceiling)
			}
		}
	})
}

main.go MODIFY 3 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]
`)
}

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:])
	default:
		usage()
		os.Exit(2)
	}
	if err != nil {
		fmt.Fprintln(os.Stderr, "algo:", err)
		os.Exit(1)
	}
}