JavaScript Algorithms: Select Sort

If you haven’t already done so, I strongly encourage you to read my post on Bubble Sort first as this post builds upon the principles discussed therein 😊

Select Sort is similar to Bubble Sort except instead of swapping each time a change is found, it first determines which element is best suited to swap. As a result, the maximum times a swap would ever be needed is only whatever the length of the array is.

How does it work?

I’m glad you asked. Let me tell you! Say you have a list…

[10,9,8,7,6,5,4,3,2,1]

… and you want to sort it so it starts with 1 and ends with 10. With Select Sort you would start at the beginning of the list and compare the first item against all the other items in the list. Each time an item which is less than the first item is found, we remember that item and continue comparing the rest of list against it instead of the first item. So for example, using the above array, the steps needed to arrive at the first swap would look like this:

10 => 9,8,7,6,5,4,3,2,1
10 is greater than 9
9 => 9,8,7,6,5,4,3,2,1
9 is greater than 8
8 => 9,8,7,6,5,4,3,2,1
8 is greater than 7
7 => 9,8,7,6,5,4,3,2,1
7 is greater than 6
6 => 9,8,7,6,5,4,3,2,1
6 is greater than 5
5 => 9,8,7,6,5,4,3,2,1
5 is greater than 4
4 => 9,8,7,6,5,4,3,2,1
4 is greater than 3
3 => 9,8,7,6,5,4,3,2,1
3 is greater than 2
2 => 9,8,7,6,5,4,3,2,1
2 is greater than 1
Should swap 10 and 1
EXECUTE SWAP:
[ 1, 9, 8, 7, 6, 5, 4, 3, 2, 10 ]

Got it? Good. Now we start over again. Except this time because we know for sure that the first item is the smallest item in the list, instead of starting with the first item, we start with the second item:

9 => 8,7,6,5,4,3,2,10
9 is greater than 8
8 => 8,7,6,5,4,3,2,10
8 is greater than 7
7 => 8,7,6,5,4,3,2,10
7 is greater than 6
6 => 8,7,6,5,4,3,2,10
6 is greater than 5
5 => 8,7,6,5,4,3,2,10
5 is greater than 4
4 => 8,7,6,5,4,3,2,10
4 is greater than 3
3 => 8,7,6,5,4,3,2,10
3 is greater than 2
2 => 8,7,6,5,4,3,2,10

Should swap 9 and 2

EXECUTE SWAP:
[ 1, 2, 8, 7, 6, 5, 4, 3, 9, 10 ]

So the first two items in the list (1,2)are now sorted. How do we sort the rest? You guessed it, increment to the next item and compare it against the rest of the list, then rinse and repeat until you ain’t got nothing left to compare:

8 => 7,6,5,4,3,9,10
8 is greater than 7
7 => 7,6,5,4,3,9,10
7 is greater than 6
6 => 7,6,5,4,3,9,10
6 is greater than 5
5 => 7,6,5,4,3,9,10
5 is greater than 4
4 => 7,6,5,4,3,9,10
4 is greater than 3
3 => 7,6,5,4,3,9,10
3 => 7,6,5,4,3,9,10

Should swap 8 and 3

EXECUTE SWAP:
[ 1, 2, 3, 7, 6, 5, 4, 8, 9, 10 ] 
-------------------------------------
7 => 6,5,4,8,9,10
7 is greater than 6
6 => 6,5,4,8,9,10
6 is greater than 5
5 => 6,5,4,8,9,10
5 is greater than 4
4 => 6,5,4,8,9,10
4 => 6,5,4,8,9,10
4 => 6,5,4,8,9,10

Should swap 7 and 4

EXECUTE SWAP:
[ 1, 2, 3, 4, 6, 5, 7, 8, 9, 10 ] 
-------------------------------------
6 => 5,7,8,9,10
6 is greater than 5
5 => 5,7,8,9,10
5 => 5,7,8,9,10
5 => 5,7,8,9,10
5 => 5,7,8,9,10

Should swap 6 and 5

EXECUTE SWAP:
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
-------------------------------------

