선택정렬 (Selection Sort)

선택정렬

선택정렬 : 정렬되지 않은 리스트에서 최소값을 선택하여 정렬된 부분의 마지막에 추가하는 알고리즘

- In-place 알고리즘

- Stable sort

 

#include <stdio.h>
 
void selectionSort(int arr[], int n) {
   int i, j, min_idx;
 
   for (i = 0; i < n-1; i++) {
       min_idx = i;
       for (j = i+1; j < n; j++) {
           if (arr[j] < arr[min_idx]) {
               min_idx = j;
           }
       }
       int temp = arr[min_idx];
       arr[min_idx] = arr[i];
       arr[i] = temp;
   }
}
 
int main() {
   int arr[] = {64, 25, 12, 22, 11};
   int n = sizeof(arr)/sizeof(arr[0]);
 
   selectionSort(arr, n);
 
   printf("Sorted array: ");
   for (int i=0; i < n; i++) {
       printf("%d ", arr[i]);
   }
   return 0;
}

선택정렬의 시간복잡도

시간복잡도 분석 : $$ O(n^2) $$

리스트의 크기가 n일 때... (레코트 갯수가 n개 일때)

 

1. for 루프 반복 횟수 : 외부 for문 : n-1번 / 내부 for문 : n-i-1번

 for (i = 0; i < n-1; i++) {
       min_idx = i;
       for (j = i+1; j < n; j++) {
           ...
       }
      ...
   }

 

2. 비교 연산 횟수 : $$ (n-1) + (n-2) + (n-3) + ... + 1 = n(n-1)/2 = O(n^2) $$

 

3. 이동 횟수 : $$ 3(n-1) $$

 

장/단점

장점 :  자료의 이동횟수가 미리 결정된다. [but 이동횟수가 큰편] -> 시간복잡도가 일정하다.

단점 :  자료가 정렬된 경우에 불필요하게 자기 자신과의 이동이 있다 (unstable) -> if(min_idx

 

int* selection_sort(int *list, int n){
    
    int i, j, least, tmp;
    for(i=0;i<n-1;i++){
        least = i;                //제일 작은 레코드가 담겨있는 인덱스 
        for(j=i+1;j<n;j++){
            if(list[j]<list[least]) least=j;
        }
        if(i != least) SWAP(list[i],list[least],tmp);
    }
    
    return *list;
}