If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

### Course: Computer science theory>Unit 1

Lesson 4: Selection sort

# Analysis of selection sort

Selection sort loops over indices in the array; for each index, selection sort calls indexOfMinimum and swap. If the length of the array is $n$, there are $n$ indices in the array.
Since each execution of the body of the loop runs two lines of code, you might think that $2n$ lines of code are executed by selection sort. But it's not true! Remember that indexOfMinimum and swap are functions: when either is called, some lines of code are executed.
How many lines of code are executed by a single call to swap? In the usual implementation, it's three lines, so that each call to swap takes constant time.
How many lines of code are executed by a single call to indexOfMinimum? We have to account for the loop inside indexOfMinimum. How many times does this loop execute in a given call to indexOfMinimum? It depends on the size of the subarray that it's iterating over. If the subarray is the whole array (as it is on the first step), the loop body runs $n$ times. If the subarray is of size 6, then the loop body runs 6 times.
For example, let's say the whole array is of size 8 and think about how selection sort works.
1. In the first call of indexOfMinimum, it has to look at every value in the array, and so the loop body in indexOfMinimum runs 8 times.
2. In the second call of indexOfMinimum, it has to look at every value in the subarray from indices 1 to 7, and so the loop body in indexOfMinimum runs 7 times.
3. In the third call, it looks at the subarray from indices 2 to 7; the loop body runs 6 times.
4. In the fourth call, it looks at the subarray from indices 3 to 7; the loop body runs 5 times.
5. In the eighth and final call of indexOfMinimum, the loop body runs just 1 time.
If we total up the number of times the loop body of indexOfMinimum runs, we get 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 times.

### Side note: Computing summations from 1 to $n$‍

How do you compute the sum 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 quickly? Here's a trick. Let's add the numbers in a sneaky order. First, let's add 8 + 1, the largest and smallest values. We get 9. Then, let's add 7 + 2, the second-largest and second-smallest values. Interesting, we get 9 again. How about 6 + 3? Also 9. Finally, 5 + 4. Once again, 9! So what do we have?
There were four pairs of numbers, each of which added up to 9. So here's the general trick to sum up any sequence of consecutive integers:
1. Add the smallest and the largest number.
2. Multiply by the number of pairs.
What if the number of integers in the sequence is odd, so that you cannot pair them all up? It doesn't matter! Just count the unpaired number in the middle of the sequence as half a pair. For example, let's sum up 1 + 2 + 3 + 4 + 5. We have two full pairs (1 + 5 and 2 + 4, each summing to 6) and one "half pair" (3, which is half of 6), giving a total of 2.5 pairs. We multiply $2.5\cdot 6=15$, and we get the right answer.
What if the sequence to sum up goes from 1 to $n$? We call this an arithmetic series. The sum of the smallest and largest numbers is $n+1$. Because there are $n$ numbers altogether, there are $n/2$ pairs (whether $n$ is odd or even). Therefore, the sum of numbers from 1 to $n$ is $\left(n+1\right)\left(n/2\right)$, which equals ${n}^{2}/2+n/2$. Try out this formula for $n=5$ and $n=8$.

## Asymptotic running-time analysis for selection sort

