Learn all about selection sort and its intuitive, almost human-like, approach for sorting values.

If you are just getting started with understanding sorting algorithms, selection sort is a great starting point because it’s simple and intuitive. It doesn't require any complex data structures. The sorting logic is straightforward as well: the algorithm works by repeatedly finding the smallest (or largest) element from the unsorted part of a collection and moving it to a sorted part.

All of this makes selection sort something that is easy to understand and visualize:

In the following sections, we'll learn all about how selection sort works, look at its implementation, and wrap things up by looking at its (slow) performance characteristics.

Onwards!

How Selection Sort Works

The way selection sort works is largely given away in its name. Selection sort is named for its approach of repeatedly selecting the smallest (or largest, depending on the sorting order) element from an unsorted portion of a collection (list, array, linked list, etc.) and moving it to its correct position. That sounds a bit too...simplistc, so let's walk through the ins and outs of how selection sort works by looking at two common variations.

Two Collection Variation

We are going to start with the easiest of the selection sort variations, and that is the one where we have two collections. One collection will be our original unsorted input. The other collection will be our sorted output:

Initially, our sorted collection will be empty. This is because we haven't done any type of sorting. All of our values are currently in their unsorted state as part of the unsorted collection. To go from where we are now to having a fully sorted collection of values, we need to follow these steps:

1. Select: Find the smallest (or largest) element in the unsorted collection
2. Move: Remove this element from the unsorted collection and add it to our sorted collection
3. Repeat: Repeat the process for the remaining unsorted items until all elements are moved into the sorted collection

This means, our first step will be to find the smallest item in our unsorted collection:

That would be the 1 value. What we do next is remove our 1 value from the unsorted collection and move it into the sorted collection:

This marks one full iteration of our selection sort algorithm where we found the smallest number from our unsorted collection and moved it into our sorted collection. It's time to repeat the process. When go back to our unsorted collection, we look for the current smallest number:

That would be the 8 value, and we now move it into our sorted collection at the end:

At this point, we have two sorted values figured out: 1 and 8. At this point, we can see how the remaining unsorted numbers will find themselves sorted. We will keep finding the smallest unsorted value and moving it into the end of our sorted collection. We will keep repeating this process until we have run out of unsorted numbers. The final result will look something like this:

This two collection variation is great for explaining how selection sort works. With proper implementation, it can also be great from a performance and memory point of view, which we'll cover in detail later. Because the performance is so sensitive to how we implement our collections, this variation isn't used in practice often. That brings us to...

Single Collection Variation

The most popular selection sort variation we'll encounter (and likely use) is the single collection variation. When people refer to selection sort, they are talking about this variation. This single collection variation shares a lot of similarities with the two collection variation we saw earlier. The biggest difference is that, instead of having one unsorted collection and another sorted collection, both unsorted and sorted values are divided up and arranged in the same single collection itself.

Let's drive all of this home by looking at an example. Our starting point is going to be a collection of unsorted values:

At this point, everything in our collection is considered to be unsorted. We will go one step further and mark our entire collection as being part of an unsorted region:

To sort these values, this selection sort variation will follow these steps:

1. Select: Find the smallest (or largest) element in the unsorted portion of the collection
2. Swap: Swap this element with the first element of the unsorted region, effectively growing the sorted portion of the collection by one element.
3. Repeat: Repeat the process for the remaining unsorted region of the collection until all elements are sorted.

To put these (sorta confusing) steps into practice, the first thing we are going to do is find the smallest value in our unsorted region:

In our case, this smallest value will be 3. With our 3 value selected, we swap it the first item in our unsorted region:

What we have just done is taken the smallest value from our unsorted region and placed it at the beginning of our unsorted collection. This smallest item is in its correct sorted position. To recognize this, we will divide our collection into a sorted region and an unsorted region:

From here, we repeat our steps from earlier. We now look for the smallest item in our unsorted region:

This time, the smallest value is 10. Just like before, we now swap our 10 value with the first item from our unsorted region:

After we make the swap, we also adjust the boundaries of our sorted and unsorted regions to account for there being two sorted values:

At this point, our sorted region has two values: 3 and 10. There are a lot more unsorted values left, so we continue on. We select the smallest value from our unsorted region:

We then swap it with the first unsorted item, leading to an arrangement that looks as follows:

At this point, you probably get the gist of how selection sort works in this variation. Let's quickly go through the remaining unsorted items from our example:

