Radix Sorting - bucket sorting
LSD - Least Significant Digit (start from ones digit, move <--)
MSD - Most Significant Digit (start from left digit, move -->)
Use nested buckets - MSD for 3-digit numbers ex:
Start with hundreds-place-digit % 10 bucket
Within that bucket, place in tens-place-digit % 10 bucket
Within that bucket, place in ones-place-digit % 10 bucket
Can mod by different size/number of buckets
Will take O(n) time to place elements - placing in sorted order
Will take O(n) time to retrieve elements in sorted order
Total sort time is O(n) time
Not a comparative sort, since merely placing elements
Can only work with arrays of integers
Good for when you have a set range of integes since sort is very fast
Bad for an infinite/unknown range, since can't set the appropriate number of buckets
Heaps - Binary tree where each parent is smaller than its children
Min Heap - default, what most people assume when talking about Heaps
Max Heap - binary tree where each parent is larger than its children
Often stored as an array where reading in a Breadth First manner
Can reference parents/children by index
Parent of node i is node (i-1)/2
Children of node i are (i*2)+1 & (i*2)+2
O(n) time to place all elememnts
Percolation - can either percolate up or percolate down
Percolating up - add a new element on the end of the array (become new leaf of tree), then compare it to its parent (using index). If it is smaller than its parent, swap positions. Compare to new parent. Continue this until new element is smaller than its parent (in correct position)
Percolating down - add a new element to the beginning of the array (make it the new root). Of its two children, swap with the smaller of the two (if it's smaller. Check new children, and swap with the smaller of the two if it's still larger. Continue this until it is larger than its children.
Because we're storing a binary tree in an array, it will compact to the top (so no extra-long branches)
Number of levels for n nodes --> log(n)
Hence, will take max O(logn) time to percolate up or percolate down
Because it takes O(logn) time to place 1 element, it will take O(nlogn) time to place all objects into the binary tree. Once placed, elements are in sorted order
Take first element, place at end of array and percolate up. This will take max O(logn) time
O(nlogn) time to sort all elements
Chat with Nicholas Neumann-Chun