Non-Comparison Sorting

Code

The harness and the verdict

Three files, as in lessons 7 and 8.

ncbench.go adds algo count and algo radix. The first compares counting sort against comparison sorts on the same key; the second runs radix sort with both inner passes and shows the difference.

Note what algo radix prints: not just sorted?, but the first place the unstable version breaks. Showing where a result went wrong is more useful than reporting that it did.

ncsort_test.go — the verdict, with three assertions no earlier lesson made: zero comparisons, exactly n moves, and that the unstable version fails to sort.

main.go — two lines.

Why the comparison uses the same key

algo count sorts by Rating with both counting sort and sort.SliceStable. The same key on the same data — otherwise the comparison would mean nothing.

The insertion-sort row in that table sorts by Title, and is labelled as such. It is there for scale, not as a like-for-like comparison.

ncbench.go CREATE

Create this file in ./

package main

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

	"algo/metrics"
)

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

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

// cmdCount compares counting sort against the comparison sorts on the same
// bounded key.
func cmdCount(args []string) error {
	fs := flag.NewFlagSet("count", flag.ContinueOnError)
	in := fs.String("in", "library.jsonl", "library file")
	if err := fs.Parse(args); err != nil {
		return err
	}
	items, err := load(*in)
	if err != nil {
		return err
	}
	fmt.Printf("n = %d, key = Rating (%d..%d, so k = %d)\n\n",
		len(items), MinRating, MaxRating, MaxRating-MinRating+1)
	fmt.Printf("%-26s %16s %16s %12s\n", "algorithm", "comparisons", "moves", "wall")

	{
		data := append([]Item(nil), items...)
		var c, m metrics.Counter
		start := time.Now()
		out := CountingSortByRating(data, &c, &m)
		el := time.Since(start)
		mark := ""
		if !isSortedByRating(out) {
			mark = "  ** NOT SORTED **"
		}
		fmt.Printf("%-26s %16d %16d %12s%s\n", "counting", c.N(), m.N(), el.Round(time.Microsecond), mark)
	}
	// The comparison sorts, on the same key, for scale.
	{
		data := append([]Item(nil), items...)
		var c metrics.Counter
		start := time.Now()
		sort.SliceStable(data, func(i, j int) bool {
			c.Hit()
			return data[i].Rating < data[j].Rating
		})
		el := time.Since(start)
		fmt.Printf("%-26s %16d %16s %12s\n", "sort.SliceStable", c.N(), "(hidden)", el.Round(time.Microsecond))
	}
	{
		data := append([]Item(nil), items...)
		var c, m metrics.Counter
		start := time.Now()
		InsertionSort(data, &c, &m) // by Title, but the count is what we want
		el := time.Since(start)
		fmt.Printf("%-26s %16d %16d %12s   (by Title, for scale)\n",
			"insertion (lesson 7)", c.N(), m.N(), el.Round(time.Microsecond))
	}
	return nil
}

// cmdRadix sorts by Year and demonstrates what an unstable inner pass does.
func cmdRadix(args []string) error {
	fs := flag.NewFlagSet("radix", flag.ContinueOnError)
	in := fs.String("in", "library.jsonl", "library file")
	if err := fs.Parse(args); err != nil {
		return err
	}
	items, err := load(*in)
	if err != nil {
		return err
	}
	fmt.Printf("n = %d, key = Year (%d..%d), 4 passes of base-10 counting sort\n\n",
		len(items), MinYear, MaxYear)
	fmt.Printf("%-30s %14s %14s %12s %s\n", "inner pass", "comparisons", "moves", "wall", "sorted?")

	var c1, m1 metrics.Counter
	t1 := time.Now()
	good := RadixSortByYear(items, &c1, &m1)
	e1 := time.Since(t1)
	fmt.Printf("%-30s %14d %14d %12s %v\n", "stable (backwards)", c1.N(), m1.N(), e1.Round(time.Microsecond), isSortedByYear(good))

	var c2, m2 metrics.Counter
	t2 := time.Now()
	bad := RadixSortByYearUnstable(items, &c2, &m2)
	e2 := time.Since(t2)
	fmt.Printf("%-30s %14d %14d %12s %v\n", "UNSTABLE (forwards)", c2.N(), m2.N(), e2.Round(time.Microsecond), isSortedByYear(bad))

	// Show the first place the unstable version goes wrong.
	for i := 1; i < len(bad); i++ {
		if bad[i-1].Year > bad[i].Year {
			lo := i - 3
			if lo < 0 {
				lo = 0
			}
			hi := i + 3
			if hi > len(bad) {
				hi = len(bad)
			}
			fmt.Printf("\nfirst break in the unstable run, at index %d:\n  ", i)
			for j := lo; j < hi; j++ {
				fmt.Printf("%d ", bad[j].Year)
			}
			fmt.Println()
			break
		}
	}
	return nil
}

