Sorting Algorithm Time Complexities/Details

Bubble Sort (worst time complexity)

O(n²); We compare every element to every other element, which is approximately n times n work.

Bubble Sort (average time complexity)

O(n²); On average, it performs more closely to its worst case.

Bubble Sort (best time complexity)

O(n); If we have a separate boolean flag to check if the list is already sorted, we can detect this in one pass. Otherwise, this is O(n²).

in-place

The sorting algorithm uses O(1) auxiliary space

adaptive

The sorting algorithm is adaptive if it takes advantage of pre-existing order in the input data (aka if the data is “nearly” sorted, it takes less time to sort than if the data is completely unsorted)

stable

A sorting algorithm is stable if it preservers the relative order of elements that are equal (for example in the list [4, 6, 2L, 3, 1, 2R, 7], the sorted list should be [1, 2L, 2R, 3, 4, 6, 7])

Bubble Sort (characteristics)

bubble sort is adaptive, in-place, and stable IF you include the rule that two items with the same value can’t be swapped.

[5, 4, 2, 3, 1, 6, 10, 7] → what does the list look like after three passes of bubble sort?

[2, 1, 3, 4, 5, 6, 7, 10]

Bubble Sort (description)

arranges a list of elements by repeatedly swapping adjacent items if they are in the wrong order

Cocktail Shaker Sort (description)

sorting algorithm that does bubble sort in both directions (forward and backward); allows for small elements in the list to be “bubbled down” quickly

Cocktail Shaker Sort (best time complexity)

O(n); If we have a separate boolean flag to check if the list is already sorted, we can detect this in one pass. Otherwise, this is O(n²).

Cocktail Shaker Sort (average time complexity)

O(n²); On average, it performs more closely to its worst case.

Cocktail Shaker Sort (worst time complexity)

O(n²); We may have to do up to n swaps for each of n items.

Cocktail Shaker Sort (characteristics)

Same as bubble sort (stable, adaptive, in place)

[5, 4, 2, 3, 1, 6, 10, 7] → what does this list look like after two passes of cocktail shaker sort?

[1, 2, 3, 4, 5, 6, 7, 10] → the list is fully sorted after the forward sweep of pass #2

Insertion Sort

builds the sorted list one element at a time

insertion sort (worst case time complexity)

O(n²); If the initial array is reverse-sorted, we have to move each element to the beginning of the array one spot at a time, which is approximately n times n work.

insertion sort (average case time complexity)

O(n²); On average, it performs more closely to its worst case.

Insertion sort (best case time complexity)

O(n); If the initial array is already sorted, we check each element once and do not have to move any towards the front.

Insertion Sort (characteristics)

stable (if we add the rule to avoid swapping equal items), adaptive, and in-place

[10,9,9,2,4,12] → what does the list look like after

do later

Selection Sort (best case time complexity)

O(n²); Finding the largest or smallest element in the unsorted portion of the array requires n comparisons, and we do this n times.

Selection Sort (worst case time complexity)

O(n²); Finding the largest or smallest element in the unsorted portion of the array requires n comparisons, and we do this n times.

Selection Sort (average case time complexity)

O(n²); Finding the largest or smallest element in the unsorted portion of the array requires n comparisons, and we do this n times.

Selection Sort (description)

repeatedly finds the smallest (or largest) element from the unsorted portion and moving it to the beginning; does less swaps than any other sort

Selection Sort (characteristics)

in place

Selection Sort (Use Cases)

Has the least number of swaps out of all the sorts; if swapping is expensive, use selection.

Allocating memory is expensive, so if each swap requires some allocation, we’d want to do selection.

selection sort example - do this later

do later

Merge Sort (worst case time complexity)

O(n log n); Merge sort always recursively divides the array into halves (for a total of log n levels) and merges each level (which is an O(n) operation).

Merge Sort (average case time complexity)

O(n log n); Merge sort always recursively divides the array into halves (for a total of log n levels) and merges each level (which is an O(n) operation).

Merge Sort (best case time complexity)

O(n log n); Even in the best case, merge sort still recursively divides the array into halves (for a total of log n levels) and merges each level (which is an O(n) operation).

the “worst” sort

bubble; wastes multiple comparisons on the same data

MergeSort (characteristics)

stable

MergeSort (description)

Divide and Conquer Sort; break array into smaller arrays, sort the smaller arrays, then combine the sorted smaller arrays into a larger sorted array

merge sort (use cases)

scenarios where data access is restricted, stability is required, or datasets exceed available memory

Quick Sort (description)

pick a pivot element, move all elements smaller than pivot to the left and larger than the pivot to the right, then recursively picks a pivot from the left and right sub lists and repeats

QuickSort (characteristics)

in place

QuickSort (worst case time complexity)

O(n²); The worst pivot (min or max) is chosen each partition, devolving into a selection sort.

QuickSort (average case time complexity)

O(n log n); On average, the data is split roughly in half each partition.

QuickSort (best case time complexity)

O(n log n); The pivot is perfect (the median) in every partition.

Quicksort use cases

quicksort is used for most general-purpose sorting libraries because of its efficiency

Kth Select (description)

works really similar to quicksort but instead of recursively sorting both sides of the pivot it just recursively sorts the side with the kth element\

basically, compare the pivot’s index (after partitioning) to k. if k is less, then recurse left, otherwise, recurse right.

kth select (worst case time complexity)

O(n²); The minimum or maximum value of the subarray is always chosen.

kth select (average case time complexity)

O(n); Data is split in half on average during each partition. We can discard the partition which does not contain the target.

kth select (best case time complexity)

O(n); The pivot is always the median value of the subarray.

quickselect use cases

when you want to find the kth smallest/largest element in a unsorted list without sorting the whole list

HeapSort Description

heap sort calls build heap on the unsorted list of data and then removes data from the heap one at a time. build heap is O(n) and removing n data from a heap is O(n log n), so the whole things is about O(n log n)

heap sort (characteristics)

not stable because it makes large swaps over multiple elements, which can swap the positions of equal elements

not adaptive because build heap takes O(n) time no matter what, and removing from the heap is always O(log n), so the time complexity isn’t better if the data is already mostly sorted

not in place because it uses a heap

heap sort (best time complexity)

O(n log n); Removing an element from a heap is O(log n), and we do this n times.

heap sort (average time complexity)

O(n log n); Removing an element from a heap is O(log n), and we do this n times.

heap sort (worst time complexity)

O(n log n); Removing an element from a heap is O(log n), and we do this n times.

Radix Sort (description)

a non-comparative sorting algorithm that avoids direct comparisons between elements by grouping them based on individual digits or characters

Sorts all of the data by its least significant digit, then its second least significant digit, etc.

Radix Sort (characteristics)

stable, but not adaptive (nearly sorted data isn’t any faster to sort) or in-place (you need 10 buckets/queues)

Radix Sort (worst case time complexity)

O(kn);One or a few numbers in the array are much longer than the rest. The longest number has k digits.

Radix Sort (best case time complexity)

O(kn); Each number in the array will be added to and removed from a bucket k times, where k is the length of the longest number.

Radix Sort (average case time complexity)

O(kn); All of the numbers in the array have relatively few digits.