The act of sorting (organizing) something is a concept that is so naturally ingrained in our nature that we don’t really give it much thought. We think about what we want to organize and how we want to organize it, but specifically, we rarely think about the process itself. When organizing books in alphabetical order, do we sort two or three first, then go through the rest one by one placing them in context of the original three? Do we collect all the books that start with “A” and move on to the next letter only after we finish sorting the “A” books? There are many ways people choose to organize something, a lot of that comes down to the person, their style, and their personality.

For a computer however, they have limited visual scope and do not have personalities. They need a series of very specific commands to execute a behavior. Sorting is a very common behavior that computers are asked to execute. However, they do not have the same improvisational, dynamic memory we do. And that is where we really dive into the process of sorting something.

To begin, there are three very common sorting methods for computers to execute: bubble sort, merge sort, and quick sort. But before we go into what each of these sorting methods mean, let’s start off with a sorting scenario. Imagine you want to sort a handful of playing cards from lowest to highest (disregarding the suit). However, all these cards are all faced down, and you can only flip over and view two cards at a time.

Bubble Sort:
The bubble sorting method compares two adjacent elements at the same time. Switch the two elements to fit the sorting condition. Once you make it through all the elements, go back and start over until you can make it through a list without switching anything at all.

In our example, imagine you have 8 facedown cards. Remember you can only look at two cards at a time. With the bubble method, you will look at the first two cards, and switch if the first card is larger than the second. Then you will look at the second and third card and switch if the second card is larger than the third, leave it be if not. After going through all 8 cards, repeat the process until you have made it through the list without switching any pair.

Note however, that this is the slowest and most inefficient sorting method out of the three. It has the most comparisons and takes the longest to complete. This video below does a great job of illustrating this point.

Merge Sort:

The merge sort method continually divides the elements into halves until it is able to compare two sets of elements that are already sorted. At the beginning it will break everything down into individual “halves.” Once it has two sets of sorted elements, it will compare one element of each set. It will set aside the smallest of the two, and pick up the next element of the former set. It will continue to compare an element of each set until one set empties.

In our example of 8 facedown cards, it will break it down into individual cards. It will then compare the first and second card then sets it aside as a sorted pair of two cards. Then it compares the third and fourth card. Once sorted it will be set aside as another sorted pair of two. Once all eight cards are sorted into twos, it will compare the first and second cards to the third and fourth cards. It compares the first cards of each set (so the first and third cards) and sets aside the smallest of the pair. Then it will compare the existing card with the last card in the other set. The video above also shows the merge method well.

Quick Sort:

The quick sort method randomly selects an element to use as a reference, otherwise called as a “pivot.” You then compare every element to the pivot and assign them to either the left or right. Once they are sorted into two groups choose another pivot within each group and continue the process until it is all sorted.

In our example of 8 facedown cards select one card at random. Let’s say it is a 5 of hearts. Now go through each card and place cards that are lower than 5 to the left, and those larger than 5 to the right. Now you have divided the cards into two groups. Select a new pivot amongst the cards smaller than 5 and continue the process

Previous Index Next