Join Joe Marini for an in-depth discussion in this video Overview of sorting, part of Programming Foundations: Algorithms.
- [Instructor] One of the most common problems that arise in writing modern programs is the need to sort sets of data. And there are a variety of reasons why you'd want to do this. In some cases, the data will be presented to the user, and to help them make sense of the information it needs to be sorted a certain way. So for example, someone using a real estate app might want to sort properties by price level. In other cases, the data needs to be sorted so that the app itself can work on the information more efficiently. So using that same real estate app scenario, the user might not decide to view houses sorted by price, but if they do specify a maximum price level, then the app would internally sort the data in order to limit the amount of additional information it would need to retrieve for a given set of properties.
So for example, if a house doesn't meet your price needs, then there's no sense in going and getting information about it, how many bedrooms it has, where it's located, and so on. In this chapter, we're going to learn about a few of the different algorithms for sorting information, how they work, and what their relative Big O performance characteristics are. Now most modern programming languages have sorting routines already built in, and they're pretty efficient, so it's unlikely that you'll have to write your own sorting algorithm, but it's very helpful to understand how the various algorithms work so you can choose the right one.
The sorting algorithms that we're going to look at are the bubble sort, which is a very basic algorithm, that's mainly used as teaching tool these days, because it's really not very good. There's also the merge sort, which uses recursion to implement its main logic, and the quick sort, which also uses recursion and is usually even better than the merge sort. Each of these sorting algorithms illustrates a different way of tackling the problem of sorting information. Now these are not the only sorting algorithms out there, but they are a good representation of some of the different approaches to solving the general problem of sorting data.
So, let's get started.
- Measuring algorithm performance
- Working with data structures such as arrays, stacks, and queues
- Looping and recursion
- Sorting data
- Searching data
- Filtering and value counting with hash tables