DEV Community

Tatyana Celovsky
Tatyana Celovsky

Posted on • Originally published at tatyanacelovsky.com on

Algorithm Series - Selection Sort

Multicolored pencils are laying flat on a light background. The pencils are not aligned, with some of them appearing to be longer than others. Photo by Jess Bailey on Unsplash

This is a quick tutorial on the selection sort algorithm and its implementation in Javascript.

What is Selection Sort Algorithm

Selection sort is a sorting algorithm that divides the input list into two parts: a sorted sublist that is built up from left to right and a sublist of the remaining unsorted values. The sorted sublist is placed at the front (to the left of) the unsorted sublist. Initially, the sorted sublist is empty and the unsorted sublist consists of the entire input list. The algorithm selects the smallest (or largest, depending on the ask) element in the unsorted sublist, places that element at the beginning of the unsorted sublist and moves the sublist boundary one element to the right (because there is now one element present in the sorted sublist, while the unsorted sublist became smaller by one element).

Let’s take a look at selection sort when trying to sort the elements of an array in an ascending order:

  1. Set the first element of the array as minimum;
  2. Compare minimum with the second element, if the second element is smaller than minimum, assign the second element as minimum , otherwise, do nothing;
  3. Compare minimum with the following element, if that element is smaller than minimum, then assign minimum to that element, otherwise do nothing;
  4. Continue step 3 above until the last element has been reached;
  5. Move minimum to the front of the array and move the sublist boundary one element to the right (because there is now one element present in the sorted sublist, while the unsorted sublist became smaller by one element);
  6. Continue with steps 3 - 5, until all elements are in their sorted positions.

The array is sorted when all the unsorted elements are placed in their correct positions.

Selection Sort Code in Javascript

Let’s take a look at the code for the selection sort algorithm described above (ascending order):

function selectionSort(array) {
for (let i = 0; i < array.length - 1; i++) { // for loop iterates through each item in the array, stopping with the second to last item. This is because in the next loop we will compare `i` to its neighbor `i + 1` in the array, therefore, we have to stop this initial loop one index short of the full array length;
let minimum=i; // set the first element as `minimum`;
for (let j = i + 1; j < array.length; j++) { // for loop iterates through each item in the unsorted sublist;
if (array[j] < array[minimum]) { // if statement checks whether the following element of the unsorted sublist is smaller than the current `minimum`;;
minimum=j; // if it is, assign `minimum` to that element ; otherwise, do nothing;
}
}
[array[i], array[minimum]] = [array[minimum], array[i]]; // move `minimum` to the end of the sorted sublist;
}
return array; // return the now sorted array.
}

The above code sorts the array in ascending order. To sort an array in descending order, replace the “greater than” sign in the if statement with a “less than” sign.

Selection Sort and Big-O

Selection Sort compares the adjacent elements, hence, the number of comparisons is:

(n-1) + (n-2) + (n-3) +…..+ 1 = n(n-1)/2

This nearly equals to n2, therefore Big-O is O(n²) or quadratic time. We can also deduce this from observing the code: selection sort requires two loops, therefore Big-O is expected to be O(n²).

Conclusion

Selection sort finds the lowest value of the array and moves that value to the beginning of the array, it then proceeds to look for the next lowest value and moves that in front of the unsorted elements. This continues until all values of the array have been sorted; it is a simple way to sort a list when complexity does not matter and the list that needs sorting is short.

Resources

Selection Sort Algorithm gist

Let’s Talk About Big-O

Heroku

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs