Why should I sort?

What do phone contacts, leaderboards, and the FIFA World Rankings have in common? For one, they all might contain large amounts of data. More importantly, however, they are presented in an orderly manner. Contacts in your phone are stored alphabetically, players on a leaderboard are listed based on a score of some sort, and the best soccer teams in the world are ranked based on how well they play. Imagine if the order of the contacts in your phone was random. It would, in the worst case, take you as many attempts as the amount of stored contacts to find a specific person (i.e. it would take all your time)! Furthermore, the concepts of “leaderboard” and “ranking” would surely not be fathomable without some way to algorithmically sort data. Thus, computer scientists have developed powerful sorting algorithms that are now used in many applications.

Not all sorting algorithms are created equal. The introductory methods presented in this chapter are considered to be naïve and are mainly used for the purposes of teaching. Yet, one cannot go further into more sophisticated techniques without some exposure to the basics. Namely, this chapter will introduce three well-known sorting algorithms: bubble sort, selection sort, and insertion sort. The sections later on will introduce the concept recursive sorting, and thus the gates to merge sort and quick sort will open. As different methods are introduced, the run-times will be briefly discussed so as to show the advantages of more advanced approaches.

Below is a comparison chart of the most common sorting algorithms:

---

<-- Previous | Next -->