정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것이라고 한다. 정렬 알고리즘은 이진 탐색의 전처리과정이기도 하고, 가장 많이 사용하는 알고리즘 중 하나이다.
내림차순의 정렬은 단순히 오름차순으로 정렬한 것을 반대로 뒤집으면 되므로 시간복잡도 O(N)으로 수행할 수 있다.
또한 현대의 정렬 알고리즘은 이미 정립되어 있기 때문에, 더 이상의 큰 개선이 없다면 외워서 잘 풀 수 있는 문제라고 한다.
알고 있는 개념은 최대한 간단히 정리했다.
선택 정렬
가장 작은 것을 '선택'하여 정렬하는 방식이다.
시간복잡도는 O(N^2). N이 10000을 넘어가면 수행시간이 급격히 감소한다고 한다.
# 선택정렬
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)
다른 정렬 알고리즘에 비해 매우 비효율적이지만 코테에서 가장 작은 데이터를 찾는 일이 많으므로 숙지하자.
삽입 정렬
특정 데이터를 특정 위치에 '삽입'하여 정렬하는 방식이다. 적절한 데이터가 삽입되기 전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 중요한 점은 데이터가 거의 정렬되어 있을 때 엄청나게 효율적이라는 것이다.
# 삽입정렬
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):
if array[j] < array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
else:
break
print(array)시간복잡도는 O(N^2)이며 데이터가 거의 정렬되어 있을 경우 O(N)으로 매우 효율적이다.
퀵 정렬
피벗을 사용하여 이것보다 큰 데이터와 작은 데이터의 위치를 바꿔서 '빠르게' 정렬하는 방식이다. 피벗을 설정하고 리스트를 분할하는 방법에 따라 퀵 정렬이 구분된다고 한다. 책에서는 Hoare 분할 방식을 기준으로 설명이 나와있다.
특징으로는 재귀 함수 형태로 작성할 수 있다는 것이며, 이 때 재귀의 종료 조건은 현재 리스트의 데이터 수가 1개인 경우이다.
# 퀵정렬
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick(array, start, end):
if start >= end:
return
pivot = start
right = end
left = start+1
while left <= right:
#왼쪽에서 부터 피벗보다 작은 수를 찾음. 피벗 이후에 끝까지 갈 수 있으므로 left <= end
while left <= end and array[left] <= array[pivot]:
left += 1
#오른쪽에서 부터 피벗보다 큰 수를 찾음. 피벗 이전까지 찾아야 하므로 right > start
while right > start and array[right] >= array[pivot]:
right -= 1
#큰 값과 작은 값이 엇갈린 경우, 작은 값과 피벗의 위치를 바꿈.
if left > right:
array[right], array[pivot] = array[pivot], array[right]
else:
array[left], array[right] = array[right], array[left]
#분할 후 왼쪽/오른쪽에서 다시 퀵 정렬 수행
quick(array, start, right - 1)
quick(array, right + 1, end)
quick(array, 0, len(array)-1)
print(array)퀵 정렬의 시간 복잡도는 O(NlogN)으로 삽입과 선택 정렬에 비해 매우 효율적이지만 데이터가 이미 정렬되어 있는 경우 O(N^2)로 매우 느리게 동작한다.
삽입 정렬: 데이터가 정렬되어 있는 경우 빠름
<>
퀵 정렬: 데이터가 정렬되어 있으면 느림
또한 밑의 코드는 파이썬의 장점을 살려서 만든 퀵 정렬이라고 한다.
#파이썬 장점을 살린 퀵정렬
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick(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(left_side) + [pivot] + quick(right_side)
print(quick(array))먼저 피벗을 정한 후, 피벗을 뺀 나머지 리스트인 tail에서 리스트 컴프리헨션을 사용하여 피벗보다 작은 원소만 담긴 left_side와 큰 원소만 담긴 right_side를 구한다. 그 후 피벗을 가운데에 집어넣는다.
피벗과 데이터를 더 많이 비교하므로 시간 면에서는 좀 더 비효율적이라고 한다.
계수 정렬
계수 정렬은 처음 보는 개념이었다. 이는 데이터의 크기가 제한되어 있고, 정수 형태로 표현할 수 있을 때만 사용할 수 있다. 또한 중복되는 데이터가 많을 경우 매우 빠른 정렬 알고리즘이다.
즉 데이터가 실수형이면 사용하기 어려우며 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적이다.
정렬 방식은 모든 범위를 담을 수 있는 크기의 리스트를 만들고 리스트의 각 원소별로 등장한 횟수만큼 원소를 써내려가는 방식이다.
시간복잡도는 데이터의 개수가 N, 데이터의 최대값이 K일 경우 O(N+K)라고 한다. 하지만 데이터가 0과 999999 두 개만 존재할 경우 쓸데 없이 리스트 크기를 1,000,000개가 되도록 지정해야 하므로 사용할 때 잘 고려해야한다.
#계수정렬
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
#가장 큰 수까지 포함해야 하므로 max(array) + 1
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 = ' ')일반적인 경우 퀵 정렬이 평균적으로 가장 빠르기 때문에 데이터의 특성을 파악할 수 없을 때는 퀵 정렬을 사용하는 것이 유리하고, 위와 같은 경우라면 계수 정렬이 유리하다고 한다.
코테 정렬 문제 유형
- 정렬 라이브러리로 풀 수 있는 문제: sorted나 sort 등의 기본 라이브러리만 사용할 줄 알면 풀 수 있다.
- 정렬 알고리즘의 원리에 대해 물어보는 문제: 선택/삽입/퀵 정렬 등의 개념을 숙지해야 풀 수 있다.
- 더 빠른 정렬이 필요한 문제: 퀵 정렬 기반의 기법으로는 풀 수 없고 기존의 정렬 알고리즘을 개선하거나 계수 정렬 등의 다른 알고리즘을 사용해야 풀 수 있다.
