Exercises

The following exercises provide you with the opportunity to practice with fast sorting. The solutions to these exercises are found in the section .

Given an array of positive numbers, write a function that returns the greatest product of any three numbers. The approach of using three nested loops would clock in at O(N³), which is very slow. Use sorting to implement the function in a way that it computes at O(N log N) speed. (Some other implementations are even faster, but we’re focusing on using sorting as a technique to make code faster.)

The following function finds the missing number from an array of integers; that is, the array is expected to have all integers from 0 up to the array’s length, but one is missing. As examples, the array [5, 2, 4, 1, 0] is missing the number 3, and the array [9, 3, 2, 5, 6, 7, 1, 0, 4] is missing the number 8.

Here’s an implementation that is O(N²) (the clause if number not in array is itself already O(N), since the computer needs to search the entire array to find number):

	def find_missing_number(array):
	for number in range(len(array) + 1):
	if number not in array:
	return number

	return None

Use sorting to write a new implementation of this function that only takes O(N log N). (Some other implementations are even faster, but we’re focusing on using sorting as a technique to make code faster.)

Write three different implementations of a function that finds the greatest number within an array. Write one function that is O(N²), one that is O(N log N), and one that is O(N).