# 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.

Malcolm NealPost authorCool video, thanks!

Salman AhmadPost authorThanks too much nice

kiran ganesanPost authorawesome ….. easy to understand … thanku buddy

Mr.xPost authorCan anyone help me providing line by line times for this code ?? It would be a great help…

Faraaz JabbarPost authorYou're the best

coraline 69 _Post authorthank you so much

coraline 69 _Post authorThank you so much

doodle238gamer -Post authoryo mama sooooo FAT i took a pic of her last christams its still printing

OLOLOL