[Sort] 선택 정렬 (Selection Sort)

소개

• 리스트 안의 자료중 가장 작은수 또는 가장 큰수를 찾아 첫 번째 위치 또는 가장 마지막 위치의 수와 교환해주는 정렬이다.
• 교환 횟수를 최소화하는 반면 비교하는 횟수는 증가한다.

 

동작원리

• 배열의 순서와 상관 없이 선택 정렬되는 배열은 n -1 의 교환이 이루어진다.
• 버블 정렬 보다 교환 횟수는 적어지지만 비교를 모든 원소를 해야하기 때문에 n2의 비교가 이루어진다.

for (int i = 0; i < arr.length; i++) {
    int minIndex = i;
    for (int j = i; j < arr.length; j++) {
        if (arr[minIndex] < arr[j]) {
            continue;
        }
        minIndex = j;
    }
    int temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
}

 

버블 정렬 vs 선택 정렬

대규모의 데이터를 처리한다고 가정해보자.

두개의 인접한 숫자를 n-1 번 실행하여 정렬하는 것보단 임의의 숫자를 정의하여 차례대로 비교하는 것이 훨씬 빠를것이다.