Part 5

Question 1

What is the principle of divide and conquer?

Answer 1

A large problem should be broken down into several smaller problems

Question 2

how does divide and conquer work when sorting a collection?

Answer 2

split into two collections, sort them, then somehow merge the two collections

Question 3

What are the best, average and worst time complexities of insertion sort?

Answer 3

Best: O(n)

Average: O(n²)

Worst: O(n²)

Question 4

What are the best, average, and worst time complexities of mergesort?

Answer 4

O(nlogn) for all

Question 5

What are the best, average and worst time complexites of selection sort?

Answer 5

O(n²) for all

Question 6

What is the difference between easy-split hard-merge and hard-split easy-merge?

Answer 6

ESHM: splitting into two lists is easy, work done in merging sorted sublists

HSEM: splitting is difficult - have to split into large half and small half sublists, but then once they’re sorted can just merge by appending the large list to the small one

Question 7

Is insertion sort easy-split hard-merge, or hard-split easy-merge?

Answer 7

Easy split hard merge

Question 8

How does insertion sort work?

Answer 8

Split list into two lists of size 1 and n-1

Sort the n-1 list

Insert the 1 into the correct position in the n-1 list

Question 9

Is mergesort easy split hard merge or hard split easy merge?

Answer 9

easy split hard merge

Question 10

How does mergesort work?

Answer 10

Split list into two equal sized lists

sort them by mergesort

iterate over both lists at the same time

add smaller of the two current items from the two lists to the result array

if one array is empty, append the other to the end of the results list

Question 11

Is selection sort easy split hard merge or hard split easy merge?

Answer 11

hard split easy merge

Question 12

how does selection sort work?

Answer 12

Swap the pos+1th number of the list with the smallest number from the rest of the list, until the end of the list has been reached

recursive

Question 13

is quicksort easy split hard merge or hard split easy merge?

Answer 13

hard split easy merge

Question 14

How does quicksort work?

Answer 14

Approximate the median of the list - the pivot. pivot must not be largest number in list so dont count duplicates

split list into two lists where l1 are all <= the pivot and l2 are all > pivot

to find the split point:

using two cursors starting from left and right

left cursor is incremented until an item > the pivot is found

right is decremented until item <= pivot is found

swap item

once cursors have crossed over found the split point

all items left of the cursor are less than the pivot and all on the right are greater

then sort the subarrays using quicksort

Question 15

What is the best, average and worst time complexity of Quicksort?

Answer 15

Best: O(nlogn)

Average: O(nlogn)

Worst: O(n²)