Sorting

Question 1

Bubble sort

Answer 1

iterates through array and swaps adjacent numbers if they’re not in order

keeps iterating until we have an iteration with no swaps
O(n^2)

Question 2

Insertion sort

Answer 2

build sorted array, shifting elements into the right place as we iterate through once
O(n^2)

Question 3

Selection sort

Answer 3

split into sorted and unsorted parts

find smallest element in array and add to end of the already sorted part
O(n^2)

Question 4

Merge sort

Answer 4

recursively sort left and right parts of array, merge them together
O(n log n) – space: O(n)

Question 5

Heap Sort

Answer 5

convert unsorted array into max heap
(parent - A[i/2], left - A[2i], right - A[2i + 1])

swap first element with last element and remove from heap

heapify swapped element and repeat

O(n log n)

Question 6

Quick Sort

Answer 6

choose pivot and swap to end of list

elements smaller than pivot move to the left, elements larger than pivot stay to the right

swap pivot point with counter

repeat of left and right parts

worst O(n^2) – average O(n log n)