繼 Insertion Sort 後，今天要介紹的是 Selection Sort

Selection Sort

Selection sort is a comparison-based sorting algorithm that works by repeatly selecting the smallest(or largest)element from the unsorted portion of the dataset and moving it to the correct position.

The algorithm sorts the list by iterating through the dataset, finding the minimum (maximum) value in each pass, and swapping it with the first unsorted element.This process continues untill all elements are sorted.

selection sort 在每一輪中會選出 dataset 內『最小/最大的值』，將該值與 dataset 中還未排序的部分中開頭的元素交換位置，每一輪結束後未排序的範圍會越縮越小，直到 dataset 內所有元素都被排序完畢

Steps of selection sort

這裡用 小 => 大 排序做說明

1. Selection 從未排序的部分中選出最小值
   Identify the the smallest value in the unsorted portion of the dataset.
2. Swap 將最小值與未排序部分的首項交換位置
   Swap the smallest value with the first unsorted element.
3. Move 首項確認已排序好(未排序的範圍減一)，移動到下一個未排序的部分，並重複 step1~step3
   Mark the beginning of the dataset as sorted, and reduce the range of unsorted elements by 1.
4. End 當所有元素都被排序好，selection sort 則結束
   Repeat the process untill entire array is fully sorted.

Complexity of selection sort

O(n^2)

Implementation of selection sort

let unsortedArr = [13 ,8, 3, 6, 5, 7, 1, 18, 12, 9, 2, 4];

function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let startIndex = i;
        // pick out the smallest value
        for (let j = startIndex + 1; j < arr.length; j++) {
            // if the smallest value is smaller than arr[startIndex], do swap
            if (arr[j] < arr[startIndex]) {
                [arr[j], arr[startIndex]] = [arr[startIndex], arr[j]];
            }
        }
    }
    return arr;
}

console.log(selectionSort(unsortedArr)); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 18]

相關資源

selection sort algorithm
https://www.geeksforgeeks.org/selection-sort-algorithm-2/
selection sort
https://big-o.io/algorithms/comparison/selection-sort/
selection sort and insertion sort #
https://www.youtube.com/watch?v=mVpxeSoEW5E