Documentation
¶
Index ¶
- func BubbleSort(a []int) []int
- func BuildMaxHeap(a []int)
- func CountingSort(a, b []int, k int)
- func HeapSort(a []int) []int
- func HoarePartition(a []int, lo, hi int) int
- func HoareQuickSort(a []int) []int
- func InsertionSort(a []int) []int
- func MakeRandArray() []int
- func MakeReversedArray() []int
- func MakeSortedArray() []int
- func MaxHeapify(a []int, i, heapSize int)
- func MergeSort(array []int) []int
- func Partition(a []int, lo, hi int) int
- func QuickSort(a []int) []int
- func RandomizedPartition(a []int, lo, hi int) int
- func RandomizedQuickSort(a []int) []int
- func SelectionSort(a []int) []int
- func Sort(a []int, lo, hi int, partition PartitionFn) []int
- func TestSort(t *testing.T, sortFn SortFunction)
- type PartitionFn
- type SortFunction
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BubbleSort ¶
Bubble sort. Simple algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. Time complexity: W: O(n^2) B: O(n) A: O(n^2)
func BuildMaxHeap ¶
func BuildMaxHeap(a []int)
Goes through the remaining nodes of the tree and runs MaxHeapify on each one.
func CountingSort ¶
Counting sort operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum and minimum key values, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. However, it is often used as a subroutine in radix sort, that can handle larger keys more efficiently. Time Complexity: W: O(n), B: O(n), A: O(n)
func HeapSort ¶
Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the second region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum. Time complexity: W: O(n lgn) B: O(n lgn) A: (n lgn)
func HoarePartition ¶
func HoareQuickSort ¶
The original partition scheme described by Hoare uses two indices that start at the ends of the array being partioned, then move toward each other, until they detect an inversion and swap inverted elements. When indices meet,the algorithm stops and returns the final index.
func InsertionSort ¶
func MakeRandArray ¶
func MakeRandArray() []int
func MakeReversedArray ¶
func MakeReversedArray() []int
func MakeSortedArray ¶
func MakeSortedArray() []int
func MaxHeapify ¶
This function lets the value at a[i] float down in the max-heap so that the subtree at index i obeys the max-heap property.
func MergeSort ¶
Merge sort. Divide and conquer algorithm. Have 2 steps:
- Divide unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
- Repetedly merge sublists to produce new sorted sublists until there is only 1 sorted sublist remaining.
Time complexity: W: O(n log n) B: O(n log n) A: O(n log n)
func RandomizedPartition ¶
func RandomizedQuickSort ¶
Randomized version of Quicksort. Choose pivot element randomly to obtain good expected performance over all inputs.
func SelectionSort ¶
Selection sort. The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted list is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest element in the unsorted list, exchanging it with the leftmost unsorted element, and moving the sublist boundaries one element to the right. Time complexity: W: O(n^2) B: O(n^2): A: O(n^2)
func TestSort ¶
func TestSort(t *testing.T, sortFn SortFunction)
Source Files