선택 정렬(Selection Sort)

- 선택 정렬은 해당 작업을 반복한다

1. 가장 작은 수를 찾는다

2. 정렬되지 않은 가장 앞 부분과 교환

(교환이 없다면 이미 정렬이 되어있는 상태)

 

우리가 카드 등을 숫자 별로 정리한다고 생각했을 때

가장 먼저 떠오르는 정렬 방법이다

그만큼 쉽고 구현도 간단하지만

단점은 버블 정렬과 달리 정렬 완료 시점을 알지 못해

최적화가 되지 않는다는 것이다

 

 

- 자바로 간단한 예제를 짜고 주석을 달아놓고

//n개 입력 값을 받음(입력 값을 모른다는 가정)
int[] array = new int[n];

//최소 값 번호
int minIdx;

//교환을 위한 입력 값 순환
for(int sortIdx = 0; sortIdx < array.length - 1; sortIdx++) {
    minIdx = sortIdx;
    
    //최소 값을 찾는 순환
    for(int findIdx = sortIdx; findIdx < array.length; findIdx++) {
        //값 비교 후 변경
        if(array[minIdx] > array[findIdx]) {
            minIdx = findIdx;
        }
    }

    //XOR 값 교환(이미 정렬된 값 생략)
    if(minIdx != sortIdx) {
        array[sortIdx] = array[sortIdx] ^ array[minIdx];
        array[minIdx] = array[sortIdx] ^ array[minIdx];
        array[sortIdx] = array[sortIdx] ^ array[minIdx];
    }
}

//결과 출력
System.out.println(Arrays.toString(array));

 

 

- 마지막으로 시간 복잡도(Big-O)에 대해 말하자면

외부 반복문은

배열 마지막 방을 제외한 n-1 실행

여기서 상수는 무시함으로

n-1

-> O(n)

 

내부 반복문을 계산 할 경우

매 반복마다 정렬된 방을 제외로

기존 중첩 반복문으로 정확한 계산이 불가하다

ex) O(n) * O(n) = O(n^2)

 

하지만 전체 횟수를 등차수열의 합으로 표현할 수 있으며

ex) (n - 1) + (n - 2) + ... + 2 + 1

 

예를 들어 배열이 다섯개가 주어진 경우

(5 - 1) + (5 - 2) + (5 - 3) + (5 - 4) = 10

 

여기서 등차수열의 합 공식을 풀이하고

항의 개수 / 2 * (첫 번째 값 + 마지막 값)

-> n - 1 / 2 * ((n - 1) + 1)

-> n - 1 / 2 * (n - 1 + 1)

-> n - 1 / 2 * n

-> n(n - 1) / 2

 

등차수열의 합으로 계산을 한다면

5(5 - 1) / 2

-> 20 / 2

-> 10

 

다음 빅오 표기법을 적용하면

1. 상수 계수 무시(분모 포함)

2. 가장 큰 차수만 남김

n(n - 1) / 2

-> n^2 / 2 - n / 2

-> O(n^2)

 

마지막으로 외부 반복문과 내부 반복문을 합하지만

여태까지 말했던 상수와 작은 차수를 제외하면

O(n) + O(n^2)

-> O(n^2)

 

선택 정렬은 O(n^2)의 시간 복잡도를 가진다