선택정렬(selection sort)

선택정렬(selection sort) : 위치를 선택후 정렬

---

위치를 선택한 뒤 최댓값(최솟값)과 맨뒤(맨앞)과 교체

pseudocode

선택정렬(base : 배열시작주소 , n : 배열요소 개수)
	반복(i : 0 -> n) //위치선택
		min = 10000000
		반복(j : i -> n)
			조건(min > base[j])
				min = base[j]
				index = j
		교환(base[i],base[index])

best case 시간복잡도 : $O(n^2)$

worst case 시간복잡도 : $O(n^2)$

안정성 : 불안정

장점 : 단순한 알고리즘,교환 횟수 적음

단점 : 많은 비교횟수

실제코드

#include <stdio.h>

int main(int argc, const char * argv[]) {
    int arr[20] = {
        3,5,2,2,4,
        6,1,3,7,8,
        2,11,2,21,20,
        12,14,1,6,16};
    int n = sizeof(arr)/sizeof(int);
    int count;
    int min,index;
    for(int i =  0 ; i < n ; i++){
        min = 10000000000;
        for(int j = i ; j < n ; j++){
            if(min > arr[j]){
                min = arr[j];
                index = j;
                count++;
            }
        }
        int temp = arr[i];
        arr[i] = arr[index];
        arr[index] = temp;
    }
    
    
    
    for (int k = 0 ; k < n ; k++){
        printf("%d ",arr[k]);
    }
    printf("\nn^%d",count/n);
    return 0;
}