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

 

 

선택 정렬은 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘이다.

최선, 평균, 최악 모두 O(N^2)의 시간복잡도를 가진다.

 

 

 

1. 아직 정렬되지 않은 부분에서 가장 작은 요소 selection[i]를 선택

2. selection[i]와 아직 정렬되지 않은 부분의 첫번째 요소를 교환

3. n-1회 반복

 

 

void selectionSort(int[] list) {
    int indexMin, temp;
 
    for (int i = 0; i < list.length - 1; i++) {
        indexMin = i;
        for (int j = i + 1; j < list.length; j++) {
            if (list[j] < list[indexMin]) {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
}

출처 : 위키백과

 

선택 정렬은 동일한 값에 대해 기존의 순서가 뒤바뀔 수 있는 불안정한 정렬이다.