Go — main.go

Go — Randomized Quicksort (HW3)

Toolchain

go version → go1.26.0 linux/amd64 (confirmed inside WSL2 Ubuntu)
Standard library only (math/rand/v2, time, fmt, os). No external modules.

Files

go.mod — minimal module definition (module quicksort, go 1.26)
main.go — randomized quicksort implementation + timing harness

Build & run

From inside WSL2 Ubuntu, in this directory:

go build -o quicksort .
./quicksort

Or, invoked from the Windows side (the convention used for this assignment):

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/go' && go build -o quicksort . && ./quicksort"

No special build flags are needed — a plain go build produces an optimized binary by default (Go does not have separate debug/release build modes the way C/C++/Rust do; there is no debug-symbol-heavy default to disable).

Running ./quicksort writes ../results/go.csv (i.e. HW3/results/go.csv) and echoes the same n,time_seconds rows to stdout as it goes.

Notes

gofmt -l . / go vet ./... were run and are clean.
The binary quicksort (and quicksort.exe if ever built on Windows) is a build artifact, not source — feel free to delete/rebuild it.

// Randomized Quicksort timing harness (Go)
//
// # CSC 482 HW3 - Language Comparison
//
// Algorithm: CLRS RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION (Cormen, Leiserson,
// Rivest & Stein, Introduction to Algorithms, Ch. 5). No external code used - this
// is an original implementation based on the CLRS pseudocode. No sorting-library
// shortcuts (sort.Ints / slices.Sort) are used.
//
// Random pivot selection and data generation both use the Go standard library
// math/rand/v2 package (rand.IntN), which is automatically seeded from a
// cryptographically secure random source at process start - no manual seeding
// is required in Go 1.22+.
package main

import (
	"fmt"
	"math/rand/v2"
	"os"
	"time"
)

// randomizedPartition implements CLRS's RANDOMIZED-PARTITION: pick a pivot index
// uniformly at random from [lo, hi], swap it into the last position (a[hi]), then
// run a standard Lomuto partition around that pivot.
func randomizedPartition(a []int, lo, hi int) int {
	pivotIndex := lo + rand.IntN(hi-lo+1)
	a[pivotIndex], a[hi] = a[hi], a[pivotIndex]
	return lomutoPartition(a, lo, hi)
}

// lomutoPartition implements CLRS's PARTITION (Lomuto scheme).
func lomutoPartition(a []int, lo, hi int) int {
	pivot := a[hi]
	i := lo - 1
	for j := lo; j < hi; j++ {
		if a[j] <= pivot {
			i++
			a[i], a[j] = a[j], a[i]
		}
	}
	a[i+1], a[hi] = a[hi], a[i+1]
	return i + 1
}

// randomizedQuicksort implements CLRS's RANDOMIZED-QUICKSORT, sorting a[lo..hi]
// in place.
func randomizedQuicksort(a []int, lo, hi int) {
	if lo < hi {
		p := randomizedPartition(a, lo, hi)
		randomizedQuicksort(a, lo, p-1)
		randomizedQuicksort(a, p+1, hi)
	}
}

// generateRandomSlice returns a freshly-allocated slice of n random ints drawn
// uniformly from [0, 1_000_000). Not timed (called before the timer starts).
func generateRandomSlice(n int) []int {
	a := make([]int, n)
	for i := range a {
		a[i] = rand.IntN(1000000)
	}
	return a
}

func main() {
	const (
		maxIterations  = 25
		maxElapsedSecs = 4.0
		maxN           = 200_000_000
	)

	outPath := "../results/go.csv"
	f, err := os.Create(outPath)
	if err != nil {
		fmt.Fprintf(os.Stderr, "failed to create %s: %v\n", outPath, err)
		os.Exit(1)
	}
	defer f.Close()

	fmt.Fprintln(f, "n,time_seconds")
	fmt.Println("n,time_seconds")

	n := 1000
	for iter := 1; ; iter++ {
		data := generateRandomSlice(n)

		start := time.Now()
		randomizedQuicksort(data, 0, len(data)-1)
		elapsed := time.Since(start).Seconds()

		row := fmt.Sprintf("%d,%.6f", n, elapsed)
		fmt.Fprintln(f, row)
		fmt.Println(row)

		if elapsed > maxElapsedSecs {
			break
		}
		if iter >= maxIterations {
			break
		}
		nextN := n * 2
		if nextN > maxN {
			break
		}
		n = nextN
	}
}

Read Go report