A slow but very easy-to-comprehend sort algorithm is selection sort. It's approach is very simple. Let's say you have a boring list of values that you want sorted
Selection sort works by finding (aka...selecting) the smallest item in your entire list. Once it finds that smallest item, it showers it with love and praise and makes it the first sorted item in a region it carves out called the sorted region. Our selection sort then goes out and finds the next smallest item in the list. Once it finds that item, it places it directly after our earlier smallest item in the sorted region. This whole process of finding the next smallest item and shoving it in the sorted region repeats itself until there are no more unsorted items left.
All of this probably doesn't make a whole lot of sense. It is also boring, so let's fix that with some pictures and stuff in the next section.
Onwards!
Since I am extremely lazy, let's just continue with the input of bars you saw earlier. Our goal is to use selection sort to sort the bars from shortest to tallest. Along the way, we will also learn a thing or two about how selection sort actually works. Hopefully.
First, putting on our selection sort mask, we are going to assume the first item is the smallest item in the list:
Before you start jumping up and down about the absurdity of this, hold on a second. The next step is to see if the first item is indeed the smallest item in our list. To answer this, selection sort walks through the entire list and compares the size of each item with our current smallest (...and first) item:
Usually, the first item is rarely the smallest item for long. When selection sort encounters an item that is smaller, this new item becomes the new smallest item. As you can see, this happens immediately in our example, for the next item is smaller than the first item:
At this point, we have a new smallest item. Just like before, though, it is premature to call it a day since we have only examined two values at this point. Our quest to find the smallest number needs to continue, so we compare our newest smallest value with the remaining items in the list to see if another item will take the smallest item crown.
During this trip, you will frequently encounter numbers that are larger than your current smallest value:
When that happens, simply skip over it and move on to the next item and repeat the comparison:
Selection sort will go through the entire list until it has selected the smallest item. For this example, that would be the following bar:
All that is left is to move this number to the mysterious sorted region that I alluded to earlier, and let's assume that we are going to carve our sorted region from the beginning of our list. To do this, our next step is to swap our smallest item with the first item we started with - the first item in our unsorted region:
Once this happens, your list is partially sorted with the smallest item leading the way. The rest of our list is still unsorted, though:
Your sorted region contains one item. Your unsorted region contains everything else. Now, here is where things are going to get a little repetitive and painful...for your computer. We repeat all of what you've seen on the new first item in our unsorted part of the list.
Inside the unsorted world, there is now a new smallest number in town:
Just like before, the new smallest number is the first item. As selection sort goes through the unsorted items to find the smallest item, that will change. To be more precise and foreshadowy, it will change to the following bar after all of the unsorted items are examined:
The next step is for this item to be swapped with our first unsorted item with the sorted region of our list getting one more entry:
This process of finding a new smallest number and swapping it into the sorted region repeats until you have no more unsorted items:
Now, next is where I would normally do a detailed walkthrough using real numbers instead of bars of varying heights. Given how straightforward this algorithm is, let's just skip all that and go to the boring stuff.
Selection sort is pretty easy to wrap your brain around. It simply goes through your list of data to find the smallest number, the next smallest number, and so on. Once it finds the smallest number, it places it in what I call the sorted region. There is a lot of flexibility in how you want to implement your sorted region.
Your sorted region could be at the beginning like it was in the examples we've looked at so far:
It could also be at the end:
If you really want to be cray cray, you can use an entirely new list to store your sorted items:
For the most part, given how most list-like data types work in many languages, placing your sorted items at the beginning is straightforward to implement. Placing them at the end or creating an entirely new sorted list requires a little extra effort on your part. Pick whatever makes your life easier. The performance and memory characteristics of all three approaches is pretty similar, so you don't have that to factor those in as part of your decision.
Speaking of performance and memory, selection sort isn't a fast algorithm for sorting your data. Because you pick an unsorted item and compare it against every single other unsorted item, you are doing a whole bunch of comparisons. Basically, it runs in n2 time. From a memory point of view, insertion sort is very good. It doesn't take up much memory beyond any extra objects you need for storing your input itself. That shouldn't be too surprising because almost all of our sorting-related shenanigans are done in-place on the input itself.
We are almost done here. The last thing is to look at an example selection sort implementation in JavaScript:
function selectionSort(input) { for (var i = 0; i < input.length; i++) { // assume the item in the first position is the smallest var smallestPosition = i; // go through the unsorted region for (var j = i + 1; j < input.length; j++) { if (input[j] < input[smallestPosition]) { // a new smallest number is found smallestPosition = j } } // swap the min value if it changed if (smallestPosition != i) { var temp = input[smallestPosition]; input[smallestPosition] = input[i]; input[i] = temp; } } } var myinput = [24, 10, 17, 9, 5, 9, 1, 23, 300]; selectionSort(myinput); alert(myinput);
The JavaScript doesn't veer too far from the English description you saw in the previous two sections. The outer loop represented by the i variable is responsible for going through each item in the list, and its position marks the dividing line between the sorted region and unsorted region of your input:
The inner loop represented by the talented j variable is responsible for comparing the item at the outer loop's position with every remaining item in the list. This is the time-consuming and slow part that selection sort is famous for:
As for other interesting landmarks in our code, the smallestPosition variable stores the position of the smallest item. It starts off as the first item in the unsorted region and then (potentially) changes as the inner loop does the checking against every remaining item in unsorted part of the list.
Once the smallest item has been found, that item gets swapped with the element at the i position. The code for that looks as follows:
if (smallestPosition != i) { var temp = input[smallestPosition]; input[smallestPosition] = input[i]; input[i] = temp; }
Just because I am OCD, I do a check to only do the swap if our smallest item is indeed different than the item we started off with. While that doesn't happen often, it is enough to worth adding the check to avoid some unnecessary operations. You can safely skip that if statement if you can sleep well at night without it.
Selection sort makes up the large number of sorts that is easy to understand but not very fast. To see how selection sort compares with other sort algorithms, check out the following table:
Name | Best | Average | Worst | Memory |
---|---|---|---|---|
Quicksort | n log n | n log n | n2 | log n (average) |
Mergesort | n log n | n log n | n log n | n (worst case) |
Heapsort | n log n | n log n | n log n | 1 |
Timsort | n | n log n | n log n | n |
Bubble sort | n | n2 | n2 | 1 |
Selection sort | n2 | n2 | n2 | 1 |
Insertion sort | n | n2 | n2 | 1 |
You can find a more detailed comparison of these sorting algorithms as well as many others over on the Wikipedia section fully dedicated to this. If I were you and looking for a slow sort alogirthm that is easy to implement, I would probably choose insertion sort over selection sort any day of the week.
Just a final word before we wrap up. If you have a question and/or want to be part of a friendly, collaborative community of over 220k other developers like yourself, post on the forums for a quick response!