Main content
Computer science
Course: Computer science > Unit 1
Lesson 4: Selection sortSelection 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(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(3 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 someone explain this whole thing to me(3 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;
// Loop over items starting with startIndex,
// updating minValue and minIndex as needed:
return minIndex;
};
var minValue;
var array = [18, 6, 66, 44, 9, 22, 14];
var index = indexOfMinimum(array, 2);
for (var i = index+1; i < array.length; i++) {
if (array[i] < array[index]) {
index = i;
minValue = array[i];
}
}
// 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);
This is working just fine, but challenge is not completed. Also i had to define minValue variable. Is there something wrong?(2 votes)
Sorry for the extremely latent response, but I was here and thought I might help. What you did was not within the parameters of the challenge. Re-reading the instructions: "Finish writing the function indexOfMinimum, which takes an array and a number startIndex, and returns the index of the smallest value that occurs with index startIndex or greater. If this smallest value occurs more than once in this range, then return the index of the leftmost occurrence within this range."
First, you incorrectly identified where you were intended to write that for loop. You need to finish indexOfMinimum. minValue was already provided for you if you had worked within the indexOfMinimum function.
Second, because you failed to use the function, you had to change index after it was already one, probably not something the challenge's validator would accept. There's a reason indexOfMinimum was intended to be used on index.(1 vote)
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.(2 votes)- can we choose the language.(2 votes)
- hello! i need help with this selection sort code. i don't know what i am doing wrong. please see below.
Selection Sort(myArray[] of length n)
begin
for i = 0 to n-2 repeat:
minIndx = i
for j = i+1 to n-1 repeat:
if myArray[j] < myArray[minIndx]
minIndx = j
end if
end for
swap myArray[minIndx] with myArray[i]
end for
end(1 vote)- The logic appears to be ok, but I don't recognize the programming language.
Things to check:
- In that language when you dofor i = 0 to X repeat:is X included or excluded ?
- Is the swap function working properly ?
- What errors are you getting ?
- Do you have any example inputs and outputs ?(2 votes)
