Bubble, Merge, Quick, Radix
##Quick Sort
####Complexity
- Best time: O(n log n)
- Average time: varies depending on pivots
- Worst time: O(n^2)
####Approach
- if the list has fewer than two elements, return the list because it is sorted
- picking random number from the list, called a pivot
- iterate through the list of numbers add to listadding each number to a sublist less, equal, or greater based on comparing to the pivot
- recurse on the less and greater lists to sort them
- combine less, equal, and greater lists in order
####Example:
[15 35 21 12] -> pivot 21 -> less:[15 12] equal: [21] greater: [35]
recurse on less -> pivot 12 -> less:[] equal:[12] greater:[15] -> [12 15]
recurse on greater -> [35]
less:[12 15] equal: [21] greater: [35] -> [12 15 21 35]
##Radix Sort:
####Complexity
- Best time: O(d n)
- Average time: O(d n)
- Worst time: O(d n)
where d is the number of digits in the longest number (eg for 123, d = 3). When n >> d, this algorithm is very efficient.
####Approach
- look at the one's place,
- add numbers to buckets that represent each digit (eg 8976 place 0 is 6, so it goes in bucket 6)
- combine the buckets in order back into a list
- repeat 1-3, looking at the next place until no numbers have that place
####Example
[12 35 21 15] -> 1:[21] 2:[12] 5:[35 15]
1:[21] 2:[12] 5:[35 15] -> [21 12 35 15]
[21 12 35 15] -> 1:[12 15] 2:[21] 3:[35]
1:[12 15] 2:[21] 3:[35] -> [12 15 21 35]