[Algorithm] 선택 정렬(Selection Sort) - C++, Java, Python 구현

정렬 알고리즘에서 가장 기본이 되는 선택 정렬을 알아보고 C++, 자바 그리고 파이썬으로 구현해봅시다.

 

• 자료구조, 알고리즘 시리즈 모아보기

 

선택 정렬

`선택 정렬(selection sort)`은 정렬할 수열에서 가장 큰 값(혹은 가장 작은 값)을 선택해 한쪽 끝으로 옮기는 행위를 반복하여 정렬하는 알고리즘입니다.

- Pseudocode

정렬해야 하는 배열 A[n]이 주어졌을 때 선택 정렬 알고리즘은 다음과 같습니다.

selectionSort(A[], n){
    for( last ← n downto 2 ){
        A[1 ⋯ last] 중 가장 큰 수 A[k]를 찾는다;
        A[k] ↔︎ A[last];
    }
}

조금 더 구체화하면 아래와 같습니다.

selectionSort(A[], n){
    for( last ← n downto 2 ){
        k ← findTheLargest(A, last);
        A[k] ↔︎ A[last];
    }
}

findTheLargest(A[], last){
    largest ← 1;
    for( i ← 2 to last )
        if( A[i] > A[largest] ) largest ← i;
    return largest;
}

편의상 배열에서 정렬이 안된 부분을 A, 정렬된 부분을 B라고 하겠습니다. last는 A의 마지막 인덱스입니다. A에서 가장 큰 값을 찾아 A의 끝 값과 교환합니다. A의 끝값은 이제 정렬이 되었으니 last를 하나 줄이고 위 과정을 반복합니다. 과정을 반복하는 동안 A에서 가장 큰 값이 B에 포함되어 A의 크기는 줄어들고 가장 큰 값이 순서대로 B에 포함되어 정렬이 완료됩니다.

- 시간 복잡도

선택 정렬의 수행시간은 모든 경우에서 $\Theta(n^2)$입니다.

모든 경우에서 for문은 last를 n에서 2까지 n-1번 반복합니다. 각 반복마다 1번째 원소부터 last번째 원소사이에 최댓값을 찾는데 이때 최댓값을 찾기 위해 원소끼리 비교연산을 last-1번 수행합니다.

$$\displaystyle\sum_{last=2}^n{(last-1)}=\frac{n(n-1)}{2}=\Theta(n^2)$$

 

구현

- C++

void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

int find_the_largest(int arr[], int last) {
    int idx = 0;
    for(int i=1; i<=last; i++)
        if(arr[idx] < arr[i])
            idx = i;
    return idx;
}

void selection_sort(int arr[], int n) {
    for(int last=n; --last;) {
        int idx = find_the_largest(arr, last);
        swap(arr[idx], arr[last]);
    }
}

- Java

class Sort {
    public static void selectionSort(int[] arr){
        for(int last=arr.length-1; last>0; last--){
            int k = findTheLargest(arr, last);
            swap(arr, k, last);
        }
    }

    private static int findTheLargest(int[] arr, int last){
        int largest = last;
        for(int i=0; i<last; i++)
            if(arr[i] > arr[largest])
                largest = i;
        return largest;
    }
    
    // static void selectionSort(int[] arr){
    //     for(int last=arr.length-1; last>0; last--){
    //         int largest = last;
    //         for(int i=0; i<last; i++)
    //             if(arr[i] > arr[largest])
    //                 largest = i;
    //         swap(arr, largest, last);
    //     }
    // }

    private static void swap(int[] arr, int i, int j){
        if(i==j) return;
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

- Python

def selection_sort(arr, n):
    for first in range(n):
        min_idx = first
        for i in range(first, n):
            if arr[i] < arr[min_idx]:
                min_idx = i
        arr[min_idx], arr[first] = arr[first], arr[min_idx]

파이썬에서는 최솟값을 찾아 배열의 앞으로 보내는 방법으로 구현했습니다.

 

재귀

선택 정렬의 알고리즘을 잘 보면 재귀의 성질을 가지고 있습니다. 재귀는 어떤 문제를 해결할 때 크기가 작은 동일한 문제를 해결해 얻은 답을 이용하는 방식입니다. 크기가 n인 배열을 선택 정렬로 정렬하면 첫 번째 for문이 실행되고 나면 n-1인 배열을 정렬하는 문제가 됩니다. 수도코드로 나타내면 다음과 같습니다.

- Pseudocode

selectionSort(A[], last){
    if( last < 2 ) return;
    k ← findTheLargest(A, last);
    A[k] ↔︎ A[last];
    selectionSort(A, last-1);
}

findTheLargest는 위와 같습니다.

- Java (재귀)

public static void selectionSort(int[] arr, int last){
    if(last < 1) return;
    int k = findTheLargest(arr, last);
    swap(arr, k, last);
    selectionSort(arr, last-1);
}

위에서 구현한 자바 코드에서 selectionSort 메서드만 수정하면 됩니다. for문이 자기 호출로 바뀌었고 입력으로 마지막 인덱스를 받습니다.