Selection Sort – Algorithm and Analysis

Selection Sort – Algorithm and Analysis

Articles, Blog , , , , , , , , , , , , 8 Comments


Welcome! In this video I’ll be discussing
the “Selection Sort” algorithm for sorting lists of items. Selection sort is one of the
simplest sorting algorithms out there, both conceptually and implementation-wise; which
makes it a good starting point for new learners. Let’s go ahead and get started.
The idea behind selection sort is based on dividing the original list into two sections:
sorted and unsorted. One by one the minimum element from the unsorted section is moved
to the sorted section, until all elements have been moved.
For example, say we want to sort these cards in ascending order, from smallest to largest.
We have our original list, which we assume is unsorted, and a sorted section that is
initially empty. We start by moving the two of clubs to the sorted section because it’s
the smallest. Now, we look for the *next* smallest in the unsorted section, which is
the four of clubs. So, we move that, then six, and finally seven. We now have a sorted list.
This works fine, but programmatically, the sorted section translates to an additional
array, which uses up unnecessary space. It’s not a big deal for our tiny list of four elements,
but if we have a much larger list, say 10,000 elements, we would need space to store double
that amount; 20,000. Let’s take a look at how we can modify this into an “in-place”
sorting algorithm; one that takes away the need for an extra array.
Here, we have an array containing the same four cards from the previous example. And,
like before, the whole list is initially labeled as unsorted. Even if the list were already
sorted, our program wouldn’t know until it checks each one. We’ll first step through
this with some high-level pseudocode to get the concept down.
The outer loop kicks things off by setting the current slot to index zero, because that’s
where the unsorted section begins. The inner loop finds that the two of clubs is our minimum
element. So, we place it in the current slot by swapping it with whatever card is already
there; in this case, six. Two now becomes part of the sorted section, so it’s no longer
considered in our search for the minimum. The current slot gets incremented to index
one, and now, we look for the *next* smallest number in the unsorted section, which is four.
We move that to the current slot, and now four becomes part of the sorted section, too.
Once again, increment the current slot to index two and find the minimum, which is six.
Six is already *in* the current slot, so there’s no need to swap, this time. Finally, six is
added to the sorted section, and our job is done. We don’t need to bother with the seven
because the last element will always be in its proper place. It can’t go anywhere else.
The list is now sorted. Now, we’ll walk through this same process,
with some actual C++ code and a different set of cards. “i” represents the current
slot, which starts off at index zero. We set the minimum index to a default value equal
to “i,” so we have something to compare against. This will keep track of where the
minimum element is stored. Next, we step into the inner loop, where j represents the index
being tested for the minimum element. j starts at index i + 1, which is one, so we ask the
question, “Is five less than our current minimum, three?” No, so j is incremented to
index two. Is four less than three? No, so increment j to index three. Is three less than three?
Once again, the answer is no, so we increment j to index four. Ah, finally. Two is less
than three so we update the position of our minimum element to index four, which is the
current value of j. Now, we exit the inner loop and check to see if two is already in
the current slot. If not, swap it with whatever is there; in this case, the three of diamonds.
Two now becomes part of the sorted section and we start the whole process again; this
time starting from index one. With five as our new default minimum, we step back into
the inner loop and start comparing. Is four less than five? Yes, so we set minIdx to two.
Is three less than four? Yes, so it’s updated again, to index three. Is three less than
three? No, so the three of clubs remains as our minimum. It’s not already in the current
slot so it’s swapped with five and now part of the sorted section. Now, four becomes our
default minimum. Is five less than four? Nope. How about three? Yes it is, so it’s our
new minimum. Swap it with four in order to place it in the current slot and now we head
to our final iteration. Is four less than five? Yes, so we swap those two elements,
leaving us with only one card left in the unsorted section. But remember, the last remaining
element is always in its correct position, so we’re finished. The list is sorted.
Okay, time to conclude this tutorial with a quick analysis of the algorithm. I’ll
structure this around four key properties of sorting algorithms: time complexity, space
complexity, stability, and adaptability. First up: time complexity, using “big O
notation.” In short, time complexity measures how long it takes an algorithm to complete,
relative to input size, n. And big O notation describes the max, or worst-case, of that
measurement. With that said, let’s turn our attention to the code. The phrase “relative
to input size, n” tells us that we should mainly consider loop statements or recursive
calls that involve n. Here, we have two loops; one nested inside the other. The statements
in the inner loop execute n – 1 times for i equals 0, n – 2 times for i equals 1,
n – 3 times for i equals 2, and so on. This turns out to be an arithmetic progression,
which equals n( n – 1 ) / 2. Written in polynomial form it evaluates to n^2 – n
/ 2. However, Big O notation only cares about the highest order term of a polynomial so,
the time complexity of selection sort is O(n^2), which is worst case. And because selection
sort makes a fixed number of comparisons based on n, the best case always makes the same
number of comparisons as the worst case. So, the best case and average case also turn out to be O(n^2), as well. Next up: space complexity, also using big
O notation. Because this is an in-place sorting algorithm, it doesn’t require any extra
space so it’s O( 1 ). Or said differently, it requires a constant amount of additional
space. Stability: A sorting algorithm is stable if
the initial order of equal elements is preserved. Because selection sort swaps elements to random
locations, it is not a stable algorithm. We actually saw an example of this in our C++
demonstration. Initially, the three of diamonds was positioned before the three of clubs,
but this was not the case in the end state. Adaptability: A sorting algorithm is adaptive
if it can take advantage of the initial order; improving performance the more the list is
already sorted. Selection sort is not an adaptive algorithm because it makes a fixed number
of comparisons based on n, regardless of whether the list is initially sorted or not; no early
exit condition. In conclusion, selection sort is not a very
efficient sorting algorithm, particularly with large lists, since it’s O( n^2 ) for
all cases. And although it usually performs better than bubble sort, because of far fewer
needed swaps, insertion sort is normally the preferred alternative. I hope this tutorial
was helpful and easy to understand. The next video will cover the bubble sort algorithm.
Thanks for watching.

8 thoughts on “Selection Sort – Algorithm and Analysis

Leave a Reply

Your email address will not be published. Required fields are marked *