Kodas

dcsort.go — karkasas

Sukurk dcsort.go (žr. dešinėje). Keturi parašai, keturios sutartys, keturi panic.

Trys iš keturių yra tas pats greitasis rikiavimas su skirtingu pivotu, tad Partition parašysi vieną kartą ir panaudosi tris.

Ką testas tikrins

MergeSort — stabilus, negrąžina to paties masyvo (įvestis nekeičiama), ir neviršija n·⌈log₂ n⌉ palyginimų nė vienai tvarkai;
QuickSortNaive — surikiuotiems duomenims lygiai n(n−1)/2 palyginimų. Testas reikalauja būtent šito skaičiaus, nes klaida čia yra pamoka;
QuickSortMedian3 — surikiuotiems duomenims gerokai mažiau nei kvadratas;
QuickSortRandom — sėkla fiksuota (rand.NewSource(1)), kad skaičiai kartotųsi.

Vienas dalykas, kurį lengva praleisti

MergeSort grąžina naują masyvą, o ne rikiuoja vietoje. Testas tikrina, kad įvestis liktų nepaliesta.

Tai ne kaprizas — tai suliejimo rikiavimo kaina. Jam reikia vietos suliejimui, ir ta vieta yra n papildomų elementų. Greitasis rikiavimas jos nereikalauja, ir 7 žingsnyje pamatysi, kad būtent dėl to jis dažnai greitesnis, nors palyginimų atlieka daugiau.

dcsort.go SUKURTI

Sukurk šį failą kataloge ./

package main

import (
	"math/rand"

	"algo/metrics"
)

// This file is YOURS to fill in. The algorithms are in step 2; dcsort_test.go
// decides whether you got them right.
//
// Shared rules:
//   - every comparison between two Titles goes through cmp.Hit();
//   - every element written into its place goes through moves.Hit();
//   - the counts must be deterministic: same input, same numbers, every run.

// MergeSort returns a NEW slice sorted ascending by Title. It must NOT modify
// the input — the test checks that.
//
// MUST BE STABLE: equal Titles keep their original relative order. Stability
// lives in one character of the merge step; step 2 says which one.
//
// It must stay under n*ceil(log2 n) comparisons on EVERY input — shuffled,
// sorted and reverse alike. Merge sort has no bad case, and the test proves it
// on all three.
func MergeSort(items []Item, cmp, moves *metrics.Counter) []Item {
	panic("not implemented")
}

// QuickSortNaive sorts IN PLACE, always taking the FIRST element as the pivot.
//
// NOT stable. And this one is deliberately broken in a specific way: on
// already-sorted input it must do EXACTLY n(n-1)/2 comparisons — the same
// quadratic count as lesson 7's elementary sorts. The test asserts that number,
// because the failure is the lesson.
func QuickSortNaive(items []Item, cmp, moves *metrics.Counter) {
	panic("not implemented")
}

// QuickSortMedian3 sorts IN PLACE, using the median of the first, middle and
// last elements as the pivot.
//
// NOT stable. On sorted input it must come in far below the quadratic count —
// that is the fix. On REVERSE-sorted input, measure before you assume; step 6
// has the number and it is not what you would expect.
func QuickSortMedian3(items []Item, cmp, moves *metrics.Counter) {
	panic("not implemented")
}

// QuickSortRandom sorts IN PLACE with a randomly chosen pivot.
//
// NOT stable. Seed the generator from a FIXED value (rand.NewSource(1)) so the
// counts stay reproducible — a benchmark you cannot repeat is not a benchmark.
func QuickSortRandom(items []Item, cmp, moves *metrics.Counter) {
	_ = rand.New(rand.NewSource(1))
	panic("not implemented")
}