6 => 7,8,9,10
6 => 7,8,9,10
6 => 7,8,9,10
6 => 7,8,9,10

NO SWAP FOUND
-------------------------------------

7 => 8,9,10
7 => 8,9,10
7 => 8,9,10

NO SWAP FOUND
-------------------------------------

8 => 9,10
8 => 9,10

NO SWAP FOUND
-------------------------------------

9 => 10

NO SWAP FOUND

Hopefully that make sense. Notice that halfway through the sort process (when 5 and 6 swap), the rest of the list has already sorted itself. You might be tempted to think this is something that always happens in Select Sort. Sadly you would be wrong ☹️. Just because a swap isn’t found at any point, doesn’t mean there won’t be a swap found at a later point. For example say you want to sort this list:

[7,10,9,8]

The first time you iterate through it, the following will happen:

7 => 10,9,8
7 => 10,9,8
7 => 10,9,8,

NO SWAP FOUND

This doesn’t mean the rest of the list is ordered. It’s not. All it means is that 7 is in the right place. 7 doesn’t need to move.

To illustrate the point, let’s advance to the next item in the list (10):

10 => 9,8
10 is greater than 9
9 => 9,8
9 is greater than 8

Should swap 10 and 8

EXECUTE SWAP:
[ 7, 8, 9, 10 ]

This is different from Bubble Sort. In Bubble Sort if you go through one iteration without needing to execute a swap, you know that the list is sorted because each iteration is actively looking to see if the list is ordered. Select Sort is different. Each iteration is only looking to see if the element in the current position should swap with another element. In other words, each iteration only concerns itself with whether the current element is the smallest possible element for that particular position in the list.

Let’s do it in JavaScript!

To make things simple, I’m going to start where we left off when we talked about Bubble Sort. That way you can see the similarities and differences between the two methods.

Here is Bubble Sort:

const bubbleSort = (array) => {
  for (let i = 0; i < array.length; i++) {
    for (let x = 0; x < array.length - 1 - i; x++) {
      if (array[x] > array[x + 1]) {
        [array[x], array[x + 1]] = [array[x + 1], array[x]];
      }
    }
  }
  return array;
}

Ta-da! Okay so lets convert this to Select Sort.

const selectionSort = (array) => {
  for (let i = 0; i < array.length; i++) {
    let min = i;
    for (let x = i + 1; x < array.length; x++) {
      if (array[min] > array[x]) min = x;
    }
    if (i !== min) [array[i], array[min]] = [array[min], array[i]];
  }
  return array;
}

Ta-da! So what changed? Well, the two methods actually have more similarities than they do differences.

• Both use nested for loops.
• Both concern themselves with only the part of the list which has not yet been ordered.

And the differences:

• Bubble Sort makes swaps within the inner for loop each time it encounters disorder. The inner for loop’s job in Select Sort is to determine which element is best suited for whatever particular index the outer for loop gives it. The inner for loop makes no swaps. It only determines which element is best suited to be swapped.
• Bubble Sort can determine whether order has been achieved at any point after a termination of the inner for loop. Select Sort cannot.

So what’s going on here?

Taking the function step by step:

1. Outer for loop sets i to 0.
2. min gets set to i.
3. Inner for loop starts at i + 1.
4. It looks to see if the element at index min is greater than the element at index x. That is, if the first element in the array (or whatever min happens to be) is greater than the second element in the array (or whatever x happens to be).
5. If it is, the value from x get passed into min.
6. The inner loop iterates again and x increments to the next index.
7. Step 4, 5 and 6 repeat until all the indices have been looked at and min has been set to the index of the smallest possible value. At this point, the inner for loop terminates and we return to the outer for loop.
8. Next we check to see if a swap is even necessary (if (i !== min)). If it is, we swap the item at index i with a smaller item at index min.
9. The outer for loop iterates and i increments to the next index.
10. Steps 1 through 9 repeat until the outer for loop terminates.
11. Return the sorted list.

… and that’s how it’s done!

Solution

So I already gave the solution, but here it is again in color (and with parameter validation)!