[Data Structure] Selction Sorting

Selection Sort

정렬 방법

• 가장 작은 요소를 찾고, 첫번째 위치에 지정. 범위 (0 ~ length)
• 가장 작은 요소를 찾고, 두번째 위치에 지정. 범위 (1 ~ length)
• 같은 방식으로 마지막 요소까지 진행

 

Time Complex

• 항상 quadratic in n
• not stable
• in-place sort
• worst space (n) is constant

function sortBySelection(nums: number[]) {
    for (let i = 0; i < nums.length - 1; i++) {
        let pos = i
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[pos] > nums[j]) { // find the smallest value and position
                pos = j
            }
        }
        const tmp = nums[i]
        nums[i] = nums[pos]
        nums[pos] = tmp
    }
    console.log(nums) // [2, 3, 4, 5, 6] 
}

sortBySelection([6, 3, 2, 5, 4])