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.
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.
