다양한 정렬 정리(2) - 선택정렬

선택정렬(Selection Sort)는 버블 정렬과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.

쉽게 생각하면, 어떤 자리를 선택하고 그 자리에 오는 값을 찾는 것으로 생각하면 편하다.

선택 정렬

선택 정렬은 배열의 첫번째 인덱스부터 시작하여 그 자리에 배열에서 가장 작은 수를 가져와 넣는 정렬 알고리즘이다. 배열의 첫번째 자리에 배열 전체 중 가장 작은 값을 넣고, 두번째 자리에는 그 다음으로 작은 값을 가져와 집어넣는다.

이때, 값을 집어넣는 방법으로 값을 넣어야 하는 자리에 있는 값과 가져올 자리의 값을 바꾼다.

자바 코드

void selectionSort(int[] arr){
    int indexMin, temp;
    for(int i = 0; i < arr.length -1; i++){ // 어디에 값을 넣을지 위치 확인
        indexMin = i;
        for(int j = i+1; j < arr.length; j++){ // 가장 작은 값 찾기
            if(arr[j] < arr[indexMin]){
                indexMin = j;
            }
        }
        // 원소 넣기
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
    }
}

시간 복잡도

데이터의 개수가 n개라고 생각했을 때,

• 첫 번째 반복에서의 비교 횟수 : n-1
• 두 번째 반복에서의 비교 횟수 : n-2 …. (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 가 되므로 O(n^2)이다. 최선, 평균, 최악의 경우 시간복잡도 역시 모두 동일하다.

공간 복잡도

주어진 배열안에서 원소의 교환을 통해 해결하므로, O(n)이다.