[알고리즘] 선택정렬(Selection sort)

선택정렬(Selection sort)?

선택정렬(Selection sort)은 비교 기반 정렬 알고리즘 중 하나로,

주어진 리스트에서 가장 작은(또는 가장 큰) 값을 찾아 이를 정렬된 부분과 교환하는 과정을 반복하여 전체 리스트를 정렬한다.

 

선택정렬의 장점은 구현이 매우 쉽고, 이해하기 쉬운 알고리즘이라는 점이다.
제자리 정렬(추가적인 메모리 공간을 사용하지 않고, 원래 리스트 내에서 정렬을 수행)이므로 추가적인 메모리를 거의 사용하지 않는 특징을 가지고 있다.

 

선택정렬은 시간 복잡도가 O(n²)으로, 데이터가 많을 경우 비효율적이다.

또, 동일한 값을 가진 요소의 상대적인 순서가 바뀔 수 있으므로 안정성이 문제도 가지고 있는 단점이 있다.

 

선택정렬의 시간 복잡도

 

선택정렬의 시간복잡도는 위에서 말했듯 O(n²)이다.
이는 리스트의 길이에 비례하여 정렬하는 데 필요한 비교 횟수가 증가한다는 것을 의미한다.

 

선택정렬의 작동 원리

 

선택정렬은

1. 현재 인덱스(처음 시작이라면 첫번째 원소)값과 그 다음값부터 마지막 값까지 비교하여 가장 작은 값을 찾고

2. 그 값과 현재 값을 교환하고

3. 다음 인덱스로 이동하여 리스트의 모든 원소가 정렬될 때까지 반복

 

하여 정렬한다.

 

[64, 25, 12, 22, 11]를 가지고 예시를 들어보자.

 

우선 전체 리스트 중에서 가장 작은 값을 찾는다.
11이 가장 작기 때문에 첫 번째 요소인 64와 교환한다. 그럼 결과는 [11, 25, 12, 22, 64].

그다음 순서로 가서, 나머지 리스트에서 가장 작은 값을 찾는다.
12가 가장 작기 때문에 두 번째 요소인 25와 교환한다.
리스트는 [11, 12, 25, 22, 64]가 된다.

다음으로 22가 가장 작은 값이므로 세 번째 요소인 25와 교환한다.
리스트는 [11, 12, 22, 25, 64]가 된다.

마지막으로 25와 64가 이미 정렬된 순서이므로 그대로 둔다.

 

 

코드로 구현해보자.

선택정렬 구현(Java)

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        // 배열의 각 원소를 하나씩 선택
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i; // 현재 위치를 최소값 인덱스로 초기화

            // 현재 범위에서 가장 작은 원소를 찾음
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // 가장 작은 원소를 현재 위치의 원소와 교환
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("정렬된 배열: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

 

 

선택정렬 구현(Javascript)

function selectionSort(arr) {
    let 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;
            }
        }

        // 가장 작은 원소를 현재 위치의 원소와 교환
        let temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }

    return arr;
}

let arr = [64, 25, 12, 22, 11];
arr = selectionSort(arr);
console.log("정렬된 배열: ", arr);

 

 

선택정렬은 입력 데이터가 적을 때 유용한 정렬 알고리즘이다. 구조가 간단하고 구현이 편해서 기초로 많이 활용된다.

다음에는 좀 더 효율적인 정렬 알고리즘도 공부해야겠다.

 

끝!