Chapter 11
Sorting with Sorting Algorithms
IN THIS CHAPTER
Understanding sorting algorithms and the use cases for each
Solving an example of sorting a deck of playing cards
Finding more sorting examples and researching resources
Programmers don’t use sorting algorithms that often in their daily work, but one or more interviewers will likely ask you questions about sorting because they want to know two things: your range of skill as a programmer and your depth of understanding in computer science. This chapter helps prepare you to answer those questions.
We start by giving you the full tour of standard sorting algorithms, including bubble sort, merge sort, quick sort, and heap sort. Then you learn when you need to use each sorting type to solve programming problems.
Next, we show you a common example of sorting one deck and multiple decks of playing cards. Finally, if you want to dive deeper into sorting, we tell you where you can find a variety of online resources so you can not only get more detailed information, but also view more examples.
If you’re applying for a senior software development position, then questions about sorting are practically guaranteed. Even if you’re not asked a sorting question during the interview, you should think about mentioning sorting when you’re solving another problem or when you’re asked another question about programming so you at least let your interviewers know you studied sorting … and that you’re ready to hit any follow-up sorting question out of the park.
Absorbing Common Sorting Algorithms
Fortunately, it’s not important to know every sorting algorithm, and interviewers won’t expect you to know them. What interviewers will expect you to know when you talk about sorting includes:
- The most common sorting algorithms, and
- The trade-offs between different sorting algorithms.
They will also expect you to be able to write down a simple sorting algorithm on the whiteboard in the interview room. So, as your docents in this chapter, we start your tour of sorting with a basic sorting algorithm: the bubble sort.
For the sorting examples in this chapter, we’ll use numbers because using them makes the concepts of sorting easier to understand. However, anything can be sorted with a sort algorithm. In most programming languages, all objects have some kind of value. Essentially any element can be compared to another element of the same type so the sorting algorithm will determine which is greater. For example, letters can be sorted alphabetically as they equate to an ASCII value, which is numeric.
Starting the tour with bubble sort
The bubble sort is perhaps the simplest … er, sort of sorting algorithm that you probably learned about it in your introductory computer science class in high school, community college, or university. A bubble sort is usually presented as a theoretical sorting algorithm. It isn’t something you should use in code because it’s very inefficient, as we soon explain.
The bubble sort algorithm traverses a list of numbers to sort and looks at the first and second numbers in the list. If the first number in the list is larger than the second number, the algorithm swaps the two numbers so the larger number is after the smaller one. If the second number is larger, or the first and second numbers are the same, the algorithm won’t swap the two numbers.
Then the algorithm compares the second and third numbers in the list and swaps them if the second number is larger than the third. The sorting algorithm continues comparing subsequent pairs of numbers until it reaches the end of the list.
When you discuss a bubble sort algorithm in your interview, you should explain these three points:
- The bubble sort algorithm is easy to implement.
- The algorithm is stable because it only swaps numbers if one condition exists.
- It doesn’t take up a lot of memory.
You should also note that because the algorithm traverses the entire list, a longer list means the algorithm will take longer to complete.
There may be a need where a bubble sort algorithm may solve a problem, such as sorting a few post office ZIP codes, but if you have a longer list of ZIP codes to sort, there are faster and more efficient ways to sort ZIP codes (or any other numbers).
Expanding your knowledge about merge sort and quick sort
Merge sort and quick sort are the two go-to algorithms because they’re more efficient than bubble sort. Both sorting algorithms are effective, easy to implement, recursive, and can be used to solve a wide variety of programming problems.
However, a quick sort algorithm can become too inefficient to use. In that case, you can supplement the quick sort algorithm with a merge sort or dump the quick sort code and replace it with a heap sort. Later in this chapter, we show you the different use cases for each type of sorting algorithm.
Divide and conquer with merge sort
Merge sort is a recursive algorithm that takes a list of numbers and splits the list in half. Then the algorithm continues to split each list in half until you’re left with two numbers in several (or many) small lists.
Next, the algorithm sorts each small list so that the smaller number appears first in the list. The algorithm then merges one list with another list and sorts the numbers in the merged list correctly, and continues this pattern until the entire list output shows numbers sorted from smallest to largest.
The main advantage of the merge sort algorithm is that it’s a much faster sorting method than bubble sort. In Big O notation, which you read about in Chapter 9, the average and worst-case compilation time for merge sort algorithms is O(n log n) where n is the number of elements you’re sorting. In comparison, the running time for a bubble sort algorithm is O(n2).
A merge sort algorithm is also stable because it sorts all the numbers correctly. Also, the sort won’t break if there are two identical numbers in the list; the algorithm will simply place the identical numbers next to each other in the sorted list.
The catch is that a merge sort algorithm uses more memory, and thus takes more time to process. That’s something to consider if you have a large number of elements to sort.
Quick sort, the fastest of them all
The quick sort algorithm is also a divide-and-conquer recursive algorithm like merge sort, but like its name says, the quick sort wins the speed race against all other sorting algorithms.
The quick sort algorithm works by requiring you to pick one of the elements in a list as the pivot element, the element the algorithm will pick first. For example, if you have a list with ten numbers sorted randomly, the pivot element can be any one of the numbers in your list: the first element, last element, or any random element — it doesn’t matter.
For example, suppose you have a list of 11 numbers, and you want to sort them with quick sort. Because you’re an even-tempered kind of person, you pick the median element, which is the sixth out of the 11 numbers in the list, as your pivot element.
The algorithm splits the list in two: One list has all the numbers lower than the pivot number before the pivot, and the other list has all numbers greater than the pivot number. In sum, the pivot element is the only element in your list that is ensured to appear in the right place after the quick sort algorithm does its work.
Next, you’ll write the algorithm to select a pivot number in each of the two lists. Those two lists will be ordered in the same way as in the first list. That is, the quick sort algorithm continues to split up each new list by moving all numbers before the pivot number before it and all numbers after the pivot number after it.
Eventually the lists are split to the point where there is only one number left in each list. Then the algorithm reconstructs the list by putting each number or set of numbers into the correct location in its parent list to the left or right of the parent list’s pivot number.
For example, if the number in your final list is 5, and your parent list has a pivot number of 10, the quick sort algorithm will put the number 5 to the left of number 10 in the parent list so you have a bigger list. Now the algorithm puts this bigger list into its parent that has a pivot number of 20, so that parent will have three numbers in the correct order: 5, 10, 20.
The quick sort algorithm repeats this procedure until all the lists are put back together and then outputs the result — you see all 11 numbers in order with your original pivot number in the center.
Quick sort has several drawbacks. Unlike merge sort, quick sort isn’t as stable because the quick sort algorithm accesses memory space randomly. The result is that the algorithm may become confused and move elements that it put in the right place earlier in the sorting process into the wrong place later in the process.
The other issue is that if you have a large list of elements to sort, you not only run the risk of having a more unstable algorithm and thus an incorrect sort, but also the compilation time can increase from the average O(n log n) time to the worst-scenario of O(n2).
The more complex and powerful heap sort
When a list is too big for a quick sort algorithm to manage, programmers often turn to the heap sort, which is another common sorting algorithm. The heap sort finds the maximum element in the list and places it at the end.
For example, if your list consists of many numbers, the heap sort algorithm will find the largest number and put it at the end of the list. Then the heap sort will look at the remaining numbers and put the largest remaining number to the left of the largest number. The heap sort repeats this process until the algorithm sorts all the numbers correctly. Best of all, you’ll get compilation time that matches the average of quick sort — O(n log n) — and heap sort doesn’t use much disk space and memory on your computer.
Understanding use cases for each sorting type
We’ve talked about some of the use cases for implementing different types of sorting, but in real life, you’ll likely use one or more sorting techniques to make your program run as efficiently as possible.
As we said earlier in the chapter, the bubble sort algorithm is primarily used as a teaching tool and may only be used with very limited lists. In your job, you’re going to use the more common merge sort, quick sort, and heap sort algorithms by themselves or combined with another sorting algorithm.
A linked list
A linked list, which we discuss in Chapter 9, doesn’t place its elements in a contiguous block of memory; a linked list stores its elements in random memory locations and uses pointers to connect each element in the list.
If you need to sort a linked list, merge sort is the best approach because the merge sort algorithm takes the entire list and splits it until the entire list is in the proper order. A quick sort algorithm has a difficult time finding elements in random memory locations so the compilation time will be quite slow.
You also can’t use a heap sort to sort a linked list because a heap sort uses a tree-like structure, which is the antithesis of a linked list structure.
Memory restrictions
You may encounter memory restrictions when you try to sort your list. In this case, a merge sort works much better than a quick sort.
For example, elements in your list may be large files that won’t fit into memory, but the merge sort algorithm can split up those files and sort them together so each individual file doesn’t suck up all your memory. Each file is linked together so after the algorithm outputs the information in the first file, the computer will dump that file from memory and fill it with the second file so it can run.
Partial sorts
If you have a list that’s partially or mostly sorted, then merge sort is fastest as the algorithm splits each list in two. So, because there isn’t much to sort, the algorithm compiles much more quickly. If you use a quick sort algorithm, it will re-sort the list from scratch through the use of pivot elements, and it will take longer for the algorithm to return a result.
Solving Two Sorting Examples
So, now that you know about the common types of sorting algorithms you can use and when to use them, let’s put your sorting prowess to the test. We’ll use a test that combines two sorting algorithms together — quick sort and merge sort — into one program that sorts a deck of playing cards.
We suggest you grab a physical deck of playing cards so that you can visualize what we’re doing in this upcoming section. Bookmark this page, put this book down, and go fish a deck out of your junk drawer or drive to your nearest store to buy one (or just order a deck on Amazon), and come back to this section after you have the deck next to you. Popular brands include Bicycle and Bee. Using a physical deck to illustrate what we’re saying will help you remember sorting better than the Solitaire game on Windows or card games on the web.
Sorting one deck of cards
Before you start to sort your deck of cards, you’ll need to assign a numerical value to each card so your sorting algorithm can keep track of all the cards. A standard deck contains 52 cards (excluding any jokers that come with the deck), so it’s easy to number a newly opened deck. For example, you can use 1 to 13 for ace to king in the spades suit, 14 to 26 for the hearts suit, 27 to 39 for the clubs suit, and 40 to 52 for the diamonds suit.
Then you can add code to shuffle the cards. When the cards are listed in random order, you can use two sorting algorithms that will give you the results you want with the fastest compilation time. If you’ve been following along with us, you know what that means: using a quick sort and keeping a merge sort at the ready if quick sort fails.
If you don’t know how to add code to shuffle cards, you can easily find this on Google by searching for “programming shuffle deck of cards” and you’ll see a number of sites on the results page that show you how to do this in a variety of programming languages.
You’ll start with a quick sort, so you’ll need to pick a number in your list that represents a card you want to use as the pivot number. If you need to use a physical deck of cards, shuffle them and then pick one at random and tie it to the number in the list. For example, if you select the jack of spades, use the number 11 as your pivot number.
All cards numbered before the number 11 are in one list and all cards numbered after 11 are in the second list. Then you’ll need to pick a new pivot number in each of the two lists. As the quick sort algorithm continues to divide the list into smaller lists depending on the pivot number in each list, you’ll eventually sort the entire list.
What happens if your quick sort algorithm doesn’t sort all your cards so that you see all the cards in their proper order? That’s when you add a merge sort after the quick sort so you can split the quick sort algorithm’s sorted list. The merge sort algorithm will complete a proper sort and output the list without taking up too much more of your time.
Sorting many decks of cards
Earlier in this chapter, we talked about a use case where you can use a merge sort algorithm to break up a large file because that one large file can’t fit into your computer’s memory. Another way to think of this use case is that you need to sort all the cards in ten decks, which is not such a far-fetched scenario if you find yourself working for a casino.
If you had ten decks of physical cards — and we’re not suggesting you buy ten physical decks unless you get a really great deal — you can only pick up one deck of cards at a time because you only have two hands. And your computer can only work with so many cards because it has only so much memory.
So, you need to use your programming skills to make the computer do the sorting work, and the way you do that is by using a merge sort algorithm. This is a process that requires a numbered list to digest, so here we go:
- Create an array for the cards in all the decks.
- Assign numbers to all the cards in all the decks sequentially from the ace of spades in the first deck assigned numbers 1 to 52, the second deck assigned numbers 53 to 104, and so on until you reach the king of diamonds in the tenth and final deck that has the number 520.
- Scramble the numbers in each deck.
- Use the merge sort algorithm to break down the card numbers in the deck into smaller lists so your computer’s memory can handle those lists.
- Wait for the algorithm to finish reconstructing and sorting the master list of all the cards in all ten decks.
When you view the output, every card in each suit within each deck will appear in their proper order from ace to king. Slicker than a box of rocks.
Getting More Examples and Researching Resources
We’ve told you about common sorting features, shown you some sorting examples, and explained some use cases for different sorting algorithms. However, you may find this information nice but a bit lacking because you need sorting information specific to the programming language the company wants you to use.
What’s more, there are more complex sorting algorithms out there, and the ones we’ve covered in this chapter are definitely lacking because you need to know more advanced sorting methods for your job interview.
We’re here for you. Hop onto Google and search for “sorting algorithms” and you’ll see a list of algorithms at the top of the screen that include visual diagrams of each one. Just click the sorting algorithm name or its associated diagram to refine your Google search and display websites that only discuss that algorithm.
Loads of reading material
There are some good websites out there that will give you more in-depth information. You can start with the Wikipedia website that contains charts and examples including the deck of cards example. Since Wikipedia is managed by the entire Internet community, it isn’t as well-regarded as other sources of information, and in the case of Wikipedia’s sorting algorithm article, there’s a warning at the top of the page (as of this writing, anyway) that says there aren’t enough links to reliable sources.
An excellent online resource is the GeeksforGeeks website (www.geeksforgeeks.org/sorting-algorithms) shown in Figure 11-1 that has in-depth resources about many sorting algorithms and examples of those algorithms in a variety of programming languages.
Source: www.geeksforgeeks.org
FIGURE 11-1: Click the sorting algorithm you want more information about in the Sorting Algorithms section.
When you scroll down the page, you’ll also find articles, frequently asked questions (and answers), a large number of coding problem examples and solutions, as well as links to practice sorting problems and quizzes.
Moving examples
If you’re more of a visual learner, more than a few websites contain animations of sorting algorithms so you can see how each one operates. Animated examples also illustrate the advantages and disadvantages of using each one. Just type (without the quotes) “sorting algorithms animation” into the Google Search box. The results page shows a list of sites as well as links to several animations on YouTube.
The site at the top of the search results is Toptal (www.toptal.com/developers/sorting-algorithms), shown in Figure 11-2. In the table at the top of the page, click one of the animations that shows how an algorithm sorts a list. For example, if you click the animation in the Random row and the Merge column, you’ll see how the merge sort algorithm reorders the random items in the list to create a neatly ordered list.
Source: www.toptal.com
FIGURE 11-2: Click Play All in the upper-left corner of the table to view all the animations.
Underneath the list you can change the conditions of the animation. For example, if you want to learn more about the quick sort algorithm, click Quick Sort to open a page that lets you view the animated examples for the quick sort algorithm and gives you more information about the algorithm and how it’s used.
Finally, when you scroll down to the bottom of any page on the site, you’ll see links to job interview guides for various programming languages.
Visualize the sort, Luke
If the animations don’t quite cut it and you prefer to see each step of the sorting process instead, check out the HackerEarth website visualizers at www.hackerearth.com/practice/algorithms/sorting/merge-sort/visualize. In Figure 11-3, you can see a sample for a simple merge sort.
Source: www.hackerearth.com
FIGURE 11-3: The third step on HackerEarth shows the initial array broken into two separate lists.
Under the array of numbers you see in the center of the screen, you see the text 1/99, which means this is Step 1 in the process that has a total of 99 steps (and we confirmed there really are 99 steps in this visualization exercise).
Proceed to the next step by clicking the right arrow button to the right of the step number. As you go through each step, you see the result of each step in the Visualize section as well as a brief description of what’s happening in the Steps section. As you keep clicking the right arrow button, you see the next step in the process. The step number appears to the left of the right arrow button, which in Figure 11-3 is Step 3. You can even change the array size and array values if you want.
What’s more, if you prefer to visualize how other sorting algorithms work, click one of the sorting types in the sorting list at the left side of the web page — the list includes a number of sorting algorithms we haven’t covered in this book so you can feed your ravenous brain.