지금까지 다뤄왔던 정렬 알고리즘들은 모두 최악의 경우의 시간 복잡도가 O(n^2)였다. 저번에 시간 복잡도에서 다뤘듯, 시간 복잡도가 기본적으로 O(n^2) 이상이 되면 비효율적이라고 한다. 연산시간이 오래 걸리기 때문이기도 하고, 데이터 수에 따라 수 초나 수 시간이 아닌 이론적으로 수 년이 걸릴 수도 있는 작업이 될 수 있기 때문이다. 그러나 정렬은 필수적인 작업이다. 따라서 이를 해결하기 위해 더 고급의 정렬 방식들이 등장하게 되었는데, 이 고급 정렬 방식들은 모두 O(n log n)의 시간 복잡도를 갖고 있다.
sort( )와 sorted( )
파이썬에수 흔히 사용되는 sort() 메서드는 원본 리스트를 정렬된 상태로 변환하며, sorted() 메서드는 원본의 변경 없이 정렬된 새로운 리스트를 반환한다. 이들은 매우 효율적인 팀소트 (Timsort) 알고리즘으로 구현되어 있으며, 최선의 경우 O(n) 의 시간 복잡도를 가지며 평균과 최악의 경우 O(n log n)의 시간 복잡도를 가지는 알고리즘이다. 파이썬의 기본 정렬 알고리즘이기도 하며, V8, Java SE7, Swift 등의 언어에서도 채용하고 있는 정렬 알고리즘이다.
sorted() 함수는 선택적 인수가 있으며 다양한 활용이 가능하다. 또한 사용자가 정의한 함수를 사용하여 정렬할 수도 있다.
병합 정렬
병합 정렬 (merge sort) 또는 합병 정렬은 리스트를 반으로 나누어, 정렬되지 않은 리스트를 만들고 이 작업을 반복하여 리스트의 크기가 1이 될 때 까지 계속 반으로 나눈 후, 병합 정렬 알고리즘을 호출하여 리스트를 정렬하고 병합한다. 병합 정렬은 안정적일 뿐만 아니라 대규모 데이터에 대해서도 속도가 빠르다. 배열의 경우 제자리 (in-place) 정렬이 되지 않기 때문에, 다른 알고리즘보다 훨씬 더 많은 메모리가 필요하며 공간 복잡도는 O(n)이다. 연결 리스트의 경우 별도의 저장 공간이 필요하지 않으므로 제자리 정렬이 가능하며 공간 복잡도는 O(log n)이다. 병합 정렬의 최선, 평균, 최악의 경우 시간 복잡도가 모두 O(n log n)이다. 병합 정렬은 보통의 경우 다음에 다룰 퀵 정렬 (quick sort) 보다 느리지만, 어떠한 상황에서도 시간 복잡도 O(n log n)을 보장하기 때문에 효율적이다.
데이터가 너무 커서 메모리에 넣지 못할 때, 병합 정렬은 좋은 선택이다. 하위 데이터 집합은 메모리에서 정렬할 수 있을 만큼 작아질 때까지 별도의 파일로 디스크에 넣을 수 있다. 병합은 그 후 각 파일에서 한 번에 하나의 요소들을 읽고 순서대로 최종 파일에 기록한다.
구현은 아래와 같이 될 것이다.
가) pop( ) 메서드를 사용한 병합 구현 (두 배열 모두 정렬되어 있음, merge)
나) 제자리 정렬을 구현하는 경우, 한 배열의 끝에 0이 채워져 있고, 다른 배열에는 첫 배열에서 끝에 0이 채워진 크기만큼의 요소가 있다. (merge_two_arrays_inplace)
다) 정렬된 파일을 병합 (merge_files)
이를 실제로 구현시키자면 아래와 같다.
1) pop( )을 이용한 병합 정렬 (하나의 배열 정렬)
def merge_sort(seq):
if len(seq) < 2:
return seq
mid = len(seq) // 2 # 중간점 찾기
left, right = seq[:mid], seq[mid:]
if len(left) > 1: # 재귀
left = merge_sort(left)
if len(right) > 1:
right = merge_sort(right)
result = []
while left and right: # 좌측 배열과 우측 배열 병합
if left[-1] >= right [-1]:
result.append(left.pop())
else:
result.append(right.pop())
result.reverse()
return (left or right) + result # 합쳐진 배열 반환
실행과 결과
print(merge_sort([6,3,5,7,9,5,3,2,1]))
# [1, 2, 3, 3, 5, 5, 6, 7, 9] 출력
2) 두 함수로 나누어 구현 (하나의 배열 정렬)
def merge_sort_sep(seq):
if len(seq) < 2:
return seq
mid = len(seq) // 2
left = merge_sort_sep(seq[:mid])
right = merge_sort_sep(seq[mid:])
return merge(left, right)
def merge(left, right):
if not left or not right:
return left or right
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # left와 right가 정렬되어 있다는 가정 하에 둘을 순차적으로 병합
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
if left[i:]:
result.append(left[i:])
if right[j:]:
result.append(right[j:])
return result
실행과 결과
print(merge_sort_sep([6,3,5,7,9,5,3,2,1]))
# [1, 2, 3, 3, 5, 5, 6, 7, 9] 출력
3) 두 정렬된 배열을 정렬, 시간 복잡도는 O(2n)
def merge_2n(left, right):
if not left or not right:
return left or right
result = []
while left and right:
if left[-1] >= right[-1]:
result.append(left.pop())
else:
result.append(right.pop())
ersult.reverse()
return (left or right) + result
실행과 결과
seq1 = [1,2,4,5,8,9]
seq2 = [2,4,6,6,8]
print(merge_2n(seq1, seq2))
# [1, 2, 2, 4, 4, 5, 6, 6, 8, 8, 9] 출력
4) 제자리 정렬로 구현
def merge_two_arrays_inplace(l1, l2):
if not l1 or not l2:
return l1 or l2
p2 = len(l2) - 1
p1 = len(l1) - len(l2) -1
p12 = len(l1) -1
while p2 >= 0 and p1 >= 0:
item_to_be_merged = l2[p2]
item_bigger_array = l1[p1]
if item_to_be_merged < item_bigger_array:
l1[p12] = item_bigger_array
p1 -= 1
else:
l1[p12] = item_to_be_merged
p2 -= 1
p12 -= 1
return l1
실행과 결과
seq1 = [1,2,4,5,8,9,0,0,0,0,0]
seq2 = [2,4,6,6,8]
merge_two_arrays_inplace(seq1, seq2)
print(seq1)
# [1, 2, 2, 4, 4, 5, 6, 6, 8, 8, 9] 출력
5) 파일 병합 (방금 정의했던 merge 함수를 적용)
def merge_files(list_files):
result = []
final = []
for filename in list_files:
aux = []
with open(filename, 'r') as file:
for line in file:
aux.append(int(line))
result.append(aux)
final.extend(result.pop())
for l in result:
final = merge(l, final)
return final
실행과 결과
list_files = ['./a.dat', './b.dat', './c.dat']
print(merge_files(list_files))
# [1, 1, 1, 2, 2, 2, 3, 3, 3, 5, 5, 7, 7, 9] 출력
퀵 정렬
퀵 정렬 (quick sort) 은 피벗 (pivot) 값을 잘 선택하는 것이 성능의 핵심이다. 리스트에서 기준이 되는 하나의 요소를 고르는데, 이를 피벗이라고 한다. 피벗 앞에는 피벗보다 작은 값, 뒤에는 피벗보다 큰 값이 오도록 피벗을 기준으로 리스트를 둘로 나눈 후 정렬한다. 이미 정렬된 리스트에서는 리스트의 중앙값 (median) 을 피벗으로 선택하는 것이 가장 적합한 선택이고, 정렬되지 않은 리스트 대부분에서도 다른 선택보다 나쁘지 않은 선택법이다.
분할 과정에서 n-1 요소의 영역을 생성하는 경우 (피벗이 최솟값 또는 최댓값일 때), 최악의 경우 시간 복잡도는 O(n^2) 이다. 최선의 경우는 두 개의 n/2 크기 리스트를 생성할 때이며, 이 최선의 경우와 평균 시간 복잡도는 O(n log n)이다. 퀵 정렬 알고리즘은 따라서 안정적이지 않다.
1) 한 함수로 구현 (캐시 사용)
피벗을 기준으로 왼쪽과 오른쪽을 각각 계속하여 퀵 정렬하여 구현한다. 참고로 enumerate(iterable) 함수는 각 시퀀스 항목마다 (index, item) 형식의 튜플을 만들어 배열로 반환하는 함수이다. 각 before와 after는 피벗의 앞과 뒤에 각각 피벗보다 작거나 같은 숫자 또는 피벗보다 큰 숫자들만 넣은 후 다시 그 숫자들을 퀵 정렬하며 재귀적으로 이를 처리하여 반환한다.
def quick_sort_cache(seq):
if len(seq) < 2:
return seq
ipivot = len(seq) // 2 # 피벗 인덱스 (그냥 중간에 있는 값)
pivot = seq[ipivot] # 피벗
before = [x for i, x in enumerate(seq) if x <= pivot and i != ipivot]
after = [x for i, x in enumerate(seq) if x > pivot and i != ipivot]
return quick_sort_cache(before) + [pivot] + quick_sort_cache(after)
실행과 결과
print(quick_sort_cache([2,6,8,3,2,3,5,6,1,2,9]))
# [1, 2, 2, 2, 3, 3, 5, 6, 6, 8, 9] 출력
2) 1의 퀵 정렬을 두 함수로 나누어 구현
def partition_devided(seq):
pivot, seq = seq[0], seq[1:] # (맨 처음에 있는 값)
before = []
after = []
before = [x for x in seq if x <= pivot]
after = [x for x in seq if x > pivot]
return before, pivot, after
def quick_sort_cache_devided(seq):
if len(seq) < 2:
return seq
before, pivot, after = partition_devided(seq)
return quick_sort_cache_devided(before) + [pivot] + quick_sort_cache_devided
실행과 결과
print(quick_sort_cache_devided([2,6,8,3,2,3,5,6,1,2,9]))
# [1, 2, 2, 2, 3, 3, 5, 6, 6, 8, 9] 출력
3) 두 함수로 나누어 구현 (캐시 사용 안함)
분할 (partition) 함수는 피벗을 기준으로 왼쪽과 오른쪽에 각각 피벗보다 더 작은 수들의 배열과 더 큰 수들의 배열, 그리고 그 중간에 피벗이 위치하도록 자리를 바꿔준다.
def partition(seq, start, end):
pivot = seq[start]
left = start + 1
right = end
done = False
while not done:
while left <= right and seq[left] <= pivot:
left += 1
while left <= right and pivot < seq[right]:
right -= 1
if right < left:
done = True
else:
seq[left], seq[right] = seq[right], seq[left]
seq[start], seq[right] = seq[right], seq[start]
return right
def quick_sort(seq, start, end):
if start < end:
pivot = partition(seq, start, end)
quick_sort(seq, start, pivot - 1)
quick_sort(seq, pivot + 1, end)
return seq
실행과 결과
seq = [2,6,8,3,2,3,5,6,1,2,9]
print(quick_sort(seq, 0, len(seq) - 1))
# [1, 2, 2, 2, 3, 3, 5, 6, 6, 8, 9] 출력
이 경우 정렬의 시작 지점과 끝 지점을 지정할 수 있다. 시작 지점과 끝 지점을 아래와 같이 지정해주면 그 사이의 배열만 정렬해 준다.
seq = [2,6,8,3,2,3,5,6,1,2,9]
print(quick_sort(seq, 5, 10))
# [2, 6, 8, 3, 2, 1, 2, 3, 5, 6, 9] 출력
정렬 과정을 그림으로 그려보면 아래와 같다.
초록색은 피벗으로 지정될 숫자, 노란색은 실제 피벗을 의미한다. 보면 깊이가 log n 보다 길어질 수 있음을 볼 수 있다. 퀵 정렬의 최악의 경우 시간 복잡도가 O(n^2)가 될 수 있는 이유를 볼 수 있다.
힙 정렬
힙 정렬 (heap sort) 은 정렬되지 않은 영역이 힙이라는 점을 제외하면 선택 정렬과 비슷하다. 힙에 대한 정보는 다음 글에서 찾아 보도록 하자.
https://lgphone.tistory.com/47
7-1. 추상 데이터 타입 (Abstract Data Type): 파이썬 자료구조와 알고리즘
추상 데이터 타입 (abstract data type, ADT) 은 유사한 동작을 가진 자료구조의 클래스에 대한 수학적 모델을 가리킨다. 자료구조는 크게 배열 기반의 연속 (continuation) 방식과 포인터 기반의 연결 (link)
lgphone.tistory.com
힙에서 루트가 아닌 다른 모든 노드는 부모 노드의 값보다 작은 값 (또는 가장 큰, 현재는 가장 작은, 즉 최소힙을 기준으로) 을 갖는다. 따라서 가장 작은 요소는 루트에 저장될 것이며, 루트의 하위 트리에는 루트보다 더 큰 값들이 포함될 것이다. 힙의 삽입 시간 복잡도는 O(1)이며, 힙 순서를 확인하는 데 드는 시간 복잡도는 O(log n)이다 (깊이). 힙을 순회하는 시간 복잡도는 O(n)이며, 힙 정렬은 파이썬의 내장 heapq 모듈을 사용하여 모든 값을 힙에 푸시한 뒤 한 번에 하나씩 가장 작은 값을 꺼내어 구현할 수 있다.
1) heap1 모듈을 이용한 구현
import heapq
def heap_sort1(seq):
heap = []
for value in seq:
heapq.heappush(heap, value)
return [heapq.heappop(heap) for i in range(len(heap))]
실행과 결과
print(heap_sort1([1,6,8,3,2,5,6,8,2]))
# [1, 2, 2, 3, 5, 6, 6, 8, 8] 출력
시간 복잡도 비교
| 알고리즘 | 최선 시간 복잡도 | 평균 시간 복잡도 | 최악 시간 복잡도 | 최악 공간 복잡도 |
| 퀵 정렬 | O(n log n) | O(n log n) | O(n^2) | O(n) |
| 병합 정렬 | O(n log n) | O(n log n) | O(n log n) | O(n) |
| 힙 정렬 | O(n log n) | O(n log n) | O(n log n) | O(1) |
| 거품 정렬 | O(n) | O(n^2) | O(n^2) | O(1) |
| 삽입 정렬 | O(n) | O(n^2) | O(n^2) | O(1) |
| 선택 정렬 | O(n^2) | O(n^2) | O(n^2) | O(1) |
| 버킷 정렬 | O(n+k) | O(n+k) | O(n^2) | O(nk) |
| 기수 정렬 | O(nk) | O(nk) | O(nk) | O(n+k) |
버킷 정렬과 기수 정렬
연습문제
가장 큰 항목 k개 찾기
퀵 정렬을 응용하여 리스트에서 k개의 가장 큰 항목을 찾아보자.
내 정답:
def partition(seq):
pivot, seq = seq[0], seq[1:]
before = []
after = []
before = [x for x in seq if x <= pivot]
after = [x for x in seq if x > pivot]
return before, pivot, after
def find_k_largest(seq, k):
# 먼저 피벗을 기준으로 오른쪽 왼쪽 분리
before, pivot, after = partition(seq)
after.append(pivot)
length_after = len(after)
result = []
if k == length_after: # k와 길이가 같다면 바로 반환하면 된다.
result.extend(after)
elif k < length_after: # k보다 길이가 길다면 잘라주어야 한다.
result.extend(find_k_largest(after, k))
else: # k보다 길이가 작다면 앞에서 잘라서 붙여준다.
result.extend(after)
result.extend(find_k_largest(before, k - length_after))
return result
print(find_k_largest([7,8,9,2,2,4,5,6,2,0,3,3,7], 4))
책의 정답:
import random
def swap(seq, x, y):
seq[x], seq[y] = seq[y], seq[x]
def quick_select(seq, k, left=None, right=None):
left = left or 0
right = right or len(seq) - 1
ipivot = random.randint(left, right)
pivot = seq[ipivot]
# 피벗을 정렬 범위 밖으로 이동
swap(seq, ipivot, right)
swapIndex, i = left, left
while i < right:
if seq[i] < pivot:
swap(seq, i, swapIndex)
swapIndex += 1
i += 1
# 피벗 위치 확정
swap(seq, right, swapIndex)
#피벗 위치 확인
rank = len(seq) - swapIndex
if k == rank:
return seq[swapIndex]
elif k < rank:
return quick_select(seq, k, left=swapIndex+1, right=right)
else:
return quick_select(seq, k, left=left, right=swapIndex-1)
def find_k_largest_answer_book(seq, k):
kth_largest = quick_select(seq, k)
result = []
for item in seq:
if item >= kth_largest:
result.append(item)
return result
이번엔 결과가 같지 않다. 각각 다음과 같이 나온다.
PS C:\Users\bumsu\Desktop\Python\DSA\Algorithm\9. 정렬> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/9. 정렬/eg_quick_find_k_largest.py"
[8, 9, 7, 7]
[7, 8, 9, 7]
위 결과는 내 정답의 결과, 아래 결과는 책의 정답의 결과이다. 내 정답은 관련 큰 항목이 발견될 때마다 extend 하는 방식으로 진행되기 때문에 순서가 뒤죽박죽이다. 반면 책은 먼저 k번째로 큰 수를 찾은 후, 해당 수와 비교하며 항목들을 걸러내기 때문에기존 순서가 그대로 유지된다. 그러나 책의 코드의 경우 아래와 같은 배열을 넣어줄 경우 아래와 같이 결과가 반환된다.
실행
print(find_k_largest([7,7,7,7,8,9,2,2,4,5,6,2,0,3,3,7], 4))
print(find_k_largest_answer_book([7,7,7,7,8,9,2,2,4,5,6,2,0,3,3,7], 4))
결과
PS C:\Users\bumsu\Desktop\Python\DSA\Algorithm\9. 정렬> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/9. 정렬/eg_quick_find_k_largest.py"
[8, 9, 7, 7]
[7, 7, 7, 7, 7, 8, 9]
책의 정답의 경우 k번째로 큰 항목을 찾아 걸러내는 방식이기 때문에 그 항목의 개수가 많다면 위와 같은 현상이 발생한다. 반면 내 정답의 경우 반환될 배열의 길이를 기준으로 판단하기 때문에 k개의 가장 큰 항목을 구하는 문제의 정답으로썬 내 정답이 이번엔 책의 정답보다 오히려 더 정답에 근접하다고 볼 수 있을 것 같다. 그러나 기존의 순서를 지키는 정렬이 필요하다면 책의 정답을 채용할 수 있을 것이며, 코드를 어느정도 손봐준다면 책의 정답이 더 유용하게 쓰일 수 있을 것이다.
출처
파이썬 자료구조와 알고리즘 - 한빛미디어, 미아 스타인
'Python > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 10-2. 검색 연습문제 (Searching Examples): 파이썬 자료구조와 알고리즘 (0) | 2020.08.09 |
|---|---|
| 10-1. 검색 (Searching): 파이썬 자료구조와 알고리즘 (0) | 2020.08.09 |
| 9-1. 2차 정렬과 선형 정렬 (Quadratic and Linear Sorting) : 파이썬 자료구조와 알고리즘 (0) | 2020.08.06 |
| 8. 점근적 분석 (Asymptotic Analysis): 파이썬 자료구조와 알고리즘 (0) | 2020.08.04 |
| 7-2-2. 큐, 우선순위 큐, 힙, 연결 리스트 예제 (Other Types Examples): 파이썬 자료구조와 알고리즘 (0) | 2020.08.03 |
