Python Data Structures and Algorithms

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.

In the next chapter, we will explore the world of strings. We will learn how to efficiently ...