[CH6 정렬] 기준에 따라 데이터를 정렬 (2)

선택 정렬

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸는 것을 반복한다
• 이 방법은 가장 원시적인 방법으로 매번 '가장 작은 것을 선택한다'는 의미에서 '선택 정렬'이라고 불린다
• 정렬 알고리즘에서는 흔히 데이터의 개수를 N이라고 표현한다

 

다음 예제를 통해 N=10인 경우를 살펴보자

이 때 회색 카드는 '현재 정렬되지 않은 데이터 중에서 가장 작은 데이터'를 의미하고, 하늘색 카는 '이미 정렬된 카드'를 의미한다

 

 

선택 정렬의 단계별 설명

위의 카드를 선택 정렬 알고리즘을 통해 정렬해보자!

 

STEP 0

STEP 0) 초기 단계에서는 모든 데이터가 정렬되어 있지 않으므로, 전체 중에서 가장 작은 데이터를 선택한다 (0)

따라서 선택한 0과 맨 앞에 있는 데이터 7의 자리를 바꾼다

 

 

STEP 1

STEP 1) 이제 정렬된 첫번쨰 데이터는 제외하고 그 뒤의 데이터 중에서 가장 작은 데이터인 1을 선택하여 이를 처리되지 않은 데이터 중 가장 앞에 있는 데이터 5와 자리를 바꾼다

 

 

STEP 2

STEP 2) 이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 2를 선택하고, 처리되지 않은 데이터 중 가장 앞에 있는 데이터 9와 자리를 바꾼다

 

 

STEP 3

STEP 3) 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 3을 선택하고, 이를 처리되지 않은 데이터 중 가장 앞에 있는 데이터 7과 자리를 바꾼다

---

STEP 9

STEP 9) 앞의 과정을 계속해서 반복하면 위의 그림처럼 맨 마지막 데이터만 남는다. 하지만 남은 데이터는 위 과정을 수행해도 자리는 바뀌지 않으므로 이 단계에서는 정렬을 수행하지 않고 끝내면 된다

 

---

선택 정렬 소스코드

이처럼 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬이 완료된다

이제 파이썬과 C++ 코드로 선택 정렬을 구현해보자!

 

파이썬 코드)

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    min_index = i #가장 작은 원소의 인덱스

    for j in range(i+1, len(array)):
        if array[min_index] > array[j]:
            min_index = j

    array[i], array[min_index] = array[min_index], array[i] #스와프

print(array)

중첩 반복문을 사용하여 구현하였다

이 때 파이썬에서 스와프는 위처럼 해주면 된다

 

파이썬 선택정렬 결과화면

 

C++ 코드)

#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
    int n = 10;
    int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
    
    for(int i=0;i<n;i++)
    {
        int min_index = i;
        
        for(int j=i+1;j<n;j++)
        {
            if(arr[min_index] > arr[j])
            {
                min_index = j;
            }
        }
        swap(arr[i],arr[min_index]);
    }
    
    for(int i=0;i<n;i++)
    {
        cout<<arr[i]<<" ";
    }

    return 0;
}

C++에서도 파이썬과 거의 동일하게 작성해주면 된다

C++에서는 #include <algorithm> 라이브러리에 swap 함수를 지원하기 떄문에 이를 사용하여 스와프하면 된다!

 

C++ 선택정렬 알고리즘

---

선택 정렬의 시간 복잡도

이제 선택 정렬의 시간 복잡도를 계산해보자

선택 정렬은 N-1번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다

또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다

구현 방식에 따라서 사소한 오차는 있을 수 있지만 앞쪽의 그림대로 구현하면 연산 횟수는 다음과 같다

N + (N-1) + (N-2) + ... + 2

따라서 근사치로 N*(N+1)/2 번의 연산을 수행한다고 하면, 빅오 표기법에 따라 O(N^2)이라고 표현할 수 있다

 

선택 정렬 알고리즘을 다른 알고리즘과 비교해보면 매우 비효율적인 것을 알 수 있다

(파이썬 기준)

데이터의 개수(N)	선택 정렬	퀵 정렬	기본 정렬 라이브러리
N=100	0.0123초	0.00156초	0.00000753초
N=1000	0.354초	0.00343초	0.0000365초
N=10000	15.475초	0.0312초	0.000248초

위처럼 선택 정렬 알고리즘은 다른 알고리즘에 비해 매우 비효율적이다

하지만 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩테스트에서 잦으므로 선택 정렬 소스코드에 익숙해질 필요는 있다