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

선택 정렬

• 가장 간단한 정렬 알고리즘
• 가장 직관적인 알고리즘

코드 설계하기

• 목표: 가장 작은 값을 선택하여 자리 바꾸기
  1. 모든 카드를 A에 보관하기
  2. 가장 작은 값의 카드를 선택하여 B에 보관
  3. 2를 반복

// pseudo-code
SelectionSort(A, n) {
    for i <- to n-2 {
        min <- i
        for j <- i+1 to n-1 {
            if(A[j] < A[min]) {
                min <- j
            }
        }
        tmp <- A[i]
        A[i] <- A[min]
        A[min] <- tmp
    }
}

코드 구현

    /**
     * 선택 정렬
     * @param A 정수로 이루어진 배열
     * @param n 배열의 길이
     * @return
     */
    private int[] selectionSort(int[] A, int n) {
        int[] ret;

        for (int i = 0; i < n - 1; i++) { // 0 ~ n-2 까지 반복 (배열의 마지막 전까지)
            int min = i;
            for (int j = i + 1; j < n; j++) { // 1 ~ n-1 까지 반복 (배열의 마지막 까지)
                if (A[j] < A[min]) {
                    min = j;
                }
            }
            int tmp = A[i];
            A[i] = A[min];
            A[min] = tmp;
        }

        ret = A;
        return ret;
    }

• 과정

0:     2    7    4    1    5    3    
0:     2    7    4    1    5    3    
0:     2    7    4    1    5    3    
0:     2    7    4    1    5    3    
0:     2    7    4    1    5    3    

0:     1    7    4    2    5    3    swap
1:     1    7    4    2    5    3    
1:     1    7    4    2    5    3    
1:     1    7    4    2    5    3    
1:     1    7    4    2    5    3    

1:     1    2    4    7    5    3    swap
2:     1    2    4    7    5    3    
2:     1    2    4    7    5    3    
2:     1    2    4    7    5    3    

2:     1    2    3    7    5    4    swap
3:     1    2    3    7    5    4    
3:     1    2    3    7    5    4    

3:     1    2    3    4    5    7    swap
4:     1    2    3    4    5    7    

4:     1    2    3    4    5    7    

분석

• 복잡성 분석
  • O(n^2)
• 선택정렬은 느린 알고리즘에 속함