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 complexi…


This content originally appeared on DEV Community and was authored by Aya Bouchiha

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_9


This content originally appeared on DEV Community and was authored by Aya Bouchiha


Print Share Comment Cite Upload Translate Updates
APA

Aya Bouchiha | Sciencx (2021-06-22T23:21:37+00:00) Selection sort algorithm. Retrieved from https://www.scien.cx/2021/06/22/selection-sort-algorithm/

MLA
" » Selection sort algorithm." Aya Bouchiha | Sciencx - Tuesday June 22, 2021, https://www.scien.cx/2021/06/22/selection-sort-algorithm/
HARVARD
Aya Bouchiha | Sciencx Tuesday June 22, 2021 » Selection sort algorithm., viewed ,<https://www.scien.cx/2021/06/22/selection-sort-algorithm/>
VANCOUVER
Aya Bouchiha | Sciencx - » Selection sort algorithm. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2021/06/22/selection-sort-algorithm/
CHICAGO
" » Selection sort algorithm." Aya Bouchiha | Sciencx - Accessed . https://www.scien.cx/2021/06/22/selection-sort-algorithm/
IEEE
" » Selection sort algorithm." Aya Bouchiha | Sciencx [Online]. Available: https://www.scien.cx/2021/06/22/selection-sort-algorithm/. [Accessed: ]
rf:citation
» Selection sort algorithm | Aya Bouchiha | Sciencx | https://www.scien.cx/2021/06/22/selection-sort-algorithm/ |

Please log in to upload a file.




There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.