Kodas

ncsort.go — karkasas

Sukurk ncsort.go (žr. dešinėje). Šeši parašai, ir vienas reikalavimas skiriasi nuo visų ankstesnių pamokų.

`cmp.Hit()` — nė karto

Iki šiol skaitikliai skaičiavo, kiek palyginimų. Čia testas reikalauja, kad jų būtų lygiai nulis.

cmp parametras vis tiek yra — kad parašas sutaptų su kitais rikiavimais ir kad testas galėtų įrodyti, jog skaičius nulinis. Jei kur nors atsiras cmp.Hit(), tai jau nebe skaičiavimo rikiavimas.

moves.Hit() lieka: po vieną kiekvienam į rezultatą įrašytam elementui.

Ką testas tikrins

CountingSortByRating — teisinga tvarka, 0 palyginimų, lygiai n judesių ir stabilumas;
RadixSortByYear — teisinga tvarka, 0 palyginimų;
RadixSortByYearUnstable — privalo nesurikiuoti, ir privalo atlikti tiek pat darbo kaip stabilus variantas.

Paskutinis punktas neįprastas: rašai funkciją, kuri turi būti neteisinga. Ji sugadinta tyčia, viena ciklo kryptimi, ir 7 žingsnyje pamatysi, kam.

Rėžiai, kuriuos jau turi

CountingSortByRating naudoja MinRating ir MaxRating iš item.go — konstantas, kurias parašei pirmoje pamokoje. yearDigit ir countingPass dirba su Year.

Nieko naujo pridėti nereikia. Prielaida, kurios reikia šiai pamokai, jau įrašyta tavo duomenų tipe aštuonios pamokos.

ncsort.go SUKURTI

Sukurk šį failą kataloge ./

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 — karkasas

cmp.Hit() — nė karto

Ką testas tikrins

Rėžiai, kuriuos jau turi

`cmp.Hit()` — nė karto