용어
-
merge sort(병합 정렬): 배열을 앞/뒤 두그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘
-> 안정적인 정렬 알고리즘, 시간 복잡도 O(nlogn) -
heap(힙)=partial ordered tree(부분 순서 트리): '부모의 값이 자식의 값보다 항상 크다(작다)'는 조건을 만족하는 완전 이진트리
-> 형제 간 대소관계는 정해져 있지 않음
-> index를 매길땐 부모->자식 순, 왼쪽->오른쪽 자식 순으로 매김
-> 따라서 a[i]의 주변 원소는 다음 관계를 가짐
-> 부모: a[(i-1)//2], 왼쪽 자식: a[2*i+1], 오른쪽 자식: a[2*i+2]
-> 힙에서 최댓값은 루트에 위치한다 -
heap sort(힙 정렬): 선택 정렬을 응용한 알고리즘으로, 힙의 루트를 꺼내고 나머지를 다시 힙으로 만드는 과정을 반복하는 알고리즘
-> 불안정적인 정렬 알고리즘, 시간 복잡도 O(nlogn) -
counting sort(도수 정렬)=distribution counting(분포수 세기): 원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘
-> 도수분포표의 원리를 활용해서 정렬
-> 원소를 비교할 필요가 없음
-> if문을 사용하지 않고 for문만 반복해서 정렬할 수 있음
-> 로직을 제대로 구현하면 안정적인 정렬 알고리즘, 시간/공간 복잡도 O(n)이지만 최대-최소값을 알고 있어야함
실습
병합 정렬
"""
기본 개념: 정렬할 배열을 두 그룹으로 나누고, 각 그룹 원소를 비교하고 새로운 배열에 저장하며 정렬.
=> 각 그룹의 원소 수가 1개가 될 때까지 나누는 과정을 재귀적으로 반복
"""
def _merge_sorted(lst_l: list, lst_r: list) -> list:
pointer_l, pointer_r, pointer = 0, 0, 0
n_l, n_r = len(lst_l), len(lst_r)
lst = [0]*(n_l + n_r)
if n_l > 1:
lst_l = _merge_sorted(lst_l[:n_l//2], lst_l[n_l//2:])
if n_r > 1:
lst_r = _merge_sorted(lst_r[:n_r//2], lst_r[n_r//2:])
while pointer_l < n_l and pointer_r < n_r:
if lst_l[pointer_l] <= lst_r[pointer_r]:
lst[pointer] = lst_l[pointer_l]
pointer_l += 1
else:
lst[pointer] = lst_r[pointer_r]
pointer_r += 1
pointer += 1
while pointer_l < n_l:
lst[pointer] = lst_l[pointer_l]
pointer_l += 1
pointer += 1
while pointer_r < n_r:
lst[pointer] = lst_r[pointer_r]
pointer_r += 1
pointer += 1
return lst
def merge_sorted(lst: list) -> list:
n = len(lst)
return _merge_sorted(lst[:n//2], lst[n//2:])
lst_1 = [1, 3, 9, 4, 11, 7, 88, 8, 6]
print(merge_sorted(lst_1))
# 실행결과 ==========================================
[1, 3, 4, 6, 7, 8, 9, 11, 88]힙 정렬
"""
기본 개념: 정렬할 배열을 힙으로 만들고, 힙에서 루트값을 순서대로 나열하는 식으로 정렬 진행
"""
def make_heap(lst: list) -> list:
temp = lst[0]
n = len(lst)
parent = 0
while parent < n//2:
child_l = parent * 2 + 1
child_r = child_l + 1
child = child_r if child_r < n and lst[child_r] > lst[child_l] else child_l
if temp >= lst[child]:
break
lst[parent] = lst[child]
parent = child
lst[parent] = temp
return lst
def heap_sorted(lst) -> list:
n = len(lst)
for i in range((n-1)//2, -1, -1):
lst[i:n] = make_heap(lst[i:n])
for i in range(n-1, 0, -1):
lst[0], lst[i] = lst[i], lst[0]
lst[0:i] = make_heap(lst[0:i])
return lst
lst_1 = [1, 3, 9, 4, 11, 7, 88, 8, 6]
print(heap_sorted(lst_1))
# 실행결과 ==========================================
[1, 3, 4, 6, 7, 8, 9, 11, 88]도수 정렬
"""
기본 개념: 누적 도수분포표를 만들고, 표의 인덱스에따라 재배치
"""
def counting_sorted(lst: list) -> list:
M = max(lst)
n = len(lst)
f = [0] * (M + 1)
new_lst = [0] * n
for i in range(n): f[lst[i]] += 1
for i in range(1, M+1): f[i] += f[i-1]
for i in range(n-1, -1, -1): f[lst[i]] -= 1; new_lst[f[lst[i]]] = lst[i]
return new_lst
lst_1 = [1, 3, 9, 4, 11, 7, 88, 8, 6]
print(counting_sorted(lst_1))
# 실행결과 ==========================================
[1, 3, 4, 6, 7, 8, 9, 11, 88]정리
드디어 8가지 정렬 알고리즘의 정리가 끝났다.
개인적으로 복잡한 재귀나 while문 없이 구현할 수 있는
도수 정렬이 가장 활용하기 좋아보였지만,
배열의 최대/최솟값 간격이 클수록
공간 복잡도가 커져 비효율적일 것 같았다.
필요에 따라 적절한 정렬 방법을 사용해야할 듯하다.
힙 정렬의 경우, 힙 구조를 1차원 배열로 표현하다보니
구현 로직이 잘 이해가지 않았다.
몇 번씩 구현해보며 손에 익혀야 할 듯하다.
마지막으로 8가지 정렬알고리즘을 표로 정리해보자.
| 시간 복잡도 | 공간 복잡도 | 안정성 | 특징 | |
|---|---|---|---|---|
| 버블 정렬 | O(n^2) | O(n) | o | 알고리즘이 매우 단순함 |
| 단순 선택 정렬 | O(n^2) | O(n) | x | 소수의 데이터를 추가하고 다시 정렬할 때 효율이 매우 떨어짐 |
| 단순 삽입 정렬 | O(n^2) | O(n) | o | 삽입 위치에 따라 이동 횟수가 많아질 수 있음 |
| 셸 정렬 | O(n^1.25) | O(n) | x | 그룹을 어떻게 나누냐에 따른 정렬 효율 차이가 심함 |
| 퀵 정렬 | O(nlogn) | O(n) | x | 일반적으로 많은 데이터에 대해 가장 빠르다고 알려진 방법 |
| 병합 정렬 | O(nlogn) | O(2*n) | o | 임시 배열이 필요해 추가 메모리가 요구됨 |
| 힙 정렬 | O(nlogn) | O(n) | x | 구현이 복잡함 |
| 도수 정렬 | O(a*n) | O(a*n) | o | 효율적인 정렬이 가능하지만, 최솟값/최댓값에 따라 사용 가능 여부가 결정됨. |
