Kodas

sort.go — karkasas tau užpildyti

Sukurk sort.go (žr. dešinėje).

Failas dešinėje yra pilnas ir teisingas — jį sukursi lygiai tokį. Jame yra paketas, importas, trys parašai, sutartys ir po panic("not implemented").

Tavo darbas — pakeisti tuos tris panic tikru kodu, remiantis praeito žingsnio pseudokodu.

Perskaityk sutartis, ne tik parašus

Doc komentaruose surašyta viskas, ką testas tikrins:

BubbleSort — stabilus; surikiuotam masyvui lygiai n−1 palyginimų;
SelectionSort — ne stabilus; lygiai n(n−1)/2 palyginimų bet kokiai įvesčiai; ne daugiau kaip n−1 sukeitimų;
InsertionSort — stabilus; surikiuotam masyvui lygiai n−1 palyginimų ir nulis sukeitimų.

Trys iš šių reikalavimų yra tikslūs skaičiai, ne ribos. Jei tavo realizacija duoda n vietoj n−1, testas tai pagaus — ir tai bus tikra klaida, ne priekabė: reiškia, kad kažką palygini du kartus arba lygini elementą su savimi.

sort.go SUKURTI

Sukurk šį failą kataloge ./

package main

import "algo/metrics"

// This file is YOURS to fill in. Everything below is a signature, a contract
// and a panic. The algorithms are described in step 2; sort_test.go decides
// whether you got them right.
//
// Shared rules for all three:
//   - sort IN PLACE, ascending by Title;
//   - every comparison between two Titles goes through cmp.Hit();
//   - every exchange of two elements goes through swap.Hit();
//   - the counts must be deterministic: same input, same numbers, every run.

// BubbleSort repeatedly walks the slice, swapping any two NEIGHBOURS that are
// out of order, until a whole pass makes no swaps.
//
// MUST BE STABLE: equal Titles keep their original relative order. You get this
// for free if you only ever swap neighbours and only when strictly out of order
// (> , never >=).
//
// On already-sorted input it must do exactly n-1 comparisons and stop.
func BubbleSort(items []Item, cmp, swap *metrics.Counter) {
	panic("not implemented")
}

// SelectionSort finds the smallest remaining Title and swaps it into place,
// once per position.
//
// NOT STABLE, and you are not asked to make it so — see step 5. Its long-range
// swap can throw one equal item past another. That is the price of its one
// advantage.
//
// It must do exactly n(n-1)/2 comparisons on EVERY input, sorted or not, and at
// most n-1 swaps.
func SelectionSort(items []Item, cmp, swap *metrics.Counter) {
	panic("not implemented")
}

// InsertionSort takes each item in turn and shifts it left until it sits in
// order among the items already handled.
//
// MUST BE STABLE: stop shifting as soon as the item to the left is <= the one
// being placed, so equal items never cross.
//
// On already-sorted input it must do exactly n-1 comparisons and ZERO swaps.
// That property is the whole point of this lesson.
func InsertionSort(items []Item, cmp, swap *metrics.Counter) {
	panic("not implemented")
}