Selection sort algorithm 
Tags: algorithms, computerscience, beginners, python
Published: 2021-06-22 23:21:37


## 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(n<sup>2</sup>)** 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

```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
````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.geeksforgeeks.org/python-program-for-selection-sort/)
+ [https://www.programiz.com/dsa/selection-sort](https://www.programiz.com/dsa/selection-sort)
+ [https://stackoverflow.com/questions/22898928/selection-sort-in-javascript](https://stackoverflow.com/questions/22898928/selection-sort-in-javascript)
+ [https://www.youtube.com/watch?v=EnodMqJuQEo](https://www.youtube.com/watch?v=EnodMqJuQEo)
+ [https://www.geeksforgeeks.org/selection-sort/](https://www.geeksforgeeks.org/selection-sort/)
+ [https://www.youtube.com/watch?v=xWBP4lzkoyM](https://www.youtube.com/watch?v=xWBP4lzkoyM)

Have a good day :)
\#day_10