[알고리즘] 정렬 - (1) 선택 정렬

정렬

정렬 (sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.

정렬 알고리즘은 이진 탐색 (binary search)의 전처리 과정이기도 하다.

정렬 알고리즘은 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 등 다양한 알고리즘이 존재하고, 문제에서 요구하는 조건에 따라서 적절한 정렬 알고리즘을 공식처럼 사용해야 한다. 만약 상황에 적절하지 못한 알고리즘을 이용하면 당연히 프로그램은 비효율적으로 동작하고 필요 이상으로 시간을 많이 소요한다.

이제 문제 상황을 가정해 보자. 숫자가 하나씩 적힌 카드가 10장이 있다. 이를 오름 차순으로 정렬해보자.

우리는 보통 카드를 한번 훑고 숫자가 0 ~ 9로 구성된 것을 눈치채고 0에서 9까지 순서대로 나열한다. 이것은 우리도 모르게 데이터의 규칙성을 파악한 것이다.

하지만 컴퓨터의 경우, 우리처럼 데이터의 규칙성을 직관적으로 알 수 없으며, 어떻게 정렬을 수행할 지에 대한 과정을 소스 코드로 작성하여 구체적으로 명시해줘야 한다.

1. 선택 정렬

이 방법은 가장 원시적인 방법으로, 매번 가장 작은 것을 선택한다는 의미에서 선택 정렬 알고리즘이라 불린다.

즉, 데이터가 무작위로 주어졌을 때, 가장 작은 데이터를 맨 앞자리의 데이터와 바꾸고, 그 다음으로 작은 데이터를 찾아서 앞에서 두 번째 데이터와 바꾸는 과정을 정렬이 다 될 때까지 반복하는 것이다.

가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어진다.

선택 정렬 알고리즘이 일어나는 과정을 그림을 통해 한번 살펴 보도록 하겠다.

회색 카드는 '현재 정렬되지 않은 데이터 중 가장 작은 데이터'를 의미하고, 하늘색 카드는 '이미 정렬된 데이터'를 나타낸다.

step 0️⃣ : 초기 단계에서는 모든 데이터가 정렬되어 있지 않으므로, 전체 중에서 가장 작은 데이터를 선택한다. 따라서 '0'을 선택해 맨 앞에 있는 데이터 '7'과 바꾼다.

step 1️⃣ : 이제 정렬된 첫 번째는 제외하고 이후 데이터 중에서 가장 작은 데이터인 '1'을 선택해서 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '5'와 바꾼다.

step 2️⃣ : 이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 '2'를 선택한다. 이를 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '9'와 바꾼다.

step 3️⃣ : 이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 '3'을 선택한다. 이를 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '7'과 바꾼다.

step 4️⃣ : 이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 '4'을 선택한다. 이를 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '7'과 바꾼다.

step 5️⃣ : 이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 '5'를 선택한다. 처리되지 않은 데이터 중 가장 앞에 있는 데이터도 '5' 이기 때문에 그냥 다음으로 넘어간다.

step 6️⃣ : 이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 '6'를 선택한다. 처리되지 않은 데이터 중 가장 앞에 있는 데이터도 '6' 이기 때문에 그냥 다음으로 넘어간다.

step 7️⃣ : 이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 '7'을 선택한다. 이를 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '9'와 바꾼다.

step 8️⃣ : 이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 '8'을 선택한다. 이를 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '9'와 바꾼다.

step 9️⃣ : 가장 작은 데이터를 앞으로 보내는 과정을 9번 반복한 상태는 다음과 같으며 마지막 데이터는 가만히 두어도 이미 정렬된 상태이다. 따라서 이 단계에서는 정렬을 마칠 수 있다.

아래는 정렬이 완료된 상태이다.

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

1) selectionSort.py

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] # swap

print(arrray)

- 결과

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

+) swap

선택 정렬에서는 swap이 사용된다.

swap이란 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업을 의미한다. 파이썬에서는 다음처럼 간단하게 리스트 내 두 원소의 위치를 변경할 수 있지만, 다른 프로그래밍 언어의 경우, 명시적으로 임시 저장용 변수를 만들어 두 원소의 값을 변경해야 한다.

- swap.py

# 0 인덱스와 1 인덱스의 원소 교체하기
array = [3, 5]
array[0], array[1] = array[1], array[0]

print(array)

- 결과

[5, 3]

- swap.c

// swap 함수
void swap(a, b){
    // swap 시작
    temp = a;
    a = b;
    b = temp;
    printf(a, b)
}

a = 3;
b = 5;

swap(a, b)

- 결과

5 3

2) 선택 정렬의 시간 복잡도

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

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

위의 그림처럼 구현했을 때 총 연산 횟수는 N + (N - 1) + (N - 2) + ... + 2로 볼 수 있다.

따라서 근사치로 N x (N + 1) / 2 번의 연산을 수행한다고 할 수 있고 빅 오 표기법으로는 O(N^2)이라고 표현할 수 있다.

만약 정렬해야 할 데이터가 100배 늘어나면, 이론적으로 수행 시간은 10,000배로 늘어난다. 그럼 이러한 시간 복잡도를 가지는 선택 정렬이 얼마나 효율적일까?

- 선택 정렬, 퀵 정렬, 기본 정렬 라이브러리의 수행 시간 비교

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

선택 정렬은 기본 정렬 라이브러리를 포함해 뒤에서 다룰 알고리즘과 비교했을때 매우 비효율적이다.

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