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
- itertate from 0 to len(arr) - 1
- seting to minimunIdx variable the first element index in the unsorted part
- loop trough the unsorted part
- if arr[j] < arr[minimumIdx] => minimumIdx = j
- 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
- https://www.geeksforgeeks.org/python-program-for-selection-sort/
- https://www.programiz.com/dsa/selection-sort
- https://stackoverflow.com/questions/22898928/selection-sort-in-javascript
- https://www.youtube.com/watch?v=EnodMqJuQEo
- https://www.geeksforgeeks.org/selection-sort/
- https://www.youtube.com/watch?v=xWBP4lzkoyM
Have a good day :)
#day_10
Top comments (0)