README
¶
go-algorithms
This project contains implementations of common computer science related algorithms written in Go. My aim is not to provide reference implementations, but simply to practice while working my way through the third edition of Introduction to Algorithms from MIT Press.
Documentation is available on godoc.org.
To test all algorithms for correctness with pseudo-random input, run
$ make test
To test all algorithms for correctness repeatedly with fuzzed input, run:
$ make fuzz
To benchmark all algorithms for best, worst and pseudo-random (hopefully average) case, run:
$ make bench
Documentation
¶
Overview ¶
This project contains implementations of common computer science related algorithms written in Go. My aim is not to provide reference implementations, but simply to practice while working my way through the third edition of Introduction to Algorithms* from MIT Press.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BubbleSort ¶
func BubbleSort(a []int)
BubbleSort sorts the given array of integers in ascending order using an implementation of the Bubble Sort algorithm.
It the runs in subquadtratic time O(n2) in the average and worst case.
The implementation is optimized to exit early if no swaps are performed in a given pass resulting in O(n) in the best case of a pre-sorted input.
func InsertionSort ¶
func InsertionSort(a []int)
InsertionSort sorts the given array of integers in ascending order using an implementation of the Insertion Sort algorithm.
In the best case of a presorted array, Insertion sort runs in linear time O(n) while in the worst case of a reverse sorted array, it runs in quadratic time O(n2). The average case also runs in quadratic time making it inefficient for sorting large arrays.
func MergeSort ¶
func MergeSort(a []int)
MergeSort sorts the given array of integers in ascending order using an implementation of the top-down Merge Sort algorithm.
Merge sort runs in O(n log n) in the worst and average case.
func SelectionSort ¶
func SelectionSort(a []int)
SelectionSort sorts the given array of integers in ascending order using an implementation of the Selection Sort algorithm.
Selection sort run consistently in O(n2) time for the best, worst and average case.
Types ¶
This section is empty.
Source Files