Fisher-Yates Shuffle: Pull a random card from the deck repeatedly and set it aside.
|
Time complexity: |
O(n) |
|---|---|
|
Space complexity: |
O(1) |
Bubble Sort: Adjacent items are exchanged until the largest is pushed to the right.
|
Worst time complexity: |
O(n2) |
|---|---|
|
Average time complexity: |
O(n2) |
|
Best time complexity: |
O(n) |
|
Space complexity: |
O(1) |
Selection Sort: Go through the rest of the list and take the next smallest value.
|
Worst time complexity: |
O(n2) |
|---|---|
|
Average time complexity: |
O(n2) |
|
Best time complexity: |
O(n2) |
|
Space complexity: |
O(1) |
Insertion Sort: Take the next value and insert it where it belongs in the already sorted area.
|
Worst time complexity: |
O(n2) |
|---|---|
|
Average time complexity: |
O(n2) |
|
Best time complexity: |
O(n) |
|
Space complexity: |
O(1) |
Merge Sort: Sort smaller sections of the list and merge the sorted sections together.
|
Worst time complexity: |
O(nlogn) |
|---|---|
|
Average time complexity: |
O(nlogn) |
|
Best time complexity: |
O(nlogn) |
|
Space complexity: |
O(n) |
Quick Sort: Choose a value, put all of the larger values to the right and smaller values to its left. Repeat this for smaller subsets of the list.
|
Worst time complexity: |
O(n2) |
|---|---|
|
Average time complexity: |
O(nlogn) |
|
Best time complexity: |
O(nlogn) |
|
Space complexity: |
O(logn) |
Heap Sort: Put the elements into a max heap structure. Repeatedly pop the first element off and add it to the sorted section.
|
Worst time complexity: |
O(nlogn) |
|---|---|
|
Average time complexity: |
O(nlogn) |
|
Best time complexity: |
O(nlogn) |
|
Space complexity: |
O(1) |
Radix Sort: Organize each element by its least significant digit, and work up from there.
|
Worst time complexity: |
O(n*k/d) |
|---|---|
|
Average time complexity: |
O(n*k/d) |
|
Best time complexity: |
O(n*k/d) |
|
Space complexity: |
O(n+2d) |