Sorting Algorithms

Question 1

What is the order of runtime from fastest to slowest?

Answer 1

1, log(n), n, nlog(n), n^2, 2^n, n!

Question 2

What is the runtime (worst case and best case) of bubble sort?

Answer 2

Worst case: n^2, array is reversed
Best case: n, if data is sorted and the algorithm is optimized. Meaning there is a way to exit early.

Question 3

What is the runtime (worst case and best case) of insertion sort?

Answer 3

Worst case: n^2, if array is reversed
Best case: n, if array is sorted

Question 4

What is the runtime (worst case and best case) of selection sort?

Answer 4

n^2 for best and worst case. No mechanism to know when it’s done working so it looks through the whole list again and again

Question 5

What are the non-comparison sorting algorithms? What is their runtime?

Answer 5

Counting sort
Radix sort
Both run in linear, n, time.

Question 6

What are the divide and conquer algorithms?

Answer 6

Merge sort
Quick sort

Question 7

What is the runtime (worst case and best case) of merge sort?

Answer 7

It is always nlog(n). The best case and worst case are nlog(n). No mechanism to figure out if it’s done working, so it will just keep splitting and working on the list. Needs extra space.

Question 8

What is the runtime (worst case and best case) of quick sort?

Answer 8

Worst case: n^2
Best case: nlog(n)
The runtime is based on the position of the pivot used. Pivot should be somewhere in/near the middle to get the best case runtime.

Question 9

What does merge sort need that quick sort does not need?

Answer 9

Merge sort needs needs extra space. So an extra array needs to be created.