Main content

### Course: Computer science theory > Unit 1

Lesson 4: Selection sort# Sorting

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)

- 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 ?(3 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.(6 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!(3 votes)- In JavaScript, the equals sign, "=", is used for assignment. When you type
`temp = array[secondIndex];`

, you are assigning that value in the array to the variable`temp`

. If you try it the other way, then you will be assigning the value of`temp`

to that position in the array.

The later is desired because it modifies the array. The former only reads the array. Does that help?(5 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)

- I am confused you asked us to sort but I can't drag any numbers.(2 votes)
- 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."(4 votes)

- just wondering if anyone found an algorithmic way to order those cards in the example without moving a card more than once?(3 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.(2 votes)

- I used the strategy of sorting by finding the smallest value each time, excluding the previous small value.(2 votes)
- What happens if two values in your list have the same value ?

Could you sort [3,1,3,4,3,2,3,5] using that technique ?(2 votes)

- by putting them from least to greatest(2 votes)

- can you sort in any way that is not least to greatest?(2 votes)
- You can sort in any way you want as long as you can take two elements and compare them. Comparing means taking two element and saying which element is more X than the other.

e.g.

-If I compare elements to say which element is**larger**than the other, I get the standard least to greatest sort.

-If I compare elements to say which element is**smaller**than the other, I get a greatest to least sort.

-If I compare elements to say which element has**the largest absolute value**, I get elements sorted by least to greatest magnitude (value ignoring the sign).(2 votes)