CS 개념 정리
[CS 개념 정리] 합병 정렬, 퀵 정렬, 힙 정렬
Squidward
2022. 10. 25. 17:44
합병 정렬 (Merge sort) 란?
: 분할정복과 재귀알고리즘을 이용한 정렬로, 주어진 배열에서 수가 하나밖에 남지 않을 때까지 계속 둘로 쪼갠 후에 다시 크기순으로 재배열(정렬) 하며 원래 크기의 배열로 합치는 정렬방법입니다.
합병정렬의 시간복잡도 : O(nlogn)
합병정렬의 공간복잡도 : O(N)
구현 - 파이썬 코드
sublist = [3,23,7,12,5,8,1]
def mergeSort(list):
size = len(list)
if size <= 1: return list
mid = len(list) // 2
left = mergeSort(list[:mid])
right = mergeSort(list[mid:])
merged = merge(left, right)
return merged
def merge(list1, list2):
merged = []
while len(list1) > 0 and len(list2) > 0:
if list1[0] <= list2[0]:
merged.append(list1.pop(0))
else:
merged.append(list2.pop(0))
if len(list1) > 0:
merged += list1
if len(list2) > 0:
merged += list2
return merged
sorted = mergeSort(sublist)
print (sorted)구현 - 임시배열을 사용하지 않는 효율성 높은 코드
from unsorted import numbers
sublist = [3,23,7,12,5,8,1]
def mergeSort(list,p,q):
if p>= q: return
mid = (p + q) // 2
mergeSort(list, p, mid)
mergeSort(list, mid+ 1, q)
merge(list, p, mid + 1, q)
def merge(list, left, right, end):
merged = []
l, r = left, right
while l < right and r <= end:
if list[l] <= list[r]:
merged.append(list[l])
l +=1
else:
merged.append(list[r])
r +=1
while l < right:
merged.append(list[l])
l +=1
while r <= end:
merged.append(list[r])
r+=1
l = left
for n in merged:
list[l] = n
l +=1
print(sublist)
sorted = mergeSort(sublist, 0, len(sublist) - 1)
print(sublist)퀵 정렬이란?
: 피벗(pivot)이라는 기준 데이터를 설정하고 그 기준 데이터보다 큰 데이터와 작은 데이터의 위치를 변경하는 정렬 방법입니다.
퀵 정렬은 데이터 간의 비교만으로 정렬을 수행하는 비교 정렬 중 하나로 빠릅니다.
[파이썬의 장점을 살린 퀵정렬 - 간결함]
array = [3,23,7,12,5,8,1]
def quick_sort(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_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(array))퀵정렬의 시간 복잡도 : O(nlogn)
퀵정렬의 공간 복잡도 : O(log n)
힙 정렬이란?
: 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법
자료구조 ‘힙(heap)’
: 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
: 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조
내림차순 정렬을 위해서는 최대힙을 구성하고 오름차순 정렬을 위해서는 최소힙을 구성해야 한다.
최대힙: 부모노드의 키값이 자식노드의 키값보다 항상 큰 경우
최소힙: 부모노드의 키값이 자식노드의 키값보다 항상 작은 경우
[ max 힙 정렬 과정 ] - 두 가지 과정으로 분류
1) max heap 삽입
: 새로운 요소가 들어올 때, 대소에 맞게 부모노드와 자식노드를 교환한다. (max heap은 부모 노드가 자식노드보다 무조건 커야함)
2) max heap 삭제 ( = 최대값 노드를 하나씩 삭제하며 가져와서 정렬하는 것)
: 루트 노드를 삭제 후에는 루트 노드의 자리에 힙의 마지막 노드를 가져와야한다.
이때 대소에 맞게 다시 부모노드와 자식노드를 교환하며 힙을 재구성한다.
1) max heap 삽입
2) max heap 삭제
힙정렬 시간복잡도 : O(nlogn)
[구현 코드] - 파이썬
def heapify(li, idx, n):
# li : 힙으로 만들고자 하는 배열
# idx : 선택된 노드
# n : 힙의 범위
# 자식의 왼쪽 노드를 의미
left = idx * 2
# 자식의 오른쪽 노드를 의미
right = idx * 2 + 1
s_idx = idx
# 선택 노드, 선택 노드의 양 자식 중 가장 작은 값을 찾는 과정
if left <= n and li[s_idx] > li[left]:
s_idx = left
if right <= n and li[s_idx] > li[right]:
s_idx = right
# 선택 노드와 자식 노드의 위치가 바뀌어야 한다면
if s_idx != idx:
# 부모 자식 위치 변경
li[idx], li[s_idx] = li[s_idx], li[idx]
# 부모가 자식으로 내려간 이후에도, 그 자식과 바뀔 여지가 있는지 재귀로 체크
return heapify(li, s_idx, n)
def heap_sort(array):
n = len(array)
# 루트노드는 index 1부터 시작하므로, 앞에 0 원소를 추가한 채로 시작.
array = [0] + array
# 최종 정렬된 원소들이 저장될 배열
ans = []
# Min Heap을 만드는 과정
for i in range(n // 2, 0, -1):
heapify(array, i, n)
# 루트 노드 원소를 정렬 배열에 저장, heapify 반복
for i in range(n, 0, -1):
ans.append(array[1])
array[i], array[1] = array[1], array[i]
heapify(array, 1, i - 1)
# array[1:]를 얻으면 오름차순 정렬 배열을 얻을 수 있음
return ans
print(heap_sort([5, 2, 1]))
728x90