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

목차

선택 정렬이란?

선택 정렬 (Selection Sort)이란 배열에서 가장 작은 또는 가장 큰 원소의 위치를 찾고, 그 위치와 배열의 가장 첫 번째 원소부터 차례로 바꿔주는 정렬 방식이다. 이렇게 간단하기 때문에 선택 정렬은 가장 기본적인 정렬 방식이다. 그리고 정렬을 할 때 추가적인 공간이 필요 없기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 

 

우선 한 배열의 숫자들을 오름차순으로 정렬을 한다고 가정해 보겠다. 이때 선택 정렬의 과정은 다음과 같다:

1. 주어진 배열에서 최솟값을 찾는다.

2. 최솟값을 맨 앞자리의 값과 교환한다.

3. 맨 앞자리를 제외한 나머지 값들 중 최솟값을 찾아 위와 같은 방법으로 반복한다. 

 

이제 다음과 같은 예시를 한번 보겠다. 

 

 

이 예시에는 1부터 7까지의 숫자들이 있다. 우선 첫 번째 인덱스부터 마지막 인덱스까지에서 최솟값을 찾는다. 최솟값은 1인데 맨 앞자리가 1이므로 변화 없이 간다. 

 

 

그다음에는 2번째 인덱스부터 최솟값을 찾는다. 최솟값은 2다. 따라서 두 번째 인덱스 값, 즉 7과 2의 위치를 서로 바꿔준다.

 

 

그다음에는 마찬가지로 3번째 인덱스부터 최솟값을 찾는다. 최솟값은 3이므로 세 번째 인덱스 값, 즉 5와 3의 위치를 바꿔준다. 

 

 

똑같은 방식으로 마지막까지 해 주면 다음과 같은 결과를 얻을 수 있다. 

 

 

이제 코드를 한번 보겠다.

 

코드

 

static void selectionSort() {
    int index = 0;
    int[] array = {1, 7, 5, 6, 3, 4, 2};  //정렬할 배열
    for (int i = 0; i < array.length; i++) {
        int min = Integer.MAX_VALUE;  //최솟값. 처음에는 가장 큰 수로 초기화 한다
        for (int j = i; j < array.length; j++) {
            if (array[j] < min) {  //최솟값보다 더 작은 수가 있으면 그 수를 최솟값으로 바꾸고 인덱스를 저장.
                min = array[j];
                index = j;
            }
        }
        int temp = array[i];  //새로운 변수 temp에 바꿀 수를 저장
        array[i] = array[index];  //바꿀 인덱스를 최솟값으로 바꾼다
        array[index] = temp;
    }
}

 

선택 정렬의 시간 복잡도는 O(n^2)이다. 즉, 만약에 정렬할 데이터의 개수가 10,000개 정도가 있으면 약 1억 번의 계산을 해야 한다는 것이다.