✏️ 서론
어제 배웠던 선택정렬, 삽입정렬에 이은
퀵 정렬, 계수 정렬을 배워보자
✏️ 본론
📍 quick_sort(퀵 정렬)
퀵 정렬은 지금까지 배운 정렬 알고리즘 중 가장 많이 사용되는 알고리즘이다.
퀵 정렬과 병합정렬은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 하다.
퀵 정렬은 다음과 같이 동작한다.
기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식
퀵 정렬에서는 대표적으로 피벗(pivot)이 사용된다.
큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 기준을 바로 피벗(pivot)이라고 표현한다.
피벗을 설정하는 자리는 많지만, 가장 왼쪽을 기준으로 잡자.
자세한 동작원리는 나동빈의 강의에서 살펴보자.
코드는 교재에 나온 2가지 모두 사용해봤는데,
뭔가 느낌이 딱 와닿지 않아서 나에게 이해가 잘되는 코드를 하나 찾았다.
array는 사용할때마다 랜덤한 값을 주고싶어 random 라이브러리를 호출했다.
# 1번째 방법(널리 사용되는 코드)
import random
array = random.sample(range(100), 10)
print(array)
def quick_sort(array, start, end):
if len(array) <= 1:
return array
pivot = start
left = start + 1
right = end
while left <= right:
while left <= end and array[left] <= array[pivot]:
left = left + 1
while right > start and array[right] >= array[pivot]:
right = right - 1
if left > right:
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)
👉🏽
random: [92, 5, 28, 75, 24, 32, 73, 53, 22, 46]
quick_sort: [5, 22, 24, 28, 32, 46, 53, 73, 75, 92]# 2번째 방법(개인적으로 이해가 잘 되는 코드)
import random
array = random.sample(range(100), 10)
print(array)
def quick_sort(array):
if len(array) <= 1:
return array
pivot = array[0]
left, right = list(), list()
for idx in range(1, len(array)):
if array[idx] < pivot:
left.append(array[idx])
else:
right.append(array[idx])
return quick_sort(left) + [pivot] + quick_sort(right)
print(quick_sort(array))
👉🏽
[71, 76, 32, 87, 68, 58, 96, 51, 97, 30]
[30, 32, 51, 58, 68, 71, 76, 87, 96, 97] # 3번째 방법(list Comprehension 사용한 코드)
import random
array = random.sample(range(100), 10)
print(array)
def quick_sort(array):
if len(array) <= 1:
return array
pivot = array[0]
tail = array[1:]
left=[x for x in tail if x <= pivot)]
right=[x for x in tail if x > pivot)]
return quick_sort(left) + [pivot] + quick_sort(right)
print(quick_sort(array))
👉🏽
[59, 86, 13, 24, 85, 93, 92, 17, 90, 28]
[13, 17, 24, 28, 59, 85, 86, 90, 92, 93] ⚡️ quick_sort의 시간복잡도
퀵 정렬의 평균 시간복잡도는 O(NlogN)이다.
왜 O(NlogN)인지 궁금하다면 여기를 참고하자.
다만, 여기서 중요한 점은 퀵 정렬의 시간복잡도가 최악인 경우는 O(N^2)이다.
이는 어제 배운 삽입 정렬, 선택 정렬의 시간복잡도와 동일하다.
데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높다. 하지만, 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, 이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작한다.
앞서 다룬 삽입 정렬은 이미 데이터가 정렬되어있을 경우에는 매우 빠르게 동작한다고 배웠는데, 퀵 정렬은 그와 반대된다는 점을 기억하자.
📍 count_sort(계수 정렬)
계수 정렬은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.
모든 데이터가 양의 정수인 상황을 가정했을때, 데이터의 개수가 N, 데이터 중 최댓값이 K일때, 계수 정렬은 최악의 경우에도 수행 시간 O(N+K)를 보장한다.
계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 만 사용할 수 있다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
계수정렬의 사용 조건은 다음과 같다.
- 가장 큰 데이터와 가장 작은 데이터의 차이가
1,000,000을 넘지 않을 때- 모든 데이터가 양의 정수일 때
- 동일한 데이터가 섞여있을 때
계수 정렬은 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크면 사용할 수 없는데, 그 이유는 다음과 같다. 계수 정렬을 이용할 때는 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야하기 때문이다.
예를 들어, 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000이라면 총 1,000,001개의 데이터가 들어갈 수 있는 리스트를 초기화해야한다. 여기서 1개를 더해주는 이유는 0부터 1,000,000까지는 총 1,000,001개의 수가 존재하기 때문이다.
때문에, 계수정렬은 공간복잡도는 높지만 조건이 맞으면 빠르게 동작한다는 장점을 갖고 있다.
array = [1, 3, 1, 2, 5, 6, 1]
count = [0] * (len(array) + 1)
for i in range(len(array)):
count[array[i]] = count[array[i]] + 1
for i in range(len(count)):
for j in range(count[i]):
print(i, end=' ')
👉🏽 1 1 1 2 3 5 6⚡️ count_sort의 시간복잡도
모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 대, 계수 정렬의 시간 복잡도는 O(N+K)이다.
따라서, 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다.
사실상 현존하는 정렬 알고리즘 중 기수 정렬(radix_sort)과 더불어 가장 빠르다고 할 수 있다.
⚡️ count_sort의 공간복잡도
계수정렬은 때에 따라 심각한 비효율성도 초래하는데, 데이터가 0과 999,999 단 2개만 있다고 가정할 때에도 계수 정렬은 리스트의 크기가 1,000,000 개가 되도록 선언해야한다.
따라서, 항상 사용할 수 있는 정렬 알고리즘은 아니며, 동일한 값을 가지는 데이터가 여러 개 등장할 대 적합하다.
다음은 지금까지 다룬 정렬 알고리즘을 비교한 표이다.
| 정렬 알고리즘 | 평균 시간 복잡도 | 최악의 시간 복잡도 | 공간 복잡도 | 특징 |
|---|---|---|---|---|
| 선택 정렬 | O(N^2) | O(N^2) | O(N) | 아이디어가 매우 간단하다. |
| 삽입 정렬 | O(N^2) | O(N^2) | O(N) | 데이터가 거의 정렬되어 있을 때는 가장 빠르다. |
| 퀵 정렬 | O(NlogN) | O(N^2) | O(N) | 대부분의 경우에 가장 적합하고, 충분히 빠르다. |
| 계수 정렬 | O(N+K) | O(N+K) | K값에 따라 다름 | 사용조건을 만족하면 매우 빠르게 동작한다. |
📍 파이썬의 정렬 라이브러리
파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다.
sorted()는 퀵 정렬과 동작 방식이 비슷한 병합 정렬(정확히는 병합 정렬 + 삽입 정렬을 합친 하이브리드 정렬 알고리즘)기반으로 만들어졌는데
병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간복잡도(O(NlogN))을 보장한다는 특징이 있다.
코딩테스트에서 정렬 알고리즘이 사용되는 경우를 일반적으로 3가지 문제 유형으로 나타낼 수 있다.
- 정렬 라이브러리로 풀 수 있는 문제: 정렬 라이브러리(
sort) 사용방법을 숙지하면 어렵지 않게 풀 수 있다.- 정렬 알고리즘의 원리에 대해서 물어보는 문제: 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
- 더 빠른 정렬이 필요한 문제: 퀵 정렬 기반의 문제는 풀 수 없으며, 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나, 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.
✏️ 결론
이렇게 해서 정렬 알고리즘의 4가지 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬을 알아봤다.
파이썬에서 접하기 쉬운 라이브러리인 sort()만 사용하다, 막상 동작원리를 알고나니까 기능 하나 구현하는것도 여러가지 케이스를 고려하면서 쉽게 만들어지는게 아니라고 생각했다.
같은 기능의 알고리즘인데도 불구하고 시간 복잡도, 공간 복잡도가 천차만별로 다른게 신기했고, 정렬문제를 많이 접하면서 언제 어떤 정렬 알고리즘으로 풀어야할지 고민을 많이 해봐야겠다.
