[C] <자료구조> 선택 정렬 알고리즘 selection sort 시간 복잡도

선택 정렬

선택 정렬이란 리스트 중에 최솟값을 찾아 맨 앞의 값과 교체하는 정렬이다.

시간 복잡도는 평균 O(n²)으로 일반적으로 유사한 삽입 정렬보다 비효율적이며, 특히 큰 리스트에서 최악의 효율성을 가진다.

시간 복잡도의 최상은 O(n²), 최악은 O(n²)이다.

다음 영상은 선택 정렬의 동작 방식이다.

#include <stdio.h>
void selection_sort(int arr[], int len) {
    for (int i = 0; i < len; i++) {
        int min = i;
        for (int j = i; j < len; j++) 
            if (arr[min] > arr[j]) 
                min = j;        
        if (arr[i] != arr[min]) {
            int tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;    
        }
    }
}
void main() {
        int arr[] = { 9,1,6,8,4,3,2,0 };
        int len = sizeof(arr) / sizeof(int); //배열의 길이
        selection_sort(arr, len);
        for (int i = 0; i < len; i++) {
            printf("%d ", arr[i]);
        }
}