[알고리즘] 선택 정렬(selection sort) 란 - travelbeeee

안녕하세요, 여행벌입니다.

오늘은 선택 정렬(selection sort)에 대해서 포스팅해보겠습니다.

---

선택 정렬이란

'정렬되지 않은 데이터에서 가장 작은 값을 뽑아 가장 앞의 데이터와 교환 해나가는 정렬 방식' 입니다.

---

EX)

바로 예시를 통해서 익혀보겠습니다.

[ 2 8 6 1 5 3 4 7 ] 8개의 숫자가 담긴 배열을 선택 정렬을 이용해서 정렬해보겠습니다.

STEP 1]

아직까지는 정렬된 부분이 하나도 없기 때문에 전체 범위에서 가장 작은 값인 1을 찾을 수 있습니다.

정렬되지 않은 가장 앞부분은 '2' 이므로 '2' 와 '1'을 SWAP 하게 됩니다.

STEP 2]

이제 정렬된 부분은 [ 1 ] 정렬되지 않은 부분은 [ 8 6 2 5 3 4 7 ] 이 되고, 정렬되지 않은 부분에서 가장 작은 값인 2를 가장 앞 '8'과 SWAP 합니다.

STEP 3]

이 과정을 반복하면 다음과 같이 됩니다.

STEP 4]

STEP 5]

STEP 6]

STEP 7]

정렬되지 않은 배열에 원소가 하나만 남아있다면, 그 원소가 가장 큰 원소이므로 STEP 8 까지 진행하지 않고 정렬을 종료할 수 있습니다.

---

코드 구현

코드는 다음과 같습니다.

void SelectionSort(int arr[], int N) {
    int min, temp;
    for(int i = 0; i < N - 1; i++) {
        min = i; // min 에 unsorted 중 가장 작은 값을 저장한다.
        for(int j = i+1; j < N; j++) 
            if(arr[j] < arr[min]) min = j;
        
        // 가장 앞과 SWAP 해준다.
        temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

첫 번째 for 문의 i 는 정렬되지 않은 배열의 가장 앞을 가리킵니다.

두 번째 for 문은 이제 정렬되지 않은 배열에서 가장 작은 값을 찾는 역할을 합니다.

---

복잡도 분석

이제 N 개의 원소가 있다고 가정하고 선택 정렬의 복잡도를 분석해보겠습니다.

첫 번째 원소를 정렬하기 위해 N개의 모든 원소를 순회하며 가장 작은 값을 찾아야 합니다.

즉, N - 1 번의 비교 연산이 발생합니다.

두 번째 원소를 정렬하기 위해서는 ( N - 1 )개의 모든 원소를 순회하며 가장 작은 값을 찾아야 합니다.

즉, N - 2 번의 비교 연산이 발생합니다.

그다음은 ( N - 2 ) 개의 모든 원소를 순회하며 가장 작은 값을 찾아야 하고

이 과정을 반복하면 총 (N - 1) + ( N - 2 ) + ⋯ + 1 번 비교 연산이 발생합니다.

등차수열의 합으로 O ( N ^ 2 ) 의 시간 복잡도를 가지는 것을 확인할 수 있습니다.

배열이 이미 정렬이 되어있더라도 가장 작은 값을 찾기 위해 항상 똑같은 순회, 비교 과정을 거치므로

최선, 평균, 최악의 경우에 대해서 시간 복잡도가 동일하게 O ( N ^ 2 )이 됩니다.

---

불안정 정렬

선택 정렬은 다음과 같은 상황에서 동일한 원소의 위치가 뒤바뀌므로 불안정 정렬에 속합니다.

[ 5 5 1 ] 배열을 선택 정렬을 통해서 정렬해보겠습니다.

이때 동일한 원소 5가 존재하므로 5-1 / 5-2 로 구분해주겠습니다.

결과는 다음과 같습니다.

정렬 전 [ 5-1 5-2 1 ]  → 정렬 후 [ 1 5-2 5-1 ]

 

동일한 원소가 존재할 때, 동일한 원소 간의 순서가 선택 정렬을 진행한 후 바뀐 것을 확인할 수 있습니다.

따라서, 선택 정렬은 '불안정 정렬' 입니다.

---

이상으로 선택 정렬 포스팅을 마치겠습니다.