Table of Contents

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!

The way * selection sort* works is largely given away in its name. Selection sort is named for its approach of repeatedly

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:

**Select**: Find the smallest (or largest) element in the unsorted collection**Move**: Remove this element from the unsorted collection and add it to our sorted collection**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...

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

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:

**Select**: Find the smallest (or largest) element in the unsorted portion of the collection**Swap**: Swap this element with the first element of the unsorted region, effectively growing the sorted portion of the collection by one element.**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.

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 ^{2}) 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(n^{2}) |
O(1) |

Worst case | O(n^{2}) |
O(1) |

Average case | O(n^{2}) |
O(1) |

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

Scenario | Time Complexity | Memory Complexity |
---|---|---|

Best case | O(n^{2}) |
O(n) |

Worst case | O(n^{2}) |
O(n) |

Average case | O(n^{2}) |
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.

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.

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(n^{2}) |
O(1) |

Selection sort | O(n^{2}) |
O(1) |

Insertion sort | O(n^{2}) |
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. If you have a question and/or want to be part of a **friendly**, **collaborative** community of over 220k other developers like yourself, post on the forums for a quick response!

:: Copyright KIRUPA 2024 //--