Algorithms in Go

This repository contains implementations of various algorithms in Go, organized by category with comprehensive benchmark tests.

🔍 Searching Algorithms

The searching/ directory contains implementations of various search algorithms, each in its own package with benchmark tests. Each algorithm is optimized for specific use cases and data distributions, with detailed complexity analysis and performance benchmarks. The implementations prioritize clarity and efficiency, making them suitable for both educational purposes and production use.

🔄 Sorting Algorithms

The sorting/ directory contains implementations of 11 major sorting algorithms, each optimized for different use cases and data patterns. The collection includes everything from basic comparison-based sorts to advanced hybrid algorithms and linear-time sorting methods.

Available Algorithms

Basic Sorting Algorithms

• Bubble Sort - O(n²) simple comparison-based sort, stable
• Selection Sort - O(n²) in-place selection-based sort, unstable
• Insertion Sort - O(n²) efficient for small datasets, stable

Efficient General-Purpose Sorts

• Merge Sort - O(n log n) divide-and-conquer, stable, guaranteed performance
• Quick Sort - O(n log n) average case, in-place, widely used
• Heap Sort - O(n log n) heap-based, in-place, unstable

Advanced Algorithms

• Shell Sort - O(n^1.3) gap-based improvement over insertion sort
• Tim Sort - O(n log n) hybrid stable sort, excellent for real-world data

Specialized Linear-Time Sorts

• Counting Sort - O(n + k) for integer ranges, stable
• Radix Sort - O(d(n + k)) digit-based sorting, stable
• Bucket Sort - O(n + k) distribution-based, stable

Each algorithm includes comprehensive benchmarks across different data sizes and patterns (sorted, reverse-sorted, random, and partially sorted data) to demonstrate real-world performance characteristics.

Package Structure

Each package contains:

• *.go - Algorithm implementation
• *_test.go - Comprehensive benchmark tests

Running Benchmarks

# Navigate to searching directory
cd searching

# Run all search algorithm benchmarks
go test -bench=. ./...

# Run benchmarks with memory allocation stats
go test -bench=. -benchmem ./...

# Run specific algorithm benchmarks
go test -bench=. ./binary
go test -bench=. ./interpolation

# Run benchmarks multiple times for accuracy
go test -bench=. -count=5 ./...

Benchmark Results Example

BenchmarkBinarySearchLarge-8             488984020    2.075 ns/op
BenchmarkInterpolationSearchLarge-8      566060540    2.122 ns/op
BenchmarkExponentialSearchLarge-8        47690094     24.53 ns/op
BenchmarkFibonacciSearchLarge-8          42400579     27.93 ns/op
BenchmarkJumpSearchLarge-8               8009985      161.8 ns/op
BenchmarkLinearSearchLarge-8             79647        15573 ns/op