Selection sort algorithm

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²) 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

• 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