.png){kind=small}
Bubble Sort
Concept
Repeatedly, iterate through the array, swapping adjacent elements if they are in the wrong order
Runtime
O(n2)
Video Explanation
Insertion Sort
Concept
Iteratively insert an element of the unsorted list into its correct position in the already-sorted part of the list
Runtime
O(n2)
Video Explanation
Selection Sort
Concept
Repeatedly select the smallest element from the unsorted portion of the list and swap it with the first element of the unsorted part
Runtime
O(n2)
Video Explanation
Merge Sort
Concept
A divide-and-conquer algorithm that sorts the left half of the list, then the right half, and then combines the two
Runtime
O(nlgn)
Video Explanation
Example Problems
Quicksort
Concept
A divide-and-conquer algorithm that chooses a pivot point, moves all smaller elements to the left of the pivot and all larger elements to the right, and then repeats the process on each subsection of the array
Runtime
O(nlgn), often the fastest sorting algorithm in practice
Video Explanation
Heap Sort
Concept
A faster form of Selection Sort that requires adding all elements to a heap, and then removing the minimum element n times
Runtime
O(nlgn), often the fastest sorting algorithm in practice
Video Explanation
Counting Sort
Concept
Counts the frequency of each distinct element in the array, and uses these counts to generate a sorted array (Note: only works with small ranges of values)
Runtime
O(n), great for sorting data like temperatures, percentages, etc.
