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

선택 정렬(Selection Sort)은 입력 배열 전체에서 최솟값을 선택하여 배열의 0번 원소와 자리를 바꾸고, 다음에는 0번 원소를 제외한 나머지 원소에서 최솟값을 선택하여  1번 원소와 자리를 바꾼다. 이런 방식으로 마지막에 2개의 원소중에서 작은 값을 선택하여 자리를 바꿈으로써 오름차순의 정렬을 마친다.

 

정렬 할 데이터: 15 9 6 27 24 9 8 13 10 1 5 

정렬된 데이터

1회전 결과: 1 9 6 27 24 9 8 13 10 15 5 

2회전 결과: 1 5 6 27 24 9 8 13 10 15 9 

3회전 결과: 1 5 6 27 24 9 8 13 10 15 9 

4회전 결과: 1 5 6 8 24 9 27 13 10 15 9 

5회전 결과: 1 5 6 8 9 24 27 13 10 15 9 

6회전 결과: 1 5 6 8 9 9 27 13 10 15 24 

7회전 결과: 1 5 6 8 9 9 10 13 27 15 24 

8회전 결과: 1 5 6 8 9 9 10 13 27 15 24 

9회전 결과: 1 5 6 8 9 9 10 13 15 27 24 

10회전 결과: 1 5 6 8 9 9 10 13 15 24 27

 

소스코드

void selectionsort(int a[], int n){
    for (int i = 0; i <= n - 2; i++) { //n - 1의 데이터는 자동으로 정렬됨.
        int min = i;
        for (int j = i + 1; j <= n - 1; j++) {  //i번 까진 정렬된 상태
            if (a[min] > a[j]) {
                min = j;
            }
        }
        swap(a, i, min);
    }
}

 

시간복잡도

O(N^2)