C++ 선택정렬 - 정렬1

정렬중에서 가장 간단하고 직관적인 정렬이다

 

아이디어는

1. 배열중에서 가장 작은 숫자를 선택한다

2. 선택한 숫자와 가장 앞에있는 숫자를 교체한다

 

int* SelectionSort(int* arr, int size){
    int min, index = 0, temp;
    
    for(int i=0; i < size; i++){
        min = 10000;
        for(int j=i; j < size; j++){ //~i 까지 정렬이 되어있으므로 i에서 부터 시작
            if(arr[j] < min){	// 배열의 최소값을 찾는다
                min = arr[j];
                index = j;
            }
        }
        temp = arr[i];	//최솟값과 가장 앞의 값을 교체한다
        arr[i] = arr[index];
        arr[index] = temp;
    }

    return arr;
}

시간복잡도는 O(n * (n + 1) / 2) 이므로

O(n²)이다