Elementary Sorting — Programuoki

Code

sort.go — the skeleton you fill in

Create sort.go (see the panel).

The file in the panel is complete and correct — you will create exactly that. It has the package, the import, three signatures, the contracts, and a panic("not implemented") in each.

Your job is to replace those three panics with real code, working from the previous step's pseudocode.

Read the contracts, not just the signatures

The doc comments state everything the test will check:

BubbleSort — stable; exactly n−1 comparisons on sorted input;
SelectionSort — not stable; exactly n(n−1)/2 comparisons on any input; at most n−1 swaps;
InsertionSort — stable; exactly n−1 comparisons and zero swaps on sorted input.

Three of those are exact numbers, not bounds. If your implementation gives n where n−1 is required, the test will catch it — and that is a real defect, not pedantry: it means you are comparing something twice, or comparing an element with itself.

sort.go CREATE

Create this file in ./

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