정렬 (Sort) - 선택정렬

선택정렬이란

선택정렬(Selection Sort)은 비교 기반의 정렬 알고리즘 중 하나로, 다음과 같은 절차를 통해 배열을 정렬.

1. 주어진 리스트 중에서 최솟값을 찾음.
2. 그 최솟값을 리스트의 맨 앞에 위치한 값과 교환.
3. 맨 앞의 값을 제외한 나머지 리스트를 같은 방법으로 정렬.
4. 이 과정을 통해 리스트가 정렬될 때까지 반복.

선택정렬 요약

특징	비교 기반의 정렬 알고리즘으로, 리스트에서 최솟값을 반복적으로 선택하여 정렬
장점	1. 구현이 간단하고 이해하기 쉬움 2. 작은 크기의 리스트에 대해 효율적으로 작동할 수 있음
단점	1. 시간복잡도가 O(n^2)로, 큰 데이터셋에서는 비효율적 2. 안정적인 정렬 알고리즘이 아님.
시간복잡도	O(n^2)

 

자바스크립트 예시

function selectionSort(arr) {
    const n = arr.length;
    
    for(let i = 0; i < n-1; i++) {
        let minIndex = i;
        
        for(let j = i + 1; j < n; j++) {
            if(arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        if(minIndex !== i) {
            let temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
    
    return arr;
}