Non-Comparison Sorting

Code

ncsort.go — the skeleton

Create ncsort.go (see the panel). Six signatures, and one requirement differs from every earlier lesson.

`cmp.Hit()` — not once

Until now the counters measured how many comparisons. Here the test demands exactly zero.

The cmp parameter is still there — so the signature matches the other sorts, and so the test can prove the count is zero. If a cmp.Hit() appears anywhere, it has stopped being a counting sort.

moves.Hit() stays: one per element written into the output.

What the test checks

CountingSortByRating — correct order, 0 comparisons, exactly n moves, and stability;
RadixSortByYear — correct order, 0 comparisons;
RadixSortByYearUnstable — must fail to sort, and must do the same amount of work as the stable version.

That last one is unusual: you are writing a function that has to be wrong. It is broken deliberately, by one loop direction, and step 7 shows what for.

The bounds you already have

CountingSortByRating uses MinRating and MaxRating from item.go — the constants you wrote in lesson 1. yearDigit and countingPass work on Year.

Nothing new needs adding. The assumption this lesson depends on has been in your data type for eight lessons.

ncsort.go CREATE

Create this file in ./

package main

import "algo/metrics"

// This file is YOURS to fill in. The algorithms are in step 2; ncsort_test.go
// decides whether you got them right.
//
// One rule is different from every earlier lesson: cmp.Hit() must be called
// ZERO times. Not rarely — never. These sorts do not compare items at all, and
// the test asserts the count is exactly 0.
//
// moves.Hit() is still called once per element written into the output.

// CountingSortByRating returns a NEW slice ordered by Rating, ascending.
//
// MUST BE STABLE, and must make exactly one move per item — each element is
// placed once, never shifted afterwards.
//
// It takes cmp only so its signature matches the other sorts, and so the test
// can prove the count is zero.
//
// Uses MinRating and MaxRating from item.go — the bounds you wrote in lesson 1.
func CountingSortByRating(items []Item, cmp, moves *metrics.Counter) []Item {
	panic("not implemented")
}

// yearDigit returns the given base-10 digit of a Year; digit 0 is the ones.
func yearDigit(year, digit int) int {
	panic("not implemented")
}

// countingPass is ONE stable counting sort over a single base-10 digit of Year.
// Ten buckets, whatever the size of the year range.
//
// MUST BE STABLE. RadixSortByYear is correct only because this is — step 6
// shows what happens when it is not.
func countingPass(items []Item, digit int, moves *metrics.Counter) []Item {
	panic("not implemented")
}

// countingPassUnstable is countingPass with ONE change: it walks the input
// forwards instead of backwards, so equal digits come out reversed.
//
// It exists to be broken. Do not fix it.
func countingPassUnstable(items []Item, digit int, moves *metrics.Counter) []Item {
	panic("not implemented")
}

// RadixSortByYear returns a NEW slice ordered by Year, ascending: four
// countingPass calls, least significant digit first. ZERO comparisons.
func RadixSortByYear(items []Item, cmp, moves *metrics.Counter) []Item {
	panic("not implemented")
}

// RadixSortByYearUnstable is the same four passes through countingPassUnstable.
// It is here to fail, and the test asserts that it does — with exactly the same
// comparison and move counts as the correct version.
func RadixSortByYearUnstable(items []Item, cmp, moves *metrics.Counter) []Item {
	panic("not implemented")
}

ncsort.go — the skeleton

cmp.Hit() — not once

What the test checks

The bounds you already have

`cmp.Hit()` — not once