The total running time for selection sort has three parts:
1. The running time for all the calls to indexOfMinimum.
2. The running time for all the calls to swap.
3. The running time for the rest of the loop in the selectionSort function.
Parts 2 and 3 are easy. We know that there are $n$ calls to swap, and each call takes constant time. Using our asymptotic notation, the time for all calls to swap is $\mathrm{\Theta }\left(n\right)$. The rest of the loop in selectionSort is really just testing and incrementing the loop variable and calling indexOfMinimum and swap, and so that takes constant time for each of the $n$ iterations, for another $\mathrm{\Theta }\left(n\right)$ time.
For part 1, the running time for all the calls to indexOfMinimum, we've already done the hard part. Each individual iteration of the loop in indexOfMinimum takes constant time. The number of iterations of this loop is $n$ in the first call, then $n-1$, then $n-2$, and so on. We've seen that this sum, $1+2+\cdots +\left(n-1\right)+n$ is an arithmetic series, and it evaluates to $\left(n+1\right)\left(n/2\right)$, or ${n}^{2}/2+n/2$. Therefore, the total time for all calls to indexOfMinimum is some constant times ${n}^{2}/2+n/2$. In terms of big-Θ notation, we don't care about that constant factor, nor do we care about the factor of 1/2 or the low-order term. The result is that the running time for all the calls to indexOfMinimum is $\mathrm{\Theta }\left({n}^{2}\right)$.
Adding up the running times for the three parts, we have $\mathrm{\Theta }\left({n}^{2}\right)$ for the calls to indexOfMinimum, $\mathrm{\Theta }\left(n\right)$ for the calls to swap, and $\mathrm{\Theta }\left(n\right)$ for the rest of the loop in selectionSort. The $\mathrm{\Theta }\left({n}^{2}\right)$ term is the most significant, and so we say that the running time of selection sort is $\mathrm{\Theta }\left({n}^{2}\right)$.
Notice also that no case is particularly good or particularly bad for selection sort. The loop in indexOfMinimum will always make ${n}^{2}/2+n/2$ iterations, regardless of the input. Therefore, we can say that selection sort runs in $\mathrm{\Theta }\left({n}^{2}\right)$ time in all cases.
Let's see how the $\mathrm{\Theta }\left({n}^{2}\right)$ running time affects the actual execution time. Let's say that selection sort takes approximately ${n}^{2}/{10}^{6}$ seconds to sort $n$ values. Let's start with a fairly small value of $n$, let's say $n=100$. Then the running time of selection sort is about ${100}^{2}/{10}^{6}=1/100$ seconds. That seems pretty fast. But what if $n=1000$? Then selection sort takes about ${1000}^{2}/{10}^{6}=1$ second. The array grew by a factor of 10, but the running time increased 100 times. What if $n=1,000,000$? Then selection sort takes ${1,000,000}^{2}/{10}^{6}=1,000,000$ seconds, which is a little more than 11.5 days. Increasing the array size by a factor of 1000 increases the running time a million times!
This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

## Want to join the conversation?

• In the Project: Selection Sort Visualiser, do we have to draw the lines manually or using the displayArray() function? If it is using displayArray() function then how? Please help...
• You will need to write the code to draw the lines or arrows yourself. However, you don't want to "hard code" the lines i.e. you should be able to change the array you are sorting, and your code should automatically draw the lines in the proper spot.

As far as the displayArray() function goes, it doesn't really do anything right now. You may want to use it put your code to display your array. Feel free to modify it or add additional functions to complete your project.

Good luck
• I was wondering if someone could elaborate on the statement in the second-to-last paragraph that "no case is particularly good or particularly bad for selection sort." If n is 1, why does that not count as a particularly good case for selection sort? It would still be (n^2 + n/2) iterations, but wouldn't that be like running near O(n) and therefore being really good? I must be confused.
• What it is talking about is, for a given size of the input n, some algorithms will behave poorly or really well depending on how the input is arranged.

Some sorting algorithms, like insertion sort, really like arrays that are sorted or almost sorted. For an already sorted array, insertion sort will run in O(n), which is fantastic, especially when compared to it's worst case running time of O(n^2).

Some sorting algorithms, like quick sort (using the front or back element as a pivot), hate arrays that are nearly sorted or already sorted. For an already sorted array, quick sort degrades to O(n^2), which is quite bad when compared to it's average case running time of O(n log n).

Other sorting algorithms, like selection sort, don't really care what the array looks like. These algorithms will typically perform the same number of steps regardless of what the input looks like. Selection sort will run in O(n^2) regardless of whether the array is already sorted or not.

