선택정렬(Selection Sort)

선택정렬이란?

제자리 정렬 알고리즘 중 하나로 현재 인덱스 번호 이후에 다음 인덱스 번호부터 끝까지 중에 최소값을 찾아 현재 인덱스 값과 교체를 해준다.

 

자바로 작성된 코드

 

public static void selectionSort(int [] arr){
    int num = arr.length;
    for(int i =0; i<num-1; i++){
        int idx = i;
        for(int j = i+1; j<num; j++){
            if(arr[j]<arr[idx]){
                idx = j;
            }
        }
        int tmp = arr[i];
        arr[i] = arr[idx];
        arr[idx] = tmp;
    }
}

 

시간 복잡도

O(N^2)

 

성능상 좋지 못한 알고리즘이지만 정렬 알고리즘 기초이니깐 알아두자.