Main content
Computer science
Course: Computer science > Unit 1
Lesson 4: Selection sortSorting
Sorting a list of items into ascending or descending order can help either a human or a computer find items on that list quickly, perhaps using an algorithm like binary search. JavaScript has a built-in sorting method. It works on arrays of numbers, or even on arrays of strings:
var animals = ["gnu", "zebra", "antelope", "aardvark", "yak", "iguana"];
animals.sort();
println(animals);Even though JavaScript has a built-in sorting method, sorting is a great example of how there may be many ways to think about the same problem, some perhaps better than others. Understanding sorting is a traditional first step towards mastery of algorithms and computer science.
You'll implement a particular sorting algorithm in a moment. But as a warmup, here is a sorting problem to play with. You can swap any pair of cards by clicking on one card, and then the other. Swap cards until the cards are sorted with smallest card on the left.
What strategy did you use for sorting the cards? Did your strategy change as you sorted?
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?
I have no clue what code to type on the next challenge as KA do not explain at all, can someone plz help?(13 votes)
I am having trouble with the second step of he implement swap challenge.
the only way to get the assertions to pass is to delete on of the igniters but leave a comma. This is only necessary in one of the assertions not the other and not in the first that challenge previously provided.
the code as follows is considered correct.
If i reinsert an igniter into *Program.assertEqual(testArray, [ , 4, 9]);* before the first comma the program does not pass.
*Program.assertEqual(testArray, [ 7, , 9]);* however is also a correct solution according to the challenge computer.var swap = function(array, firstIndex, secondIndex) {
var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
};
var testArray = [7, 9, 4];
swap(testArray, 0, 1);
println(testArray);
Program.assertEqual(testArray, [9, 7, 4]);
swap(testArray, 1, 2);
Program.assertEqual(testArray, [ , 4, 9]);
swap(testArray, 0, 2);
Program.assertEqual(testArray, [4, 9, 7]);(6 votes)
var swap = function(array, firstIndex, secondIndex) {
var temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
};
var testArray = [7, 9, 4];
swap(testArray, 0, 1);
println(testArray);
Program.assertEqual(testArray, [9, 7, 4]);
swap(testArray, 1, 2);
Program.assertEqual(testArray, [9, 4, 7]);
swap(testArray, 0, 2);
Program.assertEqual(testArray, [7 , 4, 9]);
I don't want to give you the answer, but this code worked. It has to do with identifying the array index and then replacing them in the second part to the corresponding values. If that doesn't make sense, keep looking, and break the code into parts. Look at the first
swap, and compare it with program assertion. You have to remember the goal is to act like a swapping program, you are swapping values and checking to see if they match the correct position.(3 votes)
- Why were there smaller numbers on the bottom of the cards like the card number 2 had a little 5 underneath it? Maybe you had the same question.(2 votes)
@clindsey737 I'm pretty sure the numbers underneath the cards showed the position of the card within the array. Javascript arrays start at 0, and go upward from there, and so do these cards.
You can find out more here:
https://www.khanacademy.org/computing/computer-programming/programming/arrays/pt/intro-to-arrays
Hope this helps!(5 votes)
in the challenge problem why this code is not working ??
var swap = function(array, firstIndex, secondIndex) {
array[firstIndex] = array[secondIndex];
array[secondIndex] = array[firstIndex];
};
it all seems to be reasonable so why it is not working ?(2 votes)
The code above will write over the value in the first index with the value at the second index. So, when you try to copy the value from the first index into the second index, it is no longer contains the original value. So, you end up with two copies of the value that was in the second index.
You need to store the value from the first index into a variable before you overwrite it, so that you can use it to copy into the second index. Have a look at the hint code provided in the challenge.(4 votes)
I am confused you asked us to sort but I can't drag any numbers.(1 vote)- You're not supposed to drag, you're suppose to swap.
"You can swap any pair of cards by clicking on one card, and then the other."(3 votes)
- Question is about Selection sort pseudocode. I see the problem, I've changed the program to fix it, I've removed the characters in front of the last line to uncomment it. I don't know how to make it run. Where's the go button? Nothing else on the page that I've found seems to make it run.(2 votes)
Hi!
Just out of curiosity, why does everything in the next challenge have to be in a specific order? After I finished step one, I tried doing temp = array[secondIndex] instead of array[secondIndex] = temp for fun and it didn't work. Can someone please explain?
Thanks!(1 vote)
In JavaScript, the equals sign, "=", is used for assignment. When you typetemp = array[secondIndex];, you are assigning that value in the array to the variabletemp. If you try it the other way, then you will be assigning the value oftempto that position in the array.
The later is desired because it modifies the array. The former only reads the array. Does that help?(3 votes)
- just wondering if anyone found an algorithmic way to order those cards in the example without moving a card more than once?(2 votes)
- No algorithm can be guaranteed to do it if you use swaps. e.g. If I have 2,3,1 it requires at least two swaps to sort it. But each swap involves 2 numbers. Which means 2 * 2 = 4 numbers were moved. Since 4 > 3, at least one number must be moved twice.
However, you can do it with a cycle sort:
https://en.wikipedia.org/wiki/Cycle_sort
The cycle sort doesn't swap the cards, instead it puts the card in the position it would appear in if the cards were sorted, and repeats that with the card currently sitting in that position. Eventually, all of the cards in the cycle will be in their sorted position by only moving them once. If you repeat that for all the cycles, the cards will be sorted.(1 vote)
In the "Challenge:implement swap", I am able to run the code. However, when I try to run the code, a square comes up saying "waiting for the code to run." and it goes on forever. Please help.
- How should we run the code? Just by refreshing the screen (that worked for first challenge!) ? or any other way?
- What are the purpose of the next 2 steps? Just to verify swapping or to get the aray [9, 7, 4]? Thanks :)(1 vote)
The checker on all of these CS exercises is pretty terrible. You aren't necessarily doing anything wrong.(2 votes)
var swap = function(array, firstIndex, secondIndex) {
var temp = array.slice();
array[firstIndex] = temp[secondIndex];
array[secondIndex] = temp[firstIndex];
};
I think this solution would be nicer? I could swap more then only two numbers with this function(1 vote)- Making a copy of the array with slice, would make the algorithm much slower, O(n), compared to the regular algorithm, which is O(1). This would make it unacceptable for most algorithms that wanted to use swap.(2 votes)