DEV Community is a community of 674,199 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Selection sort algorithm

Aya Bouchiha
Full stack web developer

Definition of selection sort

Selection sort is one of the simplest sorting algorithms, it works by continually finding the minimum number in the array and inserting it at the beginning.

Space and Time complexity

The time complexity of selection sort is O(n2) and it's space complexity is O(1)

Selection sort algorithm

1. itertate from 0 to len(arr) - 1
2. seting to minimunIdx variable the first element index in the unsorted part
3. loop trough the unsorted part
4. if arr[j] < arr[minimumIdx] => minimumIdx = j
5. swaping arr[minimumIdx] with the first in the unsorted part (unsortedPart[0])

Implementation of selection sort using python

``````def selectionSortAlgorithm(arr: list) -> list:
"""
[ name ] => Selecion sort
[ type ] => Sorting algorithms
[ time complexity ] => O(n^2)
[ space complexity ] => O(1)
[ params ] => ( arr {list} array to sort )
[ return ] => sorted list
[ logic ]  => (
1. itertate from 0 to len(arr) - 1
2. seting to minimunIdx variable the first element index in the unsorted part
3. loop trough the unsorted part
4. if arr[j] < arr[minimumIdx]  => minimumIdx = j
5. swaping arr[minimumIdx] with the first in the unsorted part (unsortedPart[0])
)
"""
# itertate from 0 to len(arr) - 1
for i in range(len(arr)):
# setting to minimunIdx variable the first element index in the unsorted part
minIdx = i
# loop trough the unsorted part
for j in range(i + 1, len(arr)):
# if arr[j] < currentMinimum (arr[minIdx])
if arr[j] < arr[minIdx]:
# minIdx will be the index of the new minimum
minIdx = j
# swaping the minimum with the first element in the unsorted part
arr[minIdx], arr[i] = arr[i], arr[minIdx]
return arr

``````

Implementation of selection sort using javascript

``````/**
* sort an array using selection sort algorithm
* time complexity : O(n^2)
* space complexity : O(1)
* @param {Array} arr  array to sort
* @returns {Array} sorted array
*/
const SelectionSortAlgorithm = (arr) => {
// iterate from 0 to arr.length - 1
for (let i = 0; i < arr.length; i++){
//  setting to minimunIdx variable the first element index in the unsorted part
var minIdx = i;
//  loop trough the unsorted part
for (let j = i + 1; j < arr.length; j++) {
//  if arr[j] < currentMinimum (arr[minIdx])
if (arr[j] < arr[minIdx]) {
// minIdx will be the index of the new minimum
minIdx = j;
}
}
// swaping the minimum with the first element in the unsorted part
[arr[minIdx], arr[i]] = [arr[i], arr[minIdx]];
}
return arr
}
``````

Exercise

sort an array in descending order using the selection sort algorithm

References and useful resources

Have a good day :)
#day_10