Algorithms

Question 1

Describe Quick Sort

Answer 1

Quick sort picks a random element as a “pivot” and then swaps values in the array…

…such that the elements less than the pivot appear before elements greater than the pivot.

This creates a “partial sort”, then it recursively sorts the left and right sides.

Expected: O(log n)
Worst: O(n^2)

Big O: n^2

Question 2

What is Binary Search?

Answer 2

A binary search starts with a sorted array.

We’ll be looking for element x and start at the middle of the data structure.

If the search point is x, we’ve found it.

If the point is greater than x the algorithm steps left to the next halfway. Otherwise the algorithm steps to the right halfway.

This repeats until the element is found.