[자료구조] 정렬 #2 - 선택정렬 (Selection Sort)

선택정렬이란?

: 제자리 정렬 알고리즘 중 하나

- 제자리 정렬: 입력배열 이외의 다른 메모리는 요구하지 않는 정렬방법

- 현재 있는 값 중 가장 최솟값을 앞으로! (오름차순 정렬시)

 

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

 

구현 (오름차순)

void selectionSort(int a[], int size) {
    int min;
    
    for(int i=0; i<size-1; i++){
        min = i;
    	for(int j=i+1; j<size; j++){
            if(a[min] > a[j]){
            	min = j;
            }
        }
        if(min != i){ // 최소가 자기 자신인 경우는 이동x
          int temp = a[i];
          a[i] = a[min];
          a[min] = temp;
        }
    }
}

 

출처

gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html