정렬이란, 섞여 있는 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이다.
정렬 알고리즘은 일반적으로 O(N^2)과 O(NlogN) 사이의 시간 복잡도를 가지며 특수한 경우 O(N)인 경우도 있다.
다양한 정렬 알고리즘에 대해서 정리해보자. (모든 예시는 오름차순 정렬을 기준으로 한다)
평균적으로 O(N^2)의 시간 복잡도를 갖는 정렬 알고리즘
1. 선택 정렬(Selection Sort)
- 현재 정렬되지 않은 데이터 중에서 가장 작은 데이터를 선택하여 가장 왼쪽의 데이터와 바꾼다.
- 맨 왼쪽 데이터를 제외한 데이터에 대해서 선택 정렬을 반복한다. (하나의 원소만 남을 때까지)
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)※ 선택 정렬의 시간 복잡도
선택 정렬은 N - 1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교가 필요하다.
일반적으로 연산횟수는 N x (N + 1) / 2번의 연산을 수행하게 되고 이는 O(N^2)의 시간 복잡도를 갖는다.
선택 정렬은 다른 정렬 알고리즘과 비교했을 때 매우 비효율적이지만 가장 직관적이고 구현이 쉬운 정렬 알고리즘이다.
2. 버블 정렬(Bubble Sort)
- 서로 인접한 두 원소를 검사하는 알고리즘
- 1회전이 끝나면 가장 큰 원소가 맨 뒤로 이동하여 제외된다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(array) - 1, 0, -1): # 정렬 범위 줄여 나가기
for j in range(i):
if array[j] > array[j + 1]: # 앞 뒤 값 비교
array[j], array[j + 1] = array[j + 1], array[j]
print(array)
※ 버블 정렬의 시간 복잡도
버블 정렬은 루프문을 통해 맨 뒤부터 맨 앞까지 모든 인덱스에 접근해야 하기 때문에 기본적으로 O(N)의 시간을 소모하며, 각 루프 안에서 인접한 값들의 대소 비교 및 자리 교대를 위해서 O(N)의 시간이 걸리기 때문에 총 O(N^2)의 시간복잡도를 갖는다.
다른 정렬 알고리즘에 비해서 스왑이 빈번하게 이루어지는 알고리즘이다 보니 매우 비효율적인 시간 복잡도를 가지지만 정렬되어 있는 데이터에 대해서는 최적화된 구현을 통해 성능을 개선시킬 수 있는 여지가 있다고 한다.
3. 삽입 정렬(Insertion Sort)
- 정렬 범위를 한 칸씩 확장해나가면서 새로운 값을 올바른 위치에 찾아 삽입하는 방식이다.
- 두 번째 원소부터 시작하여 마지막 원소의 자리까지 찾는다.
- 자리를 찾으면 삽입을 위해 원소를 한 칸씩 뒤로 이동시켜야 한다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)):
for j in range(i, 0, -1): # 인덱스 i부터 1까지 감소하며 반복
if array[j] < array[j - 1]:
array[j], array[j - 1] = array[j - 1], array[j]
else:
break
print(array)
※ 삽입 정렬의 시간 복잡도
삽입 정렬은 루프문을 통해 정렬 범위를 2개에서 전체로 확장하기 위해 O(N)의 시간을 소요하며, 각 루프에서 새롭게 추가된 값과 기존 값들의 대소 비교 및 자리 교체를 위해서 O(N)의 시간이 필요하여 총 O(N^2)의 시간 복잡도를 갖는다.
하지만 삽입 정렬은 현재 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하여 최선의 경우 O(N)의 시간 복잡도를 가진다는 것이 특징이다. 따라서 선택 정렬은 보통의 경우 비효율적이나 정렬이 거의 되어 있는 상황에서 사용한다면 어떠한 정렬 알고리즘보다도 빠른 성능을 보여줄 수 있다.
평균적으로 O(NlogN)의 시간 복잡도를 갖는 정렬 알고리즘
1. 병합 정렬(Merge Sort)
- 분할 정복(Divide and Conquer) 기법과 재귀를 이용한 정렬이다.
- 주어진 배열을 원소가 하나만 남을 때까지 계속 반으로 나눈 후, 크기 순으로 정렬을 하면서 다시 병합한다.
병합 정렬 과정을 애니메이션으로 보면 다음과 같다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def merge_sort(array):
if len(array) < 2:
return array
mid = len(array) // 2
left = merge_sort(array[:mid])
right = merge_sort(array[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right): # 둘 중 하나가 끝날 때까지
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
if i == len(left): # 왼쪽 배열이 끝났다면 오른쪽 배열의 나머지 모두 담음
result += right[j:]
else: # 오른쪽 배열이 끝났다면 왼쪽 배열의 나머지 모두 담음
result += left[i:]
return result
array = merge_sort(array)
print(array)
※ 병합 정렬의 시간 복잡도
병합 정렬은 분할과 병합 단계로 나눌 수 있으며, 단순히 중간 인덱스를 찾는 분할 비용보다 모든 값들을 비교해야하는 병합 비용이 크다. 전반적인 배열의 크기는 점점 절반으로 줄어들기 때문에 O(logN) 시간이 필요하며, 각 단계에서 병합할 때 모든 값들을 비교해야 하므로 O(N) 시간이 걸려 총 O(NlogN)의 시간 복잡도를 갖는다.
※ 병합 정렬의 공간 복잡도
병합 정렬은 두 개의 배열을 병합할 때 병합 결과를 담아 놓을 배열이 추가로 필요하기 때문에 추가 공간이 필요없는 다른 정렬 알고리즘들의 공간 복잡도가 O(1)인 것에 비해 병합 정렬의 공간 복잡도는 O(N)이다.
2. 퀵 정렬(Quick Sort)
- 병합 정렬과 마찬가지로 분할 정복(Divide and Conquer) 기법과 재귀를 이용한 정렬 알고리즘이다.
- 리스트의 요소 중 하나를 pivot 이라고 하는 임의의 기준값으로 사용한다.
- pivot을 기준으로 작은 원소들은 왼쪽 리스트, 큰 원소들은 오른쪽 리스트로 옮기고 각각을 다시 퀵 정렬하는 것을 반복한다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
if start >= end: # 원소가 1개인 경우 종료
return
pivot = start # 첫 번째 원소를 pivot으로 설정
left = pivot + 1
right = end
while left <= right:
# pivot 보다 큰 데이터를 찾을 때 까지 반복
while left <= end and array[left] <= array[pivot]:
left += 1
# pivot 보다 작은 데이터를 찾을 때 까지 반복
while right > start and array[right] >= array[pivot]:
right -= 1
if left > right: # 엇갈렸다면 작은 데이터와 pivot을 교체
array[right], array[pivot] = array[pivot], array[right]
else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
array[left], array[right] = array[right], array[left]
quick_sort(array, start, right - 1) # 왼쪽 부분 정렬
quick_sort(array, right + 1, end) # 오른쪽 부분 정렬
quick_sort(array, 0, len(array) - 1)
print(array)
※ 퀵 정렬의 시간 복잡도
퀵 정렬의 성능은 어떻게 pivot을 설정하느냐에 따라 크게 달라질 수 있다. 이상적인 경우에는 pivot 값을 기준으로 동일한 개수의 작은 값들과 큰 값들이 분할되어 병합 정렬과 같은 O(NlogN)의 시간 복잡도를 가지게 된다. 하지만 pivot 값을 기준으로 분할했을 때 값들이 한쪽으로 치우치게 되면 성능이 저하되고 최악의 경우 O(N^2)의 시간 복잡도를 가지게 된다.
퀵 정렬은 일반적으로 기본 정렬 라이브러리의 기반이 되는 알고리즘인데 이들은 항상 O(NlogN)의 시간 복잡도를 보장할 수 있도록 pivot 값을 설정하는 추가적인 로직이 더해져서 구현되어있다.
평균적으로 O(N)의 시간 복잡도를 갖는 정렬 알고리즘
1. 계수 정렬(Counting Sort)
- 계수 정렬은 중복된 값이 많이 분포되어 있는 배열을 정렬할 때 효과적인 정렬 알고리즘이다.
- 데이터의 값이 양의 정수인 경우에만 사용 가능하지만 매우 빠른 성능을 자랑한다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언
count = [0] * (max(array) + 1)
for i in range(len(array)):
count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(count)):
for j in range(count[i]):
print(i, end = ' ')
※ 계수 정렬의 시간 복잡도
모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최댓값의 크기를 K라고 할 때, 계수 정렬의 시간 복잡도는 O(N + K)이다. 계수 정렬은 앞에서부터 데이터를 하나씩 확인하면서 리스트에서 적절한 인덱스의 값을 1씩 증가시킬 뿐만 아니라, 추후에 리스트의 각 인덱스에 해당하는 값들을 확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문이다.
※ 계수 정렬의 공간 복잡도
계수 정렬은 데이터의 범위만 한정되어 있다면 항상 빠르게 동작하는 정렬 알고리즘이다.하지만 때에 따라서 심각한 비효율성을 초래할 수 있다. 예를 들어 데이터가 0과 999,999 단 2개만 존재한다고 가정하면 이럴 때에도 리스트의 크기가 100만이 되도록 선언해야 한다. 따라서 항상 사용할 수 있는 알고리즘은 아니며 동일한 값이 여러 번 등장할 때 적합하다. 계수 정렬의 공간 복잡도는 O(N + K)이다.
2. 기수 정렬(Radix Sort)
- 기수 정렬은 낮은 자리수부터 비교하여 정렬해 가는 정렬 알고리즘이다.
- 원소들의 값이 음수가 아닌 정수이고 자릿수가 모두 같을 때 사용 가능하다.
# 큐(queue)를 이용한 기수 정렬 구현
from collections import deque
array = [15, 27, 64, 35, 19, 37, 28]
def radix_sort(array):
buckets = [deque() for i in range(10)] # 0 ~ 9 까지의 큐
max_num = max(array)
queue = deque(array)
cur_digit = 1
while max_num >= cur_digit:
while queue:
num = queue.popleft()
buckets[(num // cur_digit) % 10].append(num) # 각 자리수의 숫자에 해당하는 큐에 넣음
for bucket in buckets:
while bucket:
queue.append(bucket.popleft())
cur_digit *= 10
return list(queue)
print(radix_sort(array))
※ 기수 정렬의 시간 복잡도
기수 정렬은 데이터의 개수가 N이고 데이터의 최대 자릿수를 K라고 했을 때 N * K번의 연산을 하게 되고 O(N)의 시간 복잡도를 갖는다. 보통 기수 정렬은 계수 정렬에 비해 동작이 느리지만 처리할 수 있는 정수의 크기는 더 크다. 또한 기수 정렬의 탐색 과정을 보면 알 수 있듯이 최악, 최선의 경우가 존재하지 않아 항상 빠르고 안정된 성능을 보여준다.
※ 기수 정렬의 공간 복잡도
기수 정렬이 빠르고 안정된 수행 속도를 가지고 있기에 가장 좋은 정렬 알고리즘이라고 생각할 수 있지만 그렇지는 않다.
왜냐하면, 버킷이라는 작지 않은 용량의 추가적인 메모리 공간을 필요로 하기 때문이다.
정렬 알고리즘 시간 복잡도 비교
- 힙정렬에 관한 포스트: [자료구조] 우선순위 큐(Priority Queue), 힙(Heap)
정렬 라이브러리의 사용과 코딩 테스트
정렬 라이브러리는 항상 최악의 경우에도 O(NlogN)의 시간 복잡도를 보장한다. 따라서 우리가 직접 퀵 정렬을 구현하여 사용할 때보다 더욱 더 효과적이다. 파이썬에서는 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘을 사용하고 있다.
문제에서 별도의 요구가 없이 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있다면 계수 정렬 등 더 빠르게 동작하는 정렬 알고리즘을 사용하면 된다.
※ 문제 유형 별 정렬 알고리즘의 사용
1. 정렬 라이브러리로 풀 수 있는 문제
- 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제
- 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
3. 더 빠른 정렬이 필요한 문제
- 퀵 정렬 기반의 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.
참고자료:
이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음(한빛미디어),
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
| [알고리즘 이론] 최단 경로 알고리즘(1) - 다익스트라 최단 경로 알고리즘 (0) | 2022.02.23 |
|---|---|
| [알고리즘 이론] 다이나믹 프로그래밍(Dynamic Programming) (0) | 2022.02.05 |
| [알고리즘 이론] 이진 탐색(Binaray Search) (0) | 2022.02.02 |
| [알고리즘 이론] 알고리즘 성능 평가 - 복잡도 (0) | 2022.01.25 |
| [알고리즘 이론] 탐색 알고리즘 - DFS / BFS (0) | 2022.01.14 |