정렬(Sorting)은 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 여러 정렬 알고리즘이 있지만 선택 정렬, 삽입 정렬, 퀵 정렬, 그리고 계수 정렬 4가지를 알아보자.
1. 선택 정렬
배열의 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는것이다. 선택 정렬은 이중 반복문으로 구성되어 있어 시간 복잡도가 $O(N^2)$이다.
선택 정렬은 다음과 같이 구현할 수 있다.
import random
import time
random.seed(42)
N = 10000
array = list(range(N))
random.shuffle(array)
start = time.time()
for i in range(N):
# 앞에 있는 원소가 가장 작다고 가정
min_index = i
# 뒤에 있는 원소 중 더 작은 것을 발견하면 최소값 인덱스 갱신
for j in range(i + 1, N):
if array[min_index] > array[j]:
min_index = j
# 둘의 위치를 바꿈
array[i], array[min_index] = array[min_index], array[i]
end = time.time()
print(f"선택 정렬 소요 시간: {end-start:.2f}s")선택 정렬 소요 시간: 4.79s
매우 느리다.
2. 삽입 정렬
삽입 정렬의 동작 원리는 예시로 이해하는 것이 편하다.
[7, 5, 9, 0, 3, 1, 6, 2, 4, 8] 이런 배열이 있을 때 삽입 정렬은 두 번째 원소부터 시작한다. 왜냐하면 첫 번째 원소는 그 자체로 정렬되어 있다고 판단하기 때문이다.
5는 7보다 작기 때문에 7의 왼쪽에 삽입한다.
[5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
9는 5, 7보다 크기 때문에 그대로 둔다.
[5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
0은 5, 7, 9 보다 작기 때문에 5의 왼쪽에 삽입한다.
[0, 5, 7, 9, 3, 1, 6, 2, 4, 8]
3은 0보다 크고 5, 7, 9보다 작기 때문에 0의 왼쪽에 삽입한다.
[0, 3, 5, 7, 9, 1, 6, 2, 4, 8]
이런식으로 선택된 원소를 왼쪽과 비교하여 작다면 한 칸씩 이동시키다가 자신보다 작은 원소를 발견하면 멈추는 원리이다. 이를 코드로 구현하면 다음과 같다.
import random
import time
random.seed(42)
N = 10000
array = list(range(N))
random.shuffle(array)
start = time.time()
for i in range(1, N):
for j in range(i, 0, -1):
if array[j] < array[j - 1]:
array[j], array[j - 1] = array[j - 1], array[j]
else:
break
end = time.time()
print(f"삽입 정렬 소요 시간: {end-start:.2f}s")삽입 정렬 소요 시간: 6.61s
삽입 정렬 또한 이중 반복문을 사용하기 때문에 느리다. 그렇지만 배열이 어느 정도 정렬되어 있는 상태라면 매우 빠르게 동작한다.
3. 퀵 정렬
퀵 정렬은 배열의 특정한 기준이 되는 pivot을 사용하여 두 개의 하위 배열로 분할하고, 각 하위 배열을 재귀적으로 정렬하는 방식이다. 가장 대표적인 분할 방식인 Hoare Partition 방식으로 설명한다.
- 배열에서 첫 번째 요소를 pivot으로 설정한다.
- 선택한 pivot을 기준으로 배열을 분할한다. pivot보다 작은 요소는 왼쪽, 큰 요소는 오른쪽에 배치한다.
- pivot의 위치는 [왼쪽 배열, pivot, 오른쪽 배열]이 되도록 배치한다.
- 왼쪽 배열과 오른쪽 배열에 대해서 재귀적으로 수행한다. 종료 조건은 배열의 길이가 1보다 작거나 같을 때 이다.
이를 코드로 구현하면 다음과 같다.
import random
import time
random.seed(42)
N = 10000
array = list(range(N))
random.shuffle(array)
def quick_sort(array):
# 리스트가 하나 이하의 원소만을 담고 있다면 종료
if len(array) <= 1:
return array
pivot = array[0]
tail = array[1:]
left_side = [x for x in tail if x <= pivot]
right_side = [x for x in tail if x > pivot]
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
start = time.time()
sorted_array = quick_sort(array)
end = time.time()
print(f"퀵 정렬 소요 시간: {end-start:.2f}s")퀵 정렬 소요 시간: 0.02s
선택 정렬, 삽입 정렬보다 훨씬 빠르다. 퀵 정렬의 시간 복잡도는 $O(N \log N}$이다. 그런데 최악의 경우는 시간 복잡도가 $O(N^2)$이다. 이는 배열을 분할 할 때 마다 왼쪽이나 오른쪽 배열이 거의 없는 경우이다. 그래서 위의 예시처럼 랜덤하게 섞여 있는 배열의 경우에 빠르게 동작할 확률이 높다.
4. 계수 정렬
계수 정렬은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 계수 정렬은 모든 범위의 데이터를 담을 수 있는 리스트를 선언하는 방법을 사용한다. 따라서 가장 큰 데이터와 가장 작은 데이터의 차이가 100만을 넘지 않을 때 효과적으로 사용할 수 있다.
동작 원리는 간단하다. 예를 들어 배열의 요소의 범위가 0~9라고 가정해보자. 그러면 길이가 10인 리스트를 선언한 뒤 배열을 순회하면서 해당 요소와 동일한 인덱스의 값을 1씩 증가시키는 것이다.
코드로 보면 다음과 같다.
import random
import time
random.seed(42)
N = 10000
array = list(range(N))
random.shuffle(array)
start = time.time()
count = [0] * (max(array) + 1)
for item in array:
count[item] += 1
sorted_array = []
for idx in range(len(count)):
for _ in range(count[idx]):
sorted_array.append(idx)
end = time.time()
print(f"계수 정렬 소요 시간: {end-start:.2f}s")계수 정렬 소요 시간: 0.00s
파이썬의 정렬 라이브러리(sorted 함수나, sort 메서드)는 항상 시간 복잡도 $O(N \log N)$을 보장한다. 그래서 단순히 정렬해야하는 상황에서는 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용하자. 가끔 정렬 알고리즘의 원리에 대해서 묻는 문제가 나올 수도 있다고 한다.