Efficient Sorting — Programuoki

Code

dcsort.go — the skeleton

Create dcsort.go (see the panel). Four signatures, four contracts, four panics.

Three of the four are the same quicksort with a different pivot, so you write Partition once and use it three times.

What the test checks

MergeSort — stable, does not return the same slice (the input must be untouched), and stays under n·⌈log₂ n⌉ comparisons on every order;
QuickSortNaive — exactly n(n−1)/2 comparisons on sorted input. The test demands that precise number, because the failure is the lesson;
QuickSortMedian3 — far below quadratic on sorted input;
QuickSortRandom — fixed seed (rand.NewSource(1)), so the counts repeat.

One thing that is easy to miss

MergeSort returns a new slice rather than sorting in place, and the test checks that the input is left alone.

That is not fussiness — it is merge sort's price. It needs somewhere to merge into, and that somewhere is n extra elements. Quicksort needs none, and in step 7 you will see that this is why it is often faster despite making more comparisons.

dcsort.go CREATE

Create this file in ./

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")
}