Main content

## Computer science theory

### Course: Computer science theory > Unit 1

Lesson 4: Selection sort# Selection sort pseudocode

There are many different ways to sort the cards. Here's a simple one, called

**selection sort**, possibly similar to how you sorted the cards above:- Find the smallest card. Swap it with the first card.
- Find the second-smallest card. Swap it with the second card.
- Find the third-smallest card. Swap it with the third card.
- Repeat finding the next-smallest card, and swapping it into the correct position until the array is sorted.

This algorithm is called selection sort because it repeatedly

*selects*the next-smallest element and swaps it into place.You can see the algorithm for yourself below. Start by using "Step" to see each step of the algorithm, and then try "Automatic" once you understand it to see the steps all the way through.

After seeing it for yourself, what do you think about this algorithm? What parts of it seem to take the longest? How do you think it would perform on big arrays? Keep those questions in mind as you go through and implement this algorithm.

### Finding the index of the minimum element in a subarray

One of the steps in selection sort is to find the next-smallest card to put into its correct location. For example, if the array initially has values [13, 19, 18, 4, 10], we first need to find the index of the smallest value in the array. Since 4 is the smallest value, the index of the smallest value is 3.

Selection sort would swap the value at index 3 with the value at index 0, giving [4, 19, 18, 13, 10]. Now we need to find the index of the second-smallest value to swap into index 1.

It might be tricky to write code that found the index of the second-smallest value in an array. I'm sure you could do it, but there's a better way. Notice that since the smallest value has already been swapped into index 0, what we really want is to find the smallest value in the part of the array that starts at index 1. We call a section of an array a

**subarray**, so that in this case, we want the index of the smallest value in the subarray that starts at index 1. For our example, if the full array is [4, 19, 18, 13, 10], then the smallest value in the subarray starting at index 1 is 10, and it has index 4 in the original array. So index 4 is the location of the second-smallest element of the full array.Try out that strategy in the next challenge, and then you'll have most of what you need to implement the whole selection sort algorithm.

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?

- Please provide another programming languages instead of Java scripts.

For examples:c,Python,c#(19 votes)- Sorry, why should they use another language, do you know how hard it would be for them to setup a sandbox for that language. Plus JavaScript is the most popular languages this year.(0 votes)

- I don,'t know javascript shall i stop the course here learn javascript then resume it(7 votes)
- var indexOfMinimum = function(array, startIndex) {

// Set initial values for minValue and minIndex,

// based on the leftmost entry in the subarray:

var minValue = array[startIndex];

var minIndex = startIndex;

for (var x=minIndex+1; x<array.length; x++)

{if(array[x]<minValue)

{minIndex=x;

minValue= array[x];

}

}

// Loop over items starting with startIndex,

// updating minValue and minIndex as needed:

return minIndex;

};

var array = [18, 6, 66, 44, 9, 22, 14];

var index = indexOfMinimum(array, 2);

// For the test array [18, 6, 66, 44, 9, 22, 14],

// the value 9 is the smallest of [..66, 44, 9, 22, 14]

// Since 9 is at index 4 in the original array,

// "index" has value 4

println("The index of the minimum value of the subarray starting at index 2 is " + index + "." );

Program.assertEqual(index, 4);

Program.assertEqual(indexOfMinimum(array,3),4);

Program.assertEqual(indexOfMinimum(array,0),1);

var indexOfMinimum = function(array, startIndex) {

// Set initial values for minValue and minIndex,

// based on the leftmost entry in the subarray:

var minValue = array[startIndex];

var minIndex = startIndex;

for (var x=minIndex+1; x<array.length; x++)

{if(array[x]<minValue)

{minIndex=x;

minValue= array[x];

}

}

// Loop over items starting with startIndex,

// updating minValue and minIndex as needed:

return minIndex;

};

var array = [18, 6, 66, 44, 9, 22, 14];

var index = indexOfMinimum(array, 2);

// For the test array [18, 6, 66, 44, 9, 22, 14],

// the value 9 is the smallest of [..66, 44, 9, 22, 14]

// Since 9 is at index 4 in the original array,

// "index" has value 4

println("The index of the minimum value of the subarray starting at index 2 is " + index + "." );

Program.assertEqual(index, 4);

Program.assertEqual(indexOfMinimum(array,3),4);

Program.assertEqual(indexOfMinimum(array,0),1);

I passed the challenge with this code. Hope it helps.(6 votes) - Hello,

I having little trouble about implementing the selection sort

