[정렬] 선택정렬 (Select Sort)

선택정렬 O(n^2)
오름차순을 기준으로 할 때
최소값 및 우선순위가 높은 값을 인덱스 0 방향으로 가깝게 배치 
기준이 되는 인덱스와 최소값이 되는 인덱스를 swap
첫번째 하나 뽑고, 최소값을 구하고 비교하여 swap


첫번째 for 0 < n-1
두번째 for i+1 < n

버블과 다르게 swap연산과정은 n번 수행 (첫번째 for문에서 실행됨, 반면 버블은 비교 및 데이터 이동이 두번째 for에서 실행됨)

 

버블은 그때그때 교차, 선택은 최소값 위치 알아두고 바꾼다

[3,4,1,2]
i = 0
minidx = 0

idx 1(minidx+1) ~ 3(n-1) 중 최소값이 있는 idx:2
minidx = 2

temp = a[i] 
a[i] = a[minidx]
a[minidx] = temp

 

#include<iostream>
using namespace std;
 
void SelectSort(int arr[], int n){
 
    int minidx, temp;
 
    for (int i = 0; i < n - 1; i++){
        minidx = i;
        for (int j = i + 1; j < n; j++){
            if (arr[minidx] > arr[j]){
                minidx = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minidx];
        arr[minidx] = temp;
    }
}
 
int main(){
 
    int arr[4] = { 3, 4, 2, 1 };
    
    SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
 
    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
        printf("%d: %d\n", i+1, arr[i]);
 
    return 0;
}