Sorting and Searching

Question 1

Bubble sort

Answer 1

Start at the beginning of the array and swap the first two elements if the first is greater than the second. Then, we got to the next pair, and so on, continuously making sweeps of the array until it’s sorted. O(n**2) runtime average and worst case. O(1) memeory.

Question 2

Selection Sort

Answer 2

Find the smallest element using a linear scan and move it to the front (swapping it with the front element). Then, find the second smallest and move it again doing a linear scan. Continue doing this until all the elements are in place. O(n**2) average and worst case. O(1) memory.

Question 3

Merge Sort

Answer 3

Divide the array in half, sort each of those havles, and then merge them back together. Each of those halves has the same sorting algorithm applied to it. Eventually, you are merging just two single element arrays. It is the merge part that does all the heavy lifting. O(n log(n)) runtime average and worst case. depends for memory.

Question 4

Merge Sort Implementation

Answer 4

Contains a merge method that copies all the elements from the target array segment into a helper array, keeping track of where the start of the left and right halves should be. We then iterate through helper, copying the smaller element from each half into the array. At the end, we copy any remaining elements into the target array. This requires O(n) space complexity to account for the helper function.

Question 5

Quick Sort

Answer 5

A random element is picked and partitions the array, such that all numbers that are less than the partitioning elements come before all elements that are greater than it. Done efficiently through swaps. Repeatedly partitioning an array, and sub-arrays around an element will sort the array. However, as the partitioned element is not guaranteed to be the median, sorting could be slow. O(n log(n)) average and O(n**2) worst case runtime. O(log(n)) memory.