비교 기반(Comparison-based) 알고리즘
- selection sort ( 선택 정렬 )
- bubble sort ( 버블 정렬 )
- insertion sort ( 삽입 정렬 )
- shell sort ( 쉘 정렬 )
- quick sort ( 퀵 정렬 )
- merge sort ( 합병 정렬 )
- heap sort ( 힙 정렬 )
Selection Sort
주어진 리스트 내에서 최솟값을 찾은 후, 가장 앞에 있는 값과 교체하면서 정렬하는 알고리즘으로, 각 정렬 단계가 마치 현재 단계에 들어가야 할 값을 리스트 내에서 찾아가는 과정처럼 보인다.
각 단계마다 배열의 좌측에서 배열의 정렬이 일어난다.
코드
def selection_sort(array: list[any]):
for i in range(len(array) - 1):
changed = False
min_idx: int = i
for j in range(i+1, len(array)):
if (array[min_idx] > array[j]):
min_idx = j
changed = True
array[i], array[min_idx] = array[min_idx], array[i]
print(array, changed, sep=',') # 주석 출력 단계. 필요 없으면 삭제.
if changed == False:
break
return array
arr0 = [20, 30, 10, 5, 10, 30, 15, 40]
print(selection_sort(arr0))- 시간 복잡도 : 평균, 최악 모두 O(n2)
- i 단계에서 n-i 번의 비교가 수행되므로, (n-1) + (n-2) + ... + 1 = (n-1) n/2 정도의 시간 복잡도가 발생한다.
- 제자리성 : 배열을 정렬에 상수 이상의 저장공간을 요구하지는 않으므로, 제자리성 성립.
- 안정성 : 무조건 인접한 값 사이에서 교환이 일어난다는 보장이 없으므로, 안정성이 떨어진다.
- ex ) Bbac => abBc 에서, b와 B의 위치가 변경된다. 안정성은 동일 원소에 대해 순서가 변하지 않아야 하므로, 삽입 정렬은 안정성이 낮다고 말할 수 있다.
Bubble Sort
인접한 두 원소를 검사하여 정렬하는 방법으로, 원소의 이동이 마치 거품이 수면으로 올라오는 듯한 모습을 보여 이런 이름을 지었다고 한다.
현재 원소 및 다음 원소의 크기를 비교하여, 만약 현재 원소가 더 크다면 둘의 자리를 바꾼다. 해당 과정을 계속하다 보면, 한 단계에 하나의 원소가 전체 배열의 우측에서 정렬된다.
코드
def bubble_sort(array: list[any]):
for i in range(len(array) - 1, -1, -1):
# 배열 길이 -> len(arr) 일때
# 인덱스 범위는 0 ~ len(arr) - 1
# 값은 idx ~ idx + 1 씩 비교하므로, 마지막 인덱스는 값을 비교하는 대상이 없음.
# 따라서, 마지막 인덱스 이전까지 항상 비교.
# 범위는 len(arr) - 2 ~ 0 까지
# 이때, 파이썬 range 는 stop index 바로 이전 인덱스까지 iterate 수행
# 그러므로 0 인덱스까지 보려면 -1 에서 값이 멈춰야 함.
changed = False
for j in range(0, i):
# i의 범위는 0~n-2 로, 각 단계의 마지막 원소는 포함하지 않는다.
if(array[j] > array[j+1]): # 버블정렬 : 다음원소가 더 크면 앞과 자리 교체
array[j], array[j+1] = array[j+1], array[j]
changed = True
print(array, changed, sep=', ') # 알고리즘 내용을 볼 필요 없다면 주석 처리.
if changed == False:
break
return array
arr1 = [20, 30, 10, 5, 10, 30, 15, 40]
print(bubble_sort(arr1))- 시간 복잡도 : O(n^2)
- 제자리성 : 상수 이상의 저장공간을 요구하지 않으므로, 제자리성 성립.
- 안정성 : 값의 변경이 인접 두 배열 사이에서만 발생하여 순서가 뒤집힐 일이 없으므로, 안정적이다.
Insertion Sort
정렬된 배열에 원소를 하나씩 추가하고, 정렬된 배열 내에서 해당 원소가 들어갈 자리를 찾는 방식으로 정렬을 수행하는 알고리즘으로, 원소의 제자리를 찾아 "삽입" 하는 과정에서 이름을 딴 정렬 방식이다.
코드
def selection_sort(array: list[any]):
for i in range(len(array) - 1):
changed = False
min_idx: int = i
for j in range(i+1, len(array)):
if (array[min_idx] > array[j]):
min_idx = j
changed = True
array[i], array[min_idx] = array[min_idx], array[i]
print(array, changed, sep=',') # 주석 출력 단계. 필요 없으면 삭제.
if changed == False:
break
return array
arr0 = [20, 30, 10, 5, 10, 30, 15, 40]
print(selection_sort(arr0))- 시간 복잡도 : O(n2)
- 제자리성 : 상수 크기 이상의 공간을 정렬에 사용하지 않는다.
- 안정성 : 인접 레코드 2개 사이에서만 값을 비교하므로, 순서가 변경되지 않아 안정성이 있다.
※ 평균 시간 복잡도 계산
Shell Sort
원소를 삽입하고 싶은 위치가 멀리 있더라도 한 번에 한자리씩 밖에 이동할 수 없는 삽입 정렬의 단점을 보완한 방식으로, 한번에 여러 인덱스를 뛰어넘는다는 특징을 가진다.
- 양수로 구성된 임의의 순열 h1, h2, h3... hk에 대해 각 값은 오름차순이다.
- 1 < i < k 에 대해 i < j 이면 hi는 hj 의 배수가 아니고, h1 = 1
- ex ) hi+1 = 3hi + 1
- i가 증가함에 따라 전체 배열을 hi 개로 나누어 삽입 정렬을 반복, 전체 배열을 1개 단위 나눠 정렬하게 된다.
- 시간 복잡도 : O(n2). h = 1, 4, 13, 40... 일 때 최악 시간 복잡도는 n3/2 으로 알려져 있다.
동일한 시간 복잡도라고 해도 다른 정렬 방식보다는 훨씬 빠르다고 한다. - 제자리성 : 상수 크기의 메모리만 이용하므로, 제자리성이 있다.
- 안정성 : 정렬이 거리가 먼 원소들 사이에서도 발생하기 때문에 불안정하다.
Quick Sort
Divide And Conquer(분할 정복) 방식의 알고리즘으로, 각 단계에서 피벗값에 대해 좌측은 피벗보다 작고, 우측은 피벗보다 크도록 배열을 구성하게 된다. 피벗 자체는 어느 위치를 사용하더라도 상관없으나, 간단하게는 항상 배열의 첫 번째 원소를 피벗으로 이용한다.
피벗을 배열의 첫 원소로 삼는 경우, 현재 배열의 좌측 및 우측에서 값을 읽어가면서 좌측에서는 피벗보다 큰 값을, 우측에서는 피벗보다 작은 값을 찾는다. 만약 두 값을 모두 발견하였을 때 좌측 값의 인덱스가 우측 값의 인덱스보다 작으면 두 값을 교환한다. 반대의 경우는 현재 배열을 전부 탐색하였고, 우측 값이 피벗보다 작은 값을 필연적으로 가리키고 있기 때문에 피벗과 우측에서 읽은 값의 위치를 변경하고, 피벗을 중심으로 양쪽에 대해 퀵 정렬을 다시 수행한다.
코드
from collections import namedtuple
from queue import SimpleQueue
from random import sample
def get_rand():
# 1 ~ 1000000 사이의 값 중 10개를 뽑는다.
return sample(range(1, 1000001), 10)
"""
@input arr : 대상 리스트
@input s_idx : 분할된 시작 인덱스
@input l_idx : 분할된 끝 인덱스
@return 피벗과 교환될 값.
"""
def partition(arr: list[int], s_idx: int, l_idx: int):
pivot_value = arr[s_idx]
pivot = s_idx # 정렬 기준이 되는 값의 인덱스.
left = s_idx + 1 # 피벗 자체는 정렬 대상이 아니므로, 1 더함
right = l_idx # 제일 우측 배열 요소
while True:
while left < l_idx and arr[left] < pivot_value:
# left가 배열 범위 안에 있음 + pivot_value보다 큰 값 탐색
# print("[Left]: ", arr[left])
left += 1
while right > s_idx and arr[right] > pivot_value:
# right가 배열 범위 안에 있음 + pivot_value보다 작은 값 탐색
# print("[Right]: ", arr[right])
right -= 1
if (left < right): # left < right라 배열 순서상 교환할 수 있다면,
arr[left], arr[right] = arr[right], arr[left] # 큰 값과 작은 값의 위치를 교환한다.
print("\t[Swapped] : ", arr, arr[left], arr[right]) # 주석
left += 1
right -= 1 # swap 거쳤으므로 고려하지 않음
else:
break
# left >= right이면, 서로 교환할 대상이 없고, 모든 원소를 이미 탐색함 -> while문 탈출
arr[pivot] = arr[right] # 피벗값과 right에 저장된 값을 서로 교환함
arr[right] = pivot_value
print("\t[Result] : ", arr) # 주석
return right # 현재 배열을 두 배열로 구분할 인덱스 반환
"""
비순환적 퀵 정렬 알고리즘.
큐에 인덱스를 저장한다.
quick_sort 자체는 한번만 실행된다!
@input arr 정렬의 대상이 되는 배열
"""
def quick_sort(arr: list[int]):
# 이름을 가진 튜플. 값을 left, right로 접근 가능해진다.
Idx = namedtuple('Idx', ['left', 'right']) # left,right 요소를 가지는 튜플을 만든다.
idx_queue: SimpleQueue[Idx] = SimpleQueue() # 인덱스를 관리하는 큐.
idx_queue.put(Idx(0, len(arr) - 1)) # 맨 처음 시점에 전체 배열을 sort 대상으로 넣는다
while not idx_queue.empty(): # 큐가 텅 빈게 아니면 (아직 정렬 대상이 남았다면)
left, right = idx_queue.get() # 큐에서 튜플 뽑아온다.
if left < right : # 배열의 길이가 1 이상이라면 -> 정렬할 게 있다면
print(f"[partition for {left} {right}]")
idx = partition(arr, left, right) # partition 함수를 이용하여 전체 배열을 분할 & sort
idx_queue.put(Idx(left, idx - 1)) # 큐에 좌측 배열 인덱스 넣음.
idx_queue.put(Idx(idx+1, right)) # 큐에 우측 배열 인덱스 넣음.
"""
순환적 퀵 정렬 알고리즘.
첫번째 값이 인덱스가 된다.
@input arr : 정렬 대상이 되는 배열
@input s_idx : 정렬의 시작 인덱스
@input l_idx : 정렬의 끝 인덱스
"""
def quick_sort_rec(arr: list[int], s_idx, l_idx):
if s_idx < l_idx:
print(f"[partition for {s_idx} {l_idx}]")
idx = partition(arr, s_idx, l_idx) # 피벗 인덱스는 교환 대상이 아니다!
quick_sort_rec(arr, s_idx, idx - 1) # 정렬된 원소 기준 왼쪽 정렬
quick_sort_rec(arr, idx + 1, l_idx) # 정렬된 원소 기준 오른쪽 정렬
arr1 = get_rand()
print(arr1)
quick_sort_rec(arr1, 0, len(arr1) - 1)
print(arr1)
arr2 = get_rand()
print(arr2)
quick_sort(arr2)
print(arr2)- 시간 복잡도
- 최선 : 분할 원소를 중심으로 배열이 정확히 둘로 나뉘는 경우. O(log2n)
- 최악 : 배열이 정렬되어 있는 경우. 배열이 정렬되어 있으면 피벗을 기준으로 좌측 혹은 우측으로 원소의 모든 값이 쏠리게 되어, 배열이 2개가 아니라 피벗을 제외한 하나로 나뉜다. 이 경우 O(n2) 의 복잡도를 지닌다.
- 평균 : O(n log2n)
- 최악의 경우가 될 가능성은 매우 낮고, 분할 원소 선택을 랜덤 하게 하여 방지할 수도 있다.
- 제자리성 : 배열의 값을 다른 공간에 저장하지는 않기 때문에 제자리 졍렬이기는 한데, 기본적으로 Recursive 하게 동작하기 때문에, 함수와 관련된 적절한 정보들을 따로 저장하게 된다. 이를 위해 순환 정렬 방식에서는 O(n), 비순환 정렬 방식에서는 O(log n)의 시간을 요구한다.
- 안정성 : 좌측 값과 우측 값이 항상 인접한 것은 아니므로, 교환 시 순서가 변경될 수도 있다.
# 시간 복잡도 계산
Merge Sort
quick sort처럼 Divide and Conquer(분할 정복) 알고리즘에 기반하며, 배열을 크기가 같은 두 부분 배열로 계속해서 나누고, 전체 배열이 다 나눠졌으면 이들을 합병하면서 정렬을 진행한다. quick sort와는 달리 항상 부분 배열의 크기가 거의 동일하다는 점이 특징이다.
병합되는 두 배열의 경우, 두 배열의 첫 번째 인덱스 값을 비교하면서, 더 작은 값을 삽입하는 과정을 반복한다. 만약 한 배열의 원소가 남는다면, 남은 배열을 병합된 배열 뒤에 통째로 가져다 붙인다.
"""
@input arr : 병합 대상이 되는 배열
@input left : 병합할 범위 첫번째 인덱스
@input right : 병합할 범위 마지막 인덱스
@input mid : 병합할 두 범위를 나누는 기준점.
"""
def merge(arr: list[int], left: int, right: int, mid: int):
temp_list: list[int] = [] # 두 배열에 저장된 값을 합병 및 저장할 때 사용되는 배열
a_idx = left # 첫번째 배열
b_idx = mid + 1 # 두번째 배열
if left == right: # 원소가 하나면 계산 안함
return
while a_idx <= mid and b_idx <= right: # 둘다 배열 인덱스 안에 잘 있을때
if arr[a_idx] < arr[b_idx]: # 첫번째 배열의 요소가 더 작을 때
temp_list.append(arr[a_idx])
a_idx += 1
else: # 두번째 배열의 요소가 더 작을 때
temp_list.append(arr[b_idx])
b_idx += 1
if a_idx > mid: # 첫번째 배열이 남지 않은 경우
temp_list.extend(arr[b_idx:right+1]) # 두번째 배열 통째로 붙여넣기
elif b_idx > right: # 두번째 배열이 남지 않은 경우
temp_list.extend(arr[a_idx:mid+1]) # 첫번째 배열 통째로 붙여넣기
assert(len(temp_list) == (right - left + 1))
# 새로 생기는 배열의 길이는 반드시 기존 범위와 같아야 한다.
temp_idx = 0 # 배열 복사를 위한 인덱스
for i in range(left, right + 1): # merge 끝나서 배열 복사
arr[i] = temp_list[temp_idx]
temp_idx += 1
print(arr)
"""
@input arr : 병합 대상이 되는 배열
@input left : 병합할 범위 첫번째 인덱스
@input right : 병합할 범위 마지막 인덱스
"""
def merge_sort_rec(arr: list[int], left: int, right: int):
if left < right: # 좌측 인덱스가 우측 인덱스보다는 작아야 의미가 있음.
mid = int((left + right)/2) # mid는 배열 나누는 중간 인덱스
# 인덱스를 기준으로 양쪽의 배열에 대해 recursive 하게 sort
merge_sort_rec(arr, left, mid)
merge_sort_rec(arr, mid+1, right)
merge(arr, left, right, mid) # 양쪽 배열을 merge
"""
주요 알고리즘?
for i = 1 ; i < n ; i *= 2
Left = 1
while left <= n
right = left + 2*1 - 1
if right > n
right = n
if mid <= n
merge(arr, left, right, mid)
left = right + 1
@input arr 정렬 대상이 되는 배열
"""
def merge_sort(arr: list[int]):
i : int = 1 # 두 배열이 있을 때, 한쪽 인덱스에서 mid 까지의 거리를 의미한다.
l_idx = len(arr) - 1 # 배열의 마지막 인덱스
# 알고리즘 작동 방식
# 크기가 1인 배열 단위부터 시작하여
# 점차 크기가 2의 배수인 배열을 병합하기 시작.
# 따라서, i는 매 순간마다 2배가 됨.
while i < l_idx : # i가 배열의 크기보다 작을 때
# 만약 i = l_idx이면 배열이 모두 정렬된 상태이므로, 상관 X
left = 0 # 전체 배열의 첫번째 인덱스는 0이다.
while left <= l_idx : # 좌측 인덱스가 마지막 인덱스 이하라면
right = left + i * 2 - 1
# right - left = 2i - 1 이므로, right = left + 2i - 1 이 된다.
# left <-- i -> mid <-- i --> right의 관계를 가진다.
if right > l_idx : # 배열의 길이를 초과하는 right가 설정되었다면,
right = l_idx # 배열을 정상화한다.
mid = left + i - 1 # mid의 위치는 left에서 i 만큼 떨어진 곳에 있음.
# 0 1 2 3 | 4 5 6 7 이면, mid 는 3 이 된다. 3은 0포함 4 거리에 있음.
if mid <= l_idx : # mid가 마지막 인덱스를 넘으면 안됨
merge(arr, left, right, mid)
left = right + 1 # 새로운 범위에 대해 병합을 시작한다
# right + 1 은 병합되지 않은 새로운 범위의 시작점을 의미한다.
i = i * 2 # 병합 범위를 2배로 키운다.
print("Recursive Merge Sort", '*' * 10)
arr1 = [30, 20, 40, 35, 5, 50, 45, 10, 25, 15]
print(arr1)
merge_sort_rec(arr1, 0, len(arr1)-1)
print("Nonrecursive Merge Sort", '*' * 10)
arr2 = [30, 20, 40, 35, 5, 50, 45, 10, 25, 15]
merge_sort(arr2)
# 시간 복잡도 : O(nlogn)
# 제자리성 : 입력 크기에 비례하는 행렬이 필요
# 안정성 : 가까운 2~4 ... 개의 원소끼리 정렬되므로, 안정적이다.- 시간 복잡도 : O(n logn)
- 제자리성 : 배열을 병합하는 과정에 두 배열의 크기 합에 비례하는 배열이 필요하다. 따라서 전체적으로 배열의 길이 n에 비례하는 공간 O(n) 이 요구되므로, 제자리성이 없다.
- 안정성 : 배열의 병합이 인접한 두 배열 사이에서 수행되므로, 순서를 바꾸지 않아 안정적이다.
#최악 시간 복잡도 계산
Heap Sort
힙은 완전이진트리 ( 가장 낮은 레벨은 왼쪽부터, 이외는 완전히 차 있는 이진트리 ) 에 기반을 두고 있는 자료구조로, 부모 노드의 키가 자식노드보다 크거나 같은 경우 (Max Heap) 혹은 부모 노드의 키가 자식노드보다 작거나 같은 경우 (Min Heap) 으로 나뉜다.
Heap Sort는 힙 자료구조를 이용한 정렬 방식으로, 1) 최대/최소 힙 의 형태로 배열을 구성하고 2) 전체 배열을 정렬 하는 2단계로 구성되어 있다.
- 힙 생성
- 삽입 & 재정비 방식 : 삽입 정렬처럼, 배열의 맨 끝에 노드를 삽입하고, root까지 키 값을 비교하며 힙을 복원
- 힙 변환 : 이진트리의 원소를 맨 아래부터 힙처럼 변형해가면서, 최종적으로 루트까지 힙으로 변경
- 정렬
: 최대 힙 기준으로, 루트에 저장된 값은 가장 큰 값이다. 해당 값을 정렬되지 않은 배열의 마지막 값과 바꾸고, 바뀐 루트를 기준으로 다시 힙을 만족하도록 노드의 위치를 변경한다. 각 단계에서 가장 큰 값이 정렬되지 않은 배열의 가장 마지막 위치에 존재하게 되므로, 정렬은 배열의 뒤에서부터 큰 순서대로 수행된다.
코드
make_heap1 은 삽입 & 재정비 방식에 대응되고, make_heap2는 이진 트리를 힙으로 변환하는 방식에 대응된다. make_heap2 와 힙을 정렬하는 과정은 상당히 유사하다.
# 0~n-1 까지
# 부모는 int((n-1)/2)
# 자식은 왼 + 1 오 + 2
# 배열에 원소를 하나씩 삽입하면서 만드는 방식
def make_heap1(arr: list[int]):
for i in range(1, len(arr)):
child = i
while child > 0:
parent = int((child - 1) / 2)
if(arr[parent] < arr[child]):
arr[parent], arr[child] = arr[child], arr[parent]
child = parent
else:
break
print(arr)
# 스왑하는 함수.
def swap_if(arr: list[int], x: int, y: int):
if arr[x] < arr[y]:
arr[x], arr[y] = arr[y], arr[x]
return y
else:
return x
"""
@input arr 대상 리스트
@input idx 현재 정렬 대상인 부모 노드
자식의 위치 :
left : 2n + 1 (0 - 1)
right : 2n + 2 (0 - 2)
자식이 더 크면 자식 노드 반환
부모가 더 크면 부모 노드 반환.
"""
def small_term_sort(arr: list[int], parent: int, last: int):
lc = 2 * parent + 1
rc = 2 * parent + 2
if rc <= last: # lc 및 rc가 모두 존재할 때
target = lc + int(arr[lc] < arr[rc])
# 더 큰 자식 노드를 선택하는 과정.
# lc가 더 크거나 같으면 0이 되고,
# rc가 더 크면 1이 됨.
# lc 와 rc 사이의 인덱스 차이는 1이다.
return swap_if(arr, parent, target)
elif lc <= last: # rc 는 last 보다 크고, lc는 last 이하. 즉 lc = last인 상황을 의미
return swap_if(arr, parent, lc)
else: # 자식 노드 없음
return parent
# 존재하는 배열을 마지막 원소부터 차례대로 정렬하는 방식.
# idx 위치부터 거슬러가며 배열 정렬 시도
# target을 찾는 마지막 위치는 last
def successive_pc_sort(arr:list[int], idx: int, last: int):
parent = idx
target = small_term_sort(arr, idx, last)
while parent != target: # 정렬이 발생했다면
parent = target # 자식 노드로 가서
target = small_term_sort(arr, parent, last) #자식노드 선에서 정렬한다.
def make_heap2(arr: list[int]):
last = len(arr) - 1
for i in range(len(arr) - 1, -1, -1):
successive_pc_sort(arr, i, last)
print(arr)
# 실제로 힙을 정렬하는 코드.
def heap_sort(arr: list[int]):
# i는 정렬 안된 배열의 마지막 인덱스
for i in range(len(arr) - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
print(arr)
successive_pc_sort(arr, 0, i - 1)
# 마지막 값은 이미 정렬된 상태임!
arr1 = [30, 10, 50, 60, 20, 70, 80]
print("Make Heap 1")
make_heap1(arr1)
print(arr1)
print("heap_sort")
heap_sort(arr1)
print(arr1)
arr2 = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
print("Make Heap 2")
make_heap2(arr2)
print("heap_sort")
print(arr2)
heap_sort(arr2)
print(arr2)
# 시간 복잡도 : 최악 O(nlogn)
# 제자리성 : 상수 크기의 메모리만 사용. 따로 배열에 비례하는 공간 필요 없음.
# 안정성 : 정렬의 띄어띄어 발생하므로, 불안정하다.- 시간 복잡도 : 최악의 경우 O(n logn).
- 제자리성 : 배열 정렬에 상수 크기 이상의 공간이 요구되지 않으므로, 제자리성이 있다.
- 안정성 : 정렬이 0번 인덱스와 마지막 인덱스를 교환하면서 수행되므로, 순서가 뒤바뀔 가능성이 높다. 안정성 X
시간 복잡도는 나중에 추가 ... insert / quick / merge
'CS > 알고리즘&문제풀이' 카테고리의 다른 글
| [python] 파이썬 re 모듈 동작 방식 (1) | 2023.03.13 |
|---|---|
| 최대 공약수, 최소 공배수 (0) | 2023.03.03 |
| [알고리즘] 분포기반 정렬 (0) | 2022.04.11 |
| [알고리즘] 정렬 00 : 정렬 개요 (0) | 2022.03.14 |
| [알고리즘] 알고리즘 이해 (0) | 2022.03.14 |
