In this chapter, we discussed various 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 element was 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 quicksort 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 embarked on finding the median of medians to enable us to find a good split during partitioning.
In the next chapter, we will explore the world of strings. We will learn how to efficiently store and manipulate large amounts of text. Data structures and common string operations will be covered too.
...