Summary
This chapter has examined ways to answer the question of how to find the ith-smallest element in a list. The trivial solution of simply sorting a list to perform the operation of finding the ith-smallest has been explored.
There is also the possibility of not necessarily sorting the list before we can determine the ith-smallest element. The random selection algorithm allows us to modify the quick sort algorithm to determine the ith-smallest element.
To further improve upon the random selection algorithm so that we can obtain a time complexity of O(n), we embark on finding the median of medians to enable us find a good split during partitioning.
From the next chapter, we will change our focus and take a deep dive into Python's OOP concepts.