var selectionSort = function(array) {

var temp;

for(var i = 1; i < array.length; i++){ // starting array iteration at index = 1

temp = indexOfMinimum(array,i); // to store value of minIndex

if(array[temp] < array[i-1]){ // comparing the value at minIndex with element //present at i-1

//swap if value at minIndex less than value at i-1

swap(array, i-1,temp);

}

}

};

even though the console shows the correct sorted array i cannot move to next step.

I would like to know what is the bug in code.

Thank you!(4 votes)- While it will sort the values correctly, it is a bit different from how selectionSort normally works. It is different enough that the grader doesn't think it is following the selectionSort algorithm.

Normally in selection sort:

- instead of starting at index 1 you would start at index 0.

- you don't have to check the value of the minValue (array[temp] in your code) vs the value at the index, instead you just always swap the minValue and the value at the index (this will be safe if the range of values you previously checked for your minValue includes the value at the index )

Good Luck(3 votes)

- I'm sorry, I do not speak english, but

If you have the array = [ 1, 1, 0, 2 ] and applying the algorithm as it says in the second paragraph, by analogy with the cards , as in the first iteration of the array would be ordered because it is : array = [0 , 1, 1 , 2] . Wonder is necessary to continue the algorithm until through all the indices in the subarray as paragraph 6 states or stopped in the first iteration .(3 votes)- With selection sort, you have to go through all the iterations (the algorithm has no way of knowing if the array is sorted before it has done all the iterations) . However, you could try to optimize the algorithm by checking to see if the array was sorted.

To be able to skip future iterations once sorted, you would need to add a flag if an unsorted pair of neighbors was found, and then each pass, you would need to check, for each element whether each pair of neighbors was sorted. If not, the flag would be set to false. After each pass you could check the flag. If the flag was true, then you could skip the future iterations since the array was sorted. This optimization is often incorporated into bubble sort which compares neighbors anyhow ( bubble sort is O(n^2) but generally performs worse than the other O(n^2) sorting algorithms). The problem with adding this check to selection sort is it adds an additional comparison, which would make the algorithm slower for arrays which are not nearly sorted.

That being said, if you thought you were going to be sorting a lot of arrays that were nearly sorted, then you should just use insertion sort, which performs very well with nearly sorted arrays.

Hope this makes sense(4 votes)

- This code for the selection sort isn't remotely working-- can anyone give me a tip as to what I'm doing wrong?

[Edited to only show relevant code]`var selectionSort = function(array) {`

var x;

for(x = 0; x < array.length; x++) {

x = indexOfMinimum(array, x);

...

}

};(3 votes) - can we choose the language.(3 votes)
- I fail to see why this doesn't work :(

for (var i = minIndex + 1; i === array.length - 1; i++) {

if (min(minValue, array[i]) < minValue) {

minIndex = i;

minValue = array[i];

}

}(2 votes)- There's a couple of issues:

1)

Suppose we call:`indexOfMinimum([2,9,1],0)`

The first time the for loop executes:

What is the value of`i`

?

What is the value of`array.length`

?

Is`i === array.length-1`

true or false ?

That should show the first problem.

2)

- You shouldn't need to call the min function, in the condition of your if statement. You should be able to simplify that condition.

Good Luck(3 votes)

- In the challenge implement selection sort I had the code
`var swap = function(array, firstIndex, secondIndex) {`

var temp = array[firstIndex];

array[firstIndex] = array[secondIndex];

array[secondIndex] = temp;

};

var 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];

}

}

return minIndex;

};

var selectionSort = function(array) {

var MinIndex;

for(var StartingIndex;StartingIndex<array.length;StartingIndex++ ) {

MinIndex = indexOfMinimum(array,StartingIndex);

swap(array, StartingIndex, MinIndex);

}

};

var array = [22, 11, 99, 88, 9, 7, 42];

selectionSort(array);

println("Array after sorting: " + array);

Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]);

The Program.assertEqual said that my code was wrong. I don't know why the function selectionSort isn't working. Can you help me?(2 votes)`StartingIndex`

isn't initialized to any value, so it is`null`

(which is an invalid input to the`indexOfMinimum`

function).

As a side note, the general convention in JavaScript for variable names is camel case with the initial letter in lower case i.e.`startingIndex`

instead of`StartingIndex`

. It won't impact how your code works, but it will make it easier for others to read your code if you follow the convention.(3 votes)

- can someone explain this whole thing to me(3 votes)