Hope this makes sense
• I need help with making my text appear on the canvas in the project. How do I make it display the array?
• I decided to come here to get help because I have been waiting over a week to get help on the Selection sort visualizer project, using the Help requests tab on the project page.
I got it to display lines, the final array and rectangles. However, I need help in displaying the initial array and the steps in between. Any help would be greatly appreciated.
//display the Arrayvar displayArray = function(array) {    fill(255, 0, 0,0);    stroke(0, 0, 0);    rect(array[0],array[0],array.length*28,array.length*20);    textFont(createFont("monospace"), 12);   fill(255, 0, 0);    text(array, array[0]+3,array[0]+15);    };//swap function to rearrange the arrayvar swap = function(array, firstIndex, secondIndex) {    var temp = array[firstIndex];    array[firstIndex] = array[secondIndex];    array[secondIndex] = temp;};//find the minimum in the original arrayvar indexOfMinimum = function(array, startIndex) {    var minValue = array[startIndex];    var minIndex = startIndex;    for(var i = minIndex + 1; i < array.length; i++) {        if(array[i] < minValue) {            minIndex = i;            minValue = array[i];            line(array[i],array[i],array[0],array[0]);        }    }     return minIndex;}; //sort the functionvar selectionSort = function(array) { var relocate; for(var i=0; i<array.length;i++){     relocate = indexOfMinimum(array,i);     swap(array, i, relocate); }  displayArray(array);};//display the various arraysvar array = [2,1,3,4,5];selectionSort(array);var backward=[450,400,300,280];selectionSort(backward);var samething = [250,250,300,200];selectionSort(samething);var loneStar = [150,110,200,201];selectionSort(loneStar);
• Theta of n squared!? That really is terrible;
does Selection Sort have any practical uses?
• Selection sort shares many of the benefits that insertion sort has, which is also O(n^2):
- It performs well on small inputs. (If n is small it will beat O(n log n) sorts )
- It requires only constant extra space (unlike merge sort)

It also has some extra benefits:
- It's very simple. So, it is easy to program.
- It only requires n swaps (which is better than most sorting algorithms)
- For the same set of elements, it will take the same amount of time regardless of how they are arranged. This can be good for real time applications.

Here are the Cons:
- O(n^2) is slower than O(n log n) algorithms (like merge sort) for large inputs.
- Insertion sort, which is also O(n^2), is usually faster than it on small inputs.

Situations when you want to use it include the following:
- You need a sort algorithm that is easy to program (or that requires a small amount of code)
- You only have a small number of elements to sort, so you feel that it is quick enough
- Swaps are expensive on your hardware, but you don't want to use the more complicated Cycle sort.
- You need the sorting time to be consistent for a given size.

Hope this makes sense
• I am still confused how indexOfMinimum loop is n^2 since it's just a normal for loop, just like the loop of selectionSort function except it starts at minIndex + 1
• Here's the quick and dirty (not entirely accurate) version:
-On average indexOfMinimum loops ~n/2 times every time selectionSort calls it
-selectionSort calls indexOfMinimum ~n times
total number of loops = calls * average loops/call
total number of loops = n * n/2 = 1/2 * n^2

Hope this makes sense
• when saying "1 to n" is n here represent the items count (e.g. 3 in case of [7, 4, 2]) or does it represent the last index (e.g. 2 in case of [7, 4, 2])
• Second sentence. "If the length of the array is n,"

In general, when one analyzes algorithms, n is going to be the size of the input. For an array the size of the input is based on the number of elements in the array (each element has some fixed size).
• If you run selectionSort on the array [5,2,3,4,1]
after the first iteration the array is sorted does
the program go on to swap elements with themselves?
How to code to guard against this?
• Yes, selectionSort would continue to operate as normal (swapping each element with the minimum element >= its index), as it would be unaware that the rest of the array was sorted.

One could add a check to see if the subarray was sorted, (just add for loop to check that each element >= the previous), which would take linear time i.e. O(n). So, while it would add computational time, the overall algorithm would still be O(n^2).

Normally, one wouldn't bother doing this with selection sort. Why?
If one thought that their arrays had large sorted chunks, they would switch to using insertion sort, or even the often maligned bubble sort. Insertion sort and bubble sort run in almost linear time i.e. O(n) on mostly sorted arrays.
• It is still not clear to compute things, for example.
var selectionSort = function(array)
{
var minimumIndex = 0; ONCE
for (var i = 0; i < array.length; i++) N times
{
minimumIndex = indexOfMinimum(array, i); ? if this is n(n+1)/2
swap(array, i, minimumIndex); 3 Times
}
then it becomes cubic algorithm.
If somebody is willing to clarify this it would be very helpful.
Thanks
• The for loop executes n times. The contents of the for loop is:
- indexOfMinimum which is O(n) (at most it searches all n elements to see if it is the min)
- swap is just O(1) (constant time)

So, at most, selections sort requires: n * O(n) which is O(n^2)

n(n+1)/2 is the sum of the series: 1 + 2 + 3 + 4 + ... + n
Which would be the sum of the number of elements that indexOfMinimum has to check for ALL of the iterations of the for loop. (In the above, when I showed that selectionSort was O(n^2) I just assumed that each time it searched all n elements, because it didn't affect the asymptotic analysis)

Hope this makes sense