As we can see, this process of finding the smallest item and swapping it with our first item in our unsorted region is pretty effective in helping us get to a fully sorted collection. Let's go even faster and finish up the remaining steps for getting a fully sorted collection:

At the end of all of this, once the last step once selection has run to completion, will be left with only our sorted region and a fully sorted collection of items.

Performance and Memory

Selection sort isn't a fast algorithm for sorting your data. Because we pick an unsorted item and compare it against every single other unsorted item to see what is the smallest unsorted value, we are doing a whole bunch of comparisons at every iteration:

All of this iteration results in selection sort having a running time of O(n²) time. That is not a stellar place to be!

From a memory point of view, though, selection sort is quite good. It doesn't take up much memory beyond any extra objects we need for storing the input itself. That shouldn't be too surprising because, in the popular single collection variation, almost all of our sorting-related shenanigans are done in-place on the unsorted collection itself.

The following table summarizes the performance and memory characteristics

Scenario	Time Complexity	Memory Complexity
Best case	O(n2)	O(1)
Worst case	O(n2)	O(1)
Average case	O(n2)	O(1)

When we look at our two collection variation, the above results change a bit:

Scenario	Time Complexity	Memory Complexity
Best case	O(n2)	O(n)
Worst case	O(n2)	O(n)
Average case	O(n2)	O(n)

Because we have two collections, the amount of memory we need to use to perform the various sorting operations does grow linearly.

While performance remains unchanged, a subtle detail has to do with the data structure we use for storing our collection. Because we will be frequently removing items from the middle of the collection, a strict data structure like an array will be slower than using something like a linked list. This has to do with how arrays require all items to be represented in continuous regions of memory. If you'd like to learn more about arrays and memory, our Arrays data structure article goes into greater detail.

The JavaScript Implementation

We are almost done here. The last thing is for us to look at selection sort (the single collection variation) implemented in JavaScript:

function selectionSort(input) {
  for (let i = 0; i < input.length; i++) {
    // assume the item in the first position is the smallest
    let smallestPosition = i;

    // go through the unsorted region
    for (let j = i + 1; j < input.length; j++) {
      if (input[j] < input[smallestPosition]) {
        // a new smallest number is found
        smallestPosition = j;
      }
    }

    // swap the min value if it changed
    if (smallestPosition != i) {
      let temp = input[smallestPosition];
      input[smallestPosition] = input[i];
      input[i] = temp;
    }
  }
}

let myinput = [24, 10, 17, 9, 5, 9, 1, 23, 300];
selectionSort(myinput);

console.log(myinput);

The JavaScript doesn't veer too far from the English description we saw in the previous section.

Now, for completeness, you may also want to know what the two collection version of selection sort looks like, and that is as follows:

function selectionSortTwoCollection(input) {
  let sortedArray = [];

  while (input.length > 0) {
    // Find the index of the minimum element in the unsorted array
    let minIndex = 0;
    for (let i = 1; i < input.length; i++) {
      if (input[i] < input[minIndex]) {
        minIndex = i;
      }
    }

    // Remove the minimum element from the unsorted array and add it to the sorted array
    sortedArray.push(input.splice(minIndex, 1)[0]);
  }

  return sortedArray;
}

let myinput = [24, 10, 17, 9, 5, 9, 1, 23, 300];
let sortedArray = selectionSortTwoCollection(myinput);

console.log(sortedArray);

Notice in this variation we create a new array called sortedArray where the smallest value from our original unsorted collection is moved into.

Conclusion

Selection sort makes up the large number of sorts that is easy to understand but not very fast. To see how selection sort compares with other sort algorithms, check out the following table:

Name	Running Time	Memory
Quicksort	O(n log n)	O(log n)
Mergesort	O(n log n)	O(n)
Heapsort	O(n log n)	O(1)
Timsort	O(n log n)	O(n)
Bubble sort	O(n2)	O(1)
Selection sort	O(n2)	O(1)
Insertion sort	O(n2)	O(1)
Counting sort	O(n + k)	O(n + k)
Radix sort	O(d ⋅ (n + k))	O(n + k)

You can find a more detailed comparison of these sorting algorithms as well as many others over on the Wikipedia section fully dedicated to this. If I were you and looking for a slow sort alogirthm that is easy to implement, I would probably choose insertion sort over selection sort any day of the week.

Just a final word before we wrap up. What you've seen here is freshly baked content without added preservatives, artificial intelligence, ads, and algorithm-driven doodads. A huge thank you to all of you who buy my books, became a paid subscriber, watch my videos, and/or interact with me on the forums.

Your support keeps this site going! 😇