퀵 정렬
퀵 정렬(Quick Sort) 알고리즘
가장 많이 사용되는 알고리즘
퀵 정렬과 비교할 만큼 빠른 알고리즘으로는 병합 정렬 알고리즘이 있다.
기준(피벗)을 설정한 다음 큰 수와 작을 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작
피벗(Pivot) : 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 기준
가장 대표적인 분할 방식 중 하나인 호어 분할(Hoare Partition) 방식 기준(오름차순 정렬)
리스트의 첫 번째 데이터를 피벗으로 정한다.
왼쪽부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환한다.두 값의 위치가 엇갈린 경우, 작은 데이터와 피벗의 위치를 서로 교환한다.
피벗이 이동한 상태는 피벗을 기준으로 왼쪽과 오른쪽이 분할(Divide/Partition) 완료분할된 왼쪽과 오른쪽에 대해서 동일한 방식으로 정렬을 수행한다.
현재 리스트의 데이터 개수가 1개인 경우, 이미 정렬이 되어 있다고 간주, 분할이 불가능
정렬 완료
def quick_sort(array, start, end):
if start >= end: #원소가 1개인 경우 종료
return
pivot = start #피벗은 첫 번째 원소
left = start + 1 #탐색할 범위의 가장 왼쪽
right = end #탐색 할 범위의 가장 오른쪽
while left <= right: #left(큰 값)과 right(작은 값)의 위치가 엇갈리기 전까지
while left <= end and array[left] <= array[pivot]: #피벗보다 큰 값을 찾기까지 반복
left += 1 #피벗보다 큰 값의 위치를 left로
while right > start and array[right] >= array[pivot]: #피벗보다 작은 값을 찾기까지 반복
right -= 1 #피벗보다 작은 값의 위치를 right로
if left > right: #left(큰 값)과 right(작은 값)의 위치가 엇갈린 경우
array[pivot], array[right] = array[right], array[pivot] #작은 값(right)와 피벗의 위치 교체
else: #left(큰 값)과 right(작은 값)의 위치가 엇갈리지 않은 경우
array[left], array[right] = array[right], array[left] #큰 값(left)와 작은 값(right)의 위치 교체
#분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행
quick_sort(array, start, right-1) #왼쪽 부분
quick_sort(array, right+1, end) #오른쪽 부분
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
quick_sort(array, 0, len(array)-1)파이썬 문법활용 간단한 구현
def quick_sort2(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_sort2(left_side) + [pivot] + quick_sort2(right_side)
array1 = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
print(quick_sort2(array1))퀵 정렬의 시간 복잡도
퀵 정렬의 평균 시간 복잡도는 O(NlogN)
선택 정렬과 삽입 정렬의 O(N^2)에 비해 매우 빠른 편
데이터 개수가 N개 일때 분할이 이루어지는 횟수는 평균적으로 logN번 이루어진다.
최악의 경우 퀵 정렬의 시간 복잡도는 O(N^2)가 된다.
여기서 최악의 경우는 데이터가 이미 정렬되어 있는 경우
정렬되어 있는 데이터의 경우 삽입 정렬은 매우 빠르게 동작하고 퀵 정렬은 매우 느리게 동작
C++와 자바의 기본 정렬 라이브러리는 퀵 정렬을 기반으로 하지만 추가적인 로직을 통해 최악의 경우에도 O(NlogN)을 보장한다.
계수 정렬
계수 정렬(Count Sort) 알고리즘
특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
데이터의 개수가 N, 데이터 중 최댓값이 K일 때
최악의 경우에도 수행시간 O(N+K)를 보장한다.
하지만 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 만 사용 가능
일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적
데이터의 크기가 제한되어 있을 때에 한해 데이터 개수가 매우 많더라도 빠르게 동작
계수 정렬은 비교 기반의 정렬 알고리즘이 아니다.
모든 범위를 담을 수 있는 크기의 리스트(배열)을 선언하여 사용한다.
별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다.
가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성
리스트 인덱스가 모든 범위를 포함할 수 있도록 한다.
리스트의 모든 데이터는 0으로 초기화데이터의 값과 동일한 인덱스의 데이터를 1씩 증가
리스트의 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력
def count_sort(array):
sorted_array = []
count = [0] * (max(array) + 1) #array의 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
for i in range(len(array)):
count[array[i]] += 1 #각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(count)): #count 리스트에 기록된 정렬 정보 확인
for j in range(count[i]):
sorted_array.append(i) #count 리스트의 등장 횟수만큼 기록
return sorted_array
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8, 9, 1, 5, 7]
print(count_sort(array))
계수 정렬의 시간 복잡도
모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최댓값의 크기를 K라고 할 때,
계수 정렬의 시간 복잡도는 O(N+K)
앞에서 부터 데이터를 하나씩 확인하면서 리스트에 적절한 인덱스의 값을 1씩 증가
추후 리스트의 각 인덱스에 해당하는 값들을 확일할 때 데이터 중 최댓값의 크기만큼 반복 수행
데이터의 범위가 한정되어 있다면 효과적이며 항상 빠르게 동작
정령 알고리즘 중에서 기수 정렬(Radix Sort)과 더불어 가장 빠르다.
기수 정렬은 계수 정렬에 비해 동작은 느리나 처리할 수 있는 정수의 크기가 더 크다.
계수 정렬의 공간 복잡도
계수 정렬은 때에 따라서 심각한 비효율성을 초래
데이터의 개수에 비해 최솟값과 최댓값의 차이가 매우 클 때
데이터의 크기가 한정되어 있고 동일한 값을 가지는 데이터가 여러 개 등장(중복)할 때 적합하다.
데이터의 특성을 파악하기 어려운 경우 일반적으로 빠르게 동작하는 퀵 정렬을 이용하는 것이 적합
계수 정렬의 공간 복잡도는 O(N+K)
파이썬의 정렬 라이브러리
파이썬은 기본 정렬 라이브러리 sorted(list)함수를 제공한다.
병합 정렬을 기반으로 최악의 경우에도 시간 복잡도 O(NlogN)을 보장
리스트, 딕셔너리, 집합 자료형 등을 입력받아 정렬된 결과를 리스트로 반환
list.sort()를 통해 별도의 정렬된 리스트를 반환하지 않고 내부 원소를 바로 정렬 가능
두 함수 보두 key를 통해 정렬 기준을 제시 할 수 있다.
정렬 라이브러리의 시간 복잡도
정렬 라이브러리는 항상 최악의 경우에도 시간 복잡돋 O(NlogN)을 보장
별도의 요구가 없는 경우 정렬 라이브러리 사용 권장
데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 하는 경우 계수 정렬 고려
정렬 문제의 유형
- 정렬 라이브러리로 풀 수 있는 경우 : 정렬 라이브러리 사용
- 정렬 알고리즘의 원리에 대해서 물어보는 경우 : 여러 정렬 알고리즘의 원리 이해
- 더 빠른 정렬이 필요한 경우 : 계수 정렬 둥 다른 정렬 알고리즘 이용, 기존의 알고리즘의 구조적 개선
참고
나동빈(2020).이것이 취업을 위한 코딩 테스트다 with 파이썬.한빛미디어
