선택 정렬(Selection sort)알고리즘 - c언어 예제

선택 정렬(Selection sort)

 

• 선택 정렬은 배열의 제일 작은 숫자를 찾아 n번째 자리와 교환하는 알고리즘이다.
• 시간 복잡도는 O(n²)이다.

 

제일 첫번째 숫자를 min으로 지정한 뒤 제일 작은 값을 찾아 min으로 지정해 min위치의 값과 첫번째 값을 교환한다.

이런식으로 비교를 하여 앞에서 부터 정렬을 완료하며 n-1번째 회전에는 마지막 값은 정렬된것으로 간주하여 마무리한다.

이 알고리즘의 단점으로는 정렬을 이미 완료하였더라도 n-1번 돈다는 것이다.

 

예제소스

 

#include <stdio.h>
 
#define n 6
 
int main() {
 
    int arr[n] = { 67,33,15,88,69,5 };
    int min, temp;
 
    //배열 요소의 수 -1 만큼 반복
    for (int i = 0; i < n-1;i++) {
        min = i;
        //정렬과정 출력
        printf("%d회전 결과 : ",i);
        for (int i = 0; i < n; i++) {
            printf("[%d] ", arr[i]);
        }
        printf("\n");
        //i번째와 비교화여 더 작은 값이 있다면 min수정
        for (int j = i + 1; j < n;j++) {
            if (arr[j]<arr[i]) {
                min = j;
            }
        }
        // min이 변경되었다면 자리 교환
        if (i != min) {
            temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
    
    //최종 결과 출력
    printf("%d회전 결과 : ",n-1);
    for (int i = 0; i < n; i++) {
        printf("[%d] ", arr[i]);
    }
    
    return 0;
}