Select sort

Select sort Algorithm, time complexity and Example

Selection sort (Selection sort) is a simple and intuitive sorting algorithm. It works by selecting the smallest (or largest) element from the data elements to be sorted for the first time, storing it at the beginning of the sequence, and then finding the smallest (large) element from the remaining unsorted elements The element is then placed at the end of the sorted sequence. And so on, until the number of all data elements to be sorted is zero. Selection sorting is an unstable sorting method.

Algorithm ideas:

• Use linear to find the current data to be sorted to find the minimum value
• Move the minimum value to the left of the array
• Repeat steps 1 and 2 until the array is all sorted

method 1:

Use recursive implementation, a loop is easier to read, easy to understand, but the efficiency is lower than the loop

const unsort = [6, 1, 7, 8, 9, 3, 5, 4, 2]

const selectedSort = (arr, index = 0) => { 
    let min = arr[index]

    const len = arr.length

    for (let i = index; i < len; i++) {
        const temp = arr[i]
        if (temp < min) {
            arr[index] = temp
            arr[i] = min
            min = temp
        }
    }

    if (index === len - 1) {
        return arr
    }
    return selectedSort(arr, index + 1)
}

const sorted = selectedSort(unsort)

console.log(sorted)

// console: [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

Method 2:

Use loop to achieve, two loops, it is not easy to read, the logic is prone to leaks, the efficiency is higher than recursion

const unsort = [6, 1, 7, 8, 9, 3, 5, 4, 2]

const selectedSort = (arr) => {
    const len = arr.length
    let min
    let temp
    for (let i = 0; i < len; i++) {
        min = arr[i]
        temp
        for (let j = i + 1; j < len; j++) {
            if (arr[j] < min) {
                temp = min
                min = arr[j]
                arr[j] = temp
                arr[i] = min
            }
        }
    }
    return arr
}

const sorted = selectedSort(unsort)

console.log(sorted)

// console: [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

understanding the complexity:

The selection sort uses a linear method to find the minimum value, so each cycle will compare n-m(m is the number of cycles), until the last round only compare a number, so the complexity is (n-1) + (n-2) + (n-3) ... + 1 ≈ n 2 / 2, O(n 2 ) after ignoring non-important items