ncsort_test.go CREATE

Create this file in ./

package main

import (
	"fmt"
	"testing"

	"algo/metrics"
)

func ratedLib(n int) []Item {
	s := make([]Item, n)
	for i := range s {
		s[i] = Item{
			ID:     i + 1,
			Title:  fmt.Sprintf("%06d", i),
			Rating: MinRating + (i*37)%(MaxRating-MinRating+1),
			Year:   MinYear + (i*17)%(MaxYear-MinYear+1),
		}
	}
	return s
}

func TestCountingSortOrders(t *testing.T) {
	for _, n := range []int{0, 1, 2, 3, 1000} {
		var c, m metrics.Counter
		out := CountingSortByRating(ratedLib(n), &c, &m)
		if len(out) != n {
			t.Fatalf("n=%d: got %d items", n, len(out))
		}
		if !isSortedByRating(out) {
			t.Fatalf("n=%d: not sorted by Rating", n)
		}
	}
}

// THE HEADLINE. Not "fewer comparisons" — none at all. If this number is ever
// non-zero, the implementation has stopped being a counting sort.
func TestCountingSortMakesZeroComparisons(t *testing.T) {
	var c, m metrics.Counter
	CountingSortByRating(ratedLib(10000), &c, &m)
	if c.N() != 0 {
		t.Errorf("comparisons = %d, want exactly 0", c.N())
	}
	// And exactly one move per item: each is placed once.
	if m.N() != 10000 {
		t.Errorf("moves = %d, want exactly %d (one per item)", m.N(), 10000)
	}
}

// Counting sort must be STABLE — and radix depends on it, which the next test
// makes concrete.
func TestCountingSortIsStable(t *testing.T) {
	in := []Item{
		{ID: 1, Rating: 5}, {ID: 2, Rating: 3}, {ID: 3, Rating: 5},
		{ID: 4, Rating: 3}, {ID: 5, Rating: 5},
	}
	var c, m metrics.Counter
	out := CountingSortByRating(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))
		}
	}
}

func TestRadixSortOrders(t *testing.T) {
	for _, n := range []int{0, 1, 2, 3, 5000} {
		var c, m metrics.Counter
		out := RadixSortByYear(ratedLib(n), &c, &m)
		if !isSortedByYear(out) {
			t.Fatalf("n=%d: not sorted by Year", n)
		}
		if c.N() != 0 {
			t.Errorf("n=%d: comparisons = %d, want 0", n, c.N())
		}
	}
}

// STABILITY AS A CORRECTNESS PRECONDITION, asserted.
//
// Radix sort works by sorting on the least significant digit first and relying
// on every later pass to PRESERVE that order. Take the stability away and the
// algorithm does not get untidy — it produces the wrong answer, with exactly
// the same number of comparisons and moves.
func TestRadixIsWrongWithAnUnstableInnerPass(t *testing.T) {
	in := ratedLib(1000)

	var c1, m1 metrics.Counter
	good := RadixSortByYear(in, &c1, &m1)
	if !isSortedByYear(good) {
		t.Fatal("the stable version must sort correctly")
	}

	var c2, m2 metrics.Counter
	bad := RadixSortByYearUnstable(in, &c2, &m2)
	if isSortedByYear(bad) {
		t.Fatal("the unstable version came out sorted — the demonstration has stopped working")
	}

	// Same work, different answer. That is the whole point.
	if m1.N() != m2.N() || c1.N() != c2.N() {
		t.Errorf("the two runs did different amounts of work (%d/%d vs %d/%d); "+
			"they should differ only in correctness", c1.N(), m1.N(), c2.N(), m2.N())
	}
	t.Logf("identical work — %d comparisons, %d moves — and only one is correct", c1.N(), m1.N())
}

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]
  algo count [-in FILE]
  algo radix [-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:])
	case "dc":
		err = cmdDC(os.Args[2:])
	case "stable":
		err = cmdStable(os.Args[2:])
	case "count":
		err = cmdCount(os.Args[2:])
	case "radix":
		err = cmdRadix(os.Args[2:])
	default:
		usage()
		os.Exit(2)
	}
	if err != nil {
		fmt.Fprintln(os.Stderr, "algo:", err)
		os.Exit(1)
	}
}