1. 버블 정렬 (Bubble Sort)
버블정렬은 서로 인접해 있는 요소 간의 대소 비교를 통해 정렬한다. 버블 정렬은 정렬 알고리즘 중 가장 단순한 알고리즘으로, 단순한 만큼 비효율적이다. 시간 복잡도가 최고, 평균, 최악 모두 $O(n^2)$이며 공간복잡도는 하나의 배열만 사용하므로 $O(n)$을 가진다. 동작 방식은 인접한 두 요소간의 대소 비교를 진행한다.
만약 배열에 n개의 요소가 있을 경우 1번째 원소 vs 2번째 원소를 비교하고 2번째 원소 vs 3번째 원소를 비교하고, ... n-1번째 원소 vs n번째 요소를 비교하면 1회전 비교가 끝난다. 1회전이 끝나면 가장 큰 원소는 맨 뒤에 위치하게 되므로 2회전 비교에서는 제외된다. 마찬가지로 두 번째로 큰 원소는 가장 큰 원소 앞에 위치하게 되므로 3회전 비교에서는 제외된다. 즉 버블 정렬을 1회 수행할 때 마다 정렬해야 할 원소가 하나씩 줄어든다. 이를 코드로 구현하면 아래와 같다.
def bubble_sort(array):
""" Best: O(n^2) Average: O(n^2) Worst: O(n^2) | O(n) """
for i in range(len(array)):
for j in range(len(array)-i-1):
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j]
return array
2. 삽입 정렬 (Insert Sort)
삽입 정렬이란 정렬을 진행할 원소의 index보다 낮은 곳에 있는 원소들을 탐색하며 알맞은 위치에 삽입해주는 정렬 알고리즘이다. 동작 방식은 두 번째 index부터 시작한다. 그 이유는 첫 번째 index는 비교할 원소가 없기 때문이다. 알고리즘이 동작하는 동안 계속해서 정렬이 진행되므로 반드시 맨 왼쪽 index까지 탐색하지 않아도 된다는 장점이 있다. 모두 정렬되어 있는 Optimal한 경우 모든 원소가 한 번씩만 비교되므로 $O(n)$의 시간 복잡도를 가진다. 또한 공간복잡도는, 하나의 배열에서 정렬이 이루어지므로 $O(n)$이다.
삽입 정렬을 코드로 구현하면 아래와 같다. 첫 번째 for문은 정렬할 원소를 차례대로 선택하는 것이며, 두 번째 for문은 정렬할 원소보다 아래 인덱스에 있는 요소와 비교하기 위함이다.
def insert_sort(array):
""" Best: O(n) Average: O(n^2) Worst: O(n^2) | O(n) """
for i in range(1, len(array)):
for j in range(i, 0, -1):
if array[j-1] > array[j]:
array[j-1], array[j] = array[j], array[j-1]
return array
삽입 정렬을 최적화할 경우 아래 코드와 같다.
def insert_sort(array):
for i in range(1, len(array)):
j = i
while j > 0 and array[j-1] > array[j]:
array[j-1], array[j] = array[j], array[j-1]
j -= 1
return array
3. 선택 정렬 (Selection Sort)
선택 정렬이란 배열에서 최소값을 반복적으로 찾아 정렬하는 알고리즘이다.
시간복잡도 최선, 평균, 최악 모두 $O(n^2)$에 해당하는 비효율적인 알고리즘으로 정렬 여부와 상관없이 모든 경우의 수를 전부 확인한다. 동작방식 3단계로 구성된다. 첫 번째는 주어진 배열에서 최소값을 찾는다. 두 번째는 최소값을 맨 앞의 값과 바꾼다. 세 번째는 바꿔준 맨 앞 값을 제외한 나머지 원소를 동일한 방법으로 바꿔준다. 이를 알고리즘으로 나타내면 다음과 같다.
def selection_sort(array):
""" Best: O(n^2) Average: O(n^2) Worst: O(n^2) | O(N^2) """
for i in range(len(array)):
idx = i
for j in range(i+1, len(array)):
if array[idx] > array[j]:
idx = j
array[idx], array[i] = array[i], array[idx]
return array
덧붙여 선택 정렬은 크게 2가지로 최소 선택 정렬과, 최대 선택 정렬이 있다. 최소는 위와 같이 오름차순으로 정렬하는 것이고 최대는 위와 반대로 내림차순으로 정렬하는 것이다.
4. 퀵 정렬 (Quick Sort)
퀵 정렬은 분할정복법과 재귀를 사용해 정렬하는 알고리즘이다.
퀵 정렬에는 피봇(Pivot)이라는 개념이 사용된다. 피봇은 한 마디로 정렬 될 기준 원소를 뜻한다. 피봇 선택 방법에 따라 퀵 정렬의 성능이 달라질 수 있다. 최적의 피봇 선택이 어려우므로 임의 선택을 해야 한다. 보통 배열의 첫 번째 값이나 중앙 값을 선택한다. 퀵 정렬의 동작방식은 다음과 같다. 가령 예를 들어 배열 [5, 6, 1, 4, 2, 3, 7]이 있고, 피봇을 임의로 4를 선택했다 가정하자. 이후 4를 기준으로 작은 것은 왼쪽으로 큰 것은 오른쪽으로 보내 [1, 2, 3] < 4 < [5, 6, 7]를 생성한다. 다시 왼쪽에서부터 임의의 피봇 2를 설정하여 [1] < 2 < [3]을 생성하고 오른쪽에선 임의의 피봇 6를 설정하여 [5] < 6 < [7]로 나눈다. 만약 배열 길이가 1이 된다면 가장 정렬 완료된 것이므로 분할된 배열을 합쳐 줌으로써 정렬을 마친다. 이를 알고리즘으로 구현하면 다음 코드와 같다.
def quick_sort(array : list) -> list:
""" Best: O(nlogn) Average: O(nlogn) Worst: O(n^2) | O(nlogn) """
if len(array) <= 1:
return array
pivot = array[len(array) // 2]
small, equal, big = [], [], []
for num in array:
if num < pivot:
small.append(num)
elif num > pivot:
big.append(num)
else:
equal.append(num)
return quick_sort(small) + equal + quick_sort(big)
5. 병합 정렬 (Merge Sort)
병합 정렬은 분할정복과 재귀 알고리즘을 사용하는 정렬 알고리즘이다.
퀵 정렬과 함께 두 개의 알고리즘이 사용된다는 측면에서 공통점을 가진다. 하지만 차이점은 퀵 정렬이 피봇 선택 이후 피봇 기준으로 대소를 비교하는 반면, 병합 정렬은 배열을 원소가 하나만 남을 때 까지 계속 이분할 한 다음, 대소관계를 고려하여 다시 재배열 하며 원래 크기의 배열로 병합한다. 예를 들어 배열 [6, 5, 1, 4, 3, 2, 8, 7]이 있을 때, 첫 번째로 [6, 5, 1, 4]와 [3, 2, 8, 7]로 분리한다. 두 번째로 [6, 5], [1, 4], [3, 2], [8, 7]로 나눈다. 세 번째로 [6], [5], [1], [4], [3], [2], [8], [7]로 나눈다. 이렇게 모든 원소가 분리되면 대소 관계를 고려하여 병합 과정을 거친다. 첫 번째로 [5, 6], [1, 4], [2, 3], [7, 8]이 되며, 두 번째는 [1, 4, 5, 6], [2, 3, 7, 8]이 된다. 마지막으로 하나의 배열로 병합되면서 [1, 2, 3, 4, 5, 6, 7, 8]와 같이 정렬이 완료되면서 알고리즘이 종료된다. 이를 코드로 나타내면 아래 코드와 같다.
def merge_sort(array: list) -> list:
""" Best: O(nlogn) Average: O(nlogn) Worst: O(nlogn) | O(n) """
if len(array) < 2:
return array
mid = len(array)//2
low = merge_sort(array[:mid])
high = merge_sort(array[mid:])
merged_array = []
l, h = 0, 0
while l < len(low) and h < len(high):
if low[l] < high[h]:
merged_array.append(low[l])
l += 1
else:
merged_array.append(high[h])
h += 1
merged_array += low[l:]
merged_array += high[h:]
return merged_array
시간 복잡도의 경우 최선, 평균, 최악 모두 $O(nlogn)$이며 공간 복잡도의 경우 정렬된 원소를 담을 배열이 하나 필요로 하므로 $O(n)$.
6. 힙 정렬 (Heap Sort)
힙이란 트리 기반의 자료구조로서, 두 개의 노드를 가진 완전 이진 트리를 의미한다. 따라서 힙 정렬이란 완전 이진 트리를 기반으로 하는 정렬 알고리즘이다. 힙의 분류는 크게 최대 힙과 최소 힙 두 가지로 나뉜다. 최대 힙은 내림차순 정렬에 사용하며, 최소 힙은 오름차순 정렬에 사용한다.
최대힙의 경우 부모 노드가 항상 자식노드 보다 크다는 특징을 가진다. 반대로 최소힙의 경우 부모 노드가 항상 자식노드 보다 작다는 특징을 가진다. 이러한 힙에서 오해할 수 있는 특징은 힙은 정렬된 구조가 아니다. 부모 자식 간의 대소 관계만 나타내며 좌우 관계는 나타내지 않기 때문이다. 예를 들어 최소 힙에서 대부분 왼쪽 노드가 오른쪽 노드보다 작지만 4의 자식 노드인 7과 5는 왼쪽이 오른쪽보다 크다.
힙은 완전 이진 트리기 때문에 적절히 중간 레벨의 노드를 추출하면 중앙값에 가까운 값을 근사치로 빠르게 추출할 수 있다는 장점을 갖고 있다. 때문에 힙은 배열에 순서대로 표현하기 적합하다. 또한 균형을 유지하려는 특징 때문에 힙은 우선순위 큐, 다익스트라, 힙 정렬, 프림 알고리즘에 활용된다. 특히 힙 덕분에 다익스트라 알고리즘의 시간 복잡도는 $O(V^2)$에서 O(ElogV)로 줄어들 수 있었다.
힙 정렬 과정을 최대힙을 기준으로 우선 간략히 보자면 아래 GIF와 같다.
최대 힙의 동작을 코드로 작성하면 아래와 같다.
def heap_sort(array : list) -> list:
""" Best: O(nlogn) Average: O(nlogn) Worst: O(nlogn) | O(nlogn) """
n = len(array)
for i in range(n//2-1, -1, -1):
heapify(array, i, n)
for i in range(n-1, 0, -1):
array[0], array[i] = array[i], array[0]
heapify(array, 0, i)
return array
def heapify(array : list, index : int, heap_size : int) -> None:
smallest = index
left = (2 * index) + 1
right = (2 * index) + 2
if left < heap_size and array[left] < array[smallest]:
smallest = left
if right < heap_size and array[right] < array[smallest]:
smallest = right
if smallest != index:
array[smallest], array[index] = array[index], array[smallest]
heapify(array, smallest, heap_size)
if __name__ == "__main__":
array = [1, 10, 5, 5, 2, 9, 8, 7, 6, 4, 0, 3, 2, 9]
print (heap_sort(array)) # [10, 9, 9, 8, 7, 6, 5, 5, 4, 3, 2, 2, 1, 0]
먼저 heapify 함수의 역할은 부모와 자식의 대소 관계를 확인해 자리를 바꿔주는 동작을 한다. 예를 들어 위 같이 최대힙을 구현할 때 부모 노드가 자식 노드보다 작다면 상호 간의 자리를 바꿔주는 것이다. left, right는 비교가 진행 될 노드의 인덱스를 의미한다. 초기 값은 루트 노드의 바로 아래 두 자식 노드이다.
첫 번째 조건문은 왼쪽 자식이 부모보다 작은지 확인한다.
두 번째 조건문은 오른쪽 자식이 부모보다작은지 확인한다.
세 번째 조건문은 초기 index와 동일하지 않다면 부모 자식간의 상호 위치를 변경한 뒤 재귀를 통해 반복한다.
7. 셸 정렬 (Shell Sort)
셸 정렬이란 삽입 정렬의 단점을 보완하고자 도입되었다. 삽입 정렬은 주어진 정렬 상태가 역순으로 배열되어 있을수록 비교횟수가 늘어나고, 최선의 경우 $O(N)$이지만 최악의 경우 $O(N^2)$으로 성능 차이가 크다. 셸 정렬은 이러한 시간복잡도를 평균적으로 $O(N^{1.25})$ 또는 $O(N^{1.5})$ 수준으로 낮추고자 도입된 알고리즘이다. 셸 정렬에 사용되는 핵심 개념은 interval (간격)이다. interval은 비교할 원소 간의 간격을 의미한다. 셸 정렬에서는 비교 횟수를 줄이기 위해 interval은 큰 값에서 낮은 값으로 낮춰간다. 동작 방식은 배열에서 interval 만큼 떨어진 원소들을 부분집합으로 구성한 뒤 삽입 정렬을 진행하는 방식으로 진행된다. 초기 interval 값은 len(array) // 2로 설정하며 계속 2로 나누어준다. 예를 들어 아래와 같이 배열 크기가 8이라면 초기 interval = 4가 되어 아래와 같이 비교가 진행 된다.
interval이 4인 경우 거리가 4만큼 떨어져 있는 원소끼리 부분집합을 이루어 비교대상이 된다. 위 그림에선 (35, 14), (33, 19), (42, 27), (10, 44)이 서로 비교 대상이 된다. 비교 진행한 뒤 interval을 2로 나누어주어 4에서 2가 된다. 이후 다시 interval만큼 떨어진 원소를 부분집합화하여 비교한다.
interval이 2인 경우 거리가 2만큼 떨어져 있는 원소끼리 부분집합을 이뤄 비교한다. (14, 27, 35, 42), (19, 10, 33, 34)가 부분집합이 되어 정렬이 진행된다. 이후 다시 interval을 2로 나눠주어 1이 되면 아래와 같이 삽입 정렬이 진행된다.
이를 코드로 구현하여 나타내면 다음과 같다. 주로 가독성을 위해 변수명을 interval을 h로 표현하기도 한다.
def shell_sort(array : list) -> list:
""" Best: O(n) Average: O(n^1.25,1.5) Worst: O(n^2) | O(n) """
n = len(array)
interval = n // 2
while interval > 0:
for i in range(interval, n):
j = i - interval
temp = array[i]
while j >= 0 and array[j] > temp:
array[j+interval] = array[j]
j -= interval
array[j+interval] = temp
interval //= 2
return array
8. 기수 정렬 (Radix Sort)
기수 정렬은 non-comparison 알고리즘으로 원소간의 대소 비교를 하지 않고 정렬하는 알고리즘이다. 대신 기수 정렬은 정렬하고자 하는 수의 낮은 자리 수를 차례대로 확인하여 정렬하는 방식이다. 정렬을 위해 총 10개의 queue를 사용한다.
첫 번째로, 1의 자리 수를 확인하여 각 원소의 1의 자리에 해당하는 queue에 쌓아준다. 이후 0~9의 queue를 순회하며 차례대로 가져온다.
두 번째로, 10의 자리 수를 확인하여 각 원소의 10의 자리에 해당하는 queue에 쌓아준다. 이후 0~9의 queue를 순회하며 차례대로 가져온다.
세 번째가 진행되기 위해서는 100의 자리수를 가진 값이 있어야 하며, n번째가 진행되기 위해서는 $10^{(n-1)}$의 자리수를 가진 수가 있어야 한다.
이를 코드로 구현하면 다음과 같다.
from collections import deque
def radix_sort(array : list) -> list:
""" Best: O(n) Average: O(n) Worst: O(n)"""
buckets = [deque() for _ in range(10)]
MAX = max(array)
queue = deque(array)
radix = 1
while MAX >= radix:
while queue:
num = queue.popleft()
buckets[(num // radix) % 10].append(num)
for bucket in buckets:
while bucket:
queue.append(bucket.popleft())
radix *= 10
return queue
자리수를 담을 bucket을 총 10개 생성해준다. 이후 가장 큰 자리 수 만큼 반복해야 하므로 max(array)를 통해 가져온다. 알고리즘은 크게 두 단계로 나눠서 보면 간단하다. 첫 번째는 queue에 있는 배열을 각 자리수에 해당하는 bucket에 담아주는 과정이다. 두 번째는 bucket에 담은 원소들을 다시 queue에 담아주는 과정이다. 다만 이 두 과정을 반복하되 배열 최대값이 가지는 최대 자리수까지는 비교해주어야 하므로 radix에 10을 곱해줘서 반복하며, 배열 최대값의 자리수보다 넘어가면 끝나는 것이다.
9. 카운팅 정렬 (Counting Sort)
카운팅 정렬(계수 정렬)은 non-comparison sort 알고리즘에 해당하는 알고리즘으로 comparison sort에 해당하는 버블, 선택, 힙, 병합, 퀵, 삽입이 기껏해야 평균적으로 $O(nlogn)$이나 $O(n^2)$의 시간복잡도를 갖기에 이를 $O(n)$ 수준으로 낮추고자 도입된 알고리즘이다. 카운팅 정렬의 동작은 이름 그대로 배열에 존재하는 원소 별 개수를 세어 정렬하는 방식으로 간단히 나타내보이자면 아래 GIF와 같다.
배열에 담긴 요소의 개수를 count라는 배열에 담아 넣은 뒤 차례대로 개수만큼 출력해준다. 우선, 결과적으로 코드를 구현해보자면 아래와 같이 간단한 코드로 나타낼 수 있으며 크게 5단계로 이뤄진다.
def counting_sort(array : list) -> list:
""" Best: O(n) Average: O(n+k) Worst: O(n+k) | O(n+k) """
count = [0] * (max(array) + 1) # 1. create a count array to check how many numbers each have.
for num in array: # 2. check how many numbers each have.
count[num] += 1
for i in range(1, len(count)): # 3. do cumulative sum
count[i] += count[i-1]
arr = [0] * len(array) # 4. create a new array to contain the numbers to be sorted.
for num in array: # 5. sort.
idx = count[num]
arr[idx-1] = num
count[num] -= 1
return arr
1. 배열에 있는 원소 개수를 담을 count 배열을 생성한다. 배열 크기는 원소 값 그대로를 인덱스로 사용하기 위해 max(array)+1로 해준다.
2. 배열에 있는 원소 개수를 count 해준다.
3. 누적합을 진행한다. 그 이유는 누적합을 진행하게 되면 앞 뒤 원소 간의 개수 차이가 곧 몇 칸을 차지할지 알 수 있기 때문이다. 이 부분이 제일 처음 잘 이해가 되지 않는 부분이었다. 예를 들어 설명하기 위해 임의의 배열 [2, 5, 3, 2, 1, 4, 4, 2]라는 배열이 있다 하자. 그러면 count 배열이 [0, 1, 3, 1, 2, 1]가 된다. 이후 count 배열에 누적합을 진행하면 [0, 1, 4, 5, 7, 8]이 된다. 이 누적합을 통해 아래와 같은 사실을 알 수 있다.count[0] = 0: count 배열의 0번째 인덱스인 값 0은 (0-0)칸을 차지하고, 위치하게 되는 인덱스는 [0:0]이 된다.
count[1] = 1: count 배열의 1번째 인덱스인 값 1은 (1-0)칸을 차지하고, 위치하게 되는 인덱스는 [0:1]이 된다.
count[2] = 4: count 배열의 2번째 인덱스인 값 2는 (4-1)칸을 차지하고, 위치하게 되는 인덱스는 [1:4]가 된다.
count[3] = 5: count 배열의 3번째 인덱스인 값 3은 (5-4)칸을 차지하고, 위치하게 되는 인덱스는 [4:5]가 된다.
count[4] = 7: count 배열의 4번째 인덱스인 값 4는 (7-5)칸을 차지하고, 위치하게 되는 인덱스는 [5:7]이 된다.
count[5] = 8: count 배열의 5번째 인덱스인 값 5는 (8-7)칸을 차지하고, 위치하게 되는 인덱스는 [7:8]이 된다.
즉, 누적합 해준 배열을 통해 원소 개수 만큼 도출된 인덱스에 넣어주면 자연스럽게 정렬 되는 것이다. 이러한 과정을 거치기 위해 다음 2단계를 더 진행 한다.
4. 정렬 된 원소를 담고자하는 새로운 배열을 생성해준다. 새 배열 크기는 원래 배열 크기와 동일하다.
5. 정렬하고자 하는 배열의 원소를 순회하며 count[원소]의 위치에서 누적합 되어 있는 값을 index로 지정해준다. 이후 새로 생성한 배열 result에 그 값을 넣어주고 누적합된 값을 -1을 해준다. 여기서 누적합 값에 -1을 해주는 것은 result의 index에 차례대로 같은 수를 담는 것이 아니라 역순으로 담아야 하기 때문이다. 역순으로 값을 담는 이유는 현재 알고리즘 구조상 역순으로 담아야 하기 때문이다. 이중 루프를 통해서 차례대로 값을 담을 수 있지만 코드 가독성과 동작 효율성을 고려하면 위와 같이 작성하는 것이 더 좋다.
마지막으로 시간복잡도는 $O(n+k)$가 된다. k가 상수이긴 하지만 생략되지 못하는 것은 그 만큼 영향을 미칠 수 있기 때문이다. 1~4번 과정 모두 $O(n)$에 해당한다. 하지만 5번에서 count 배열을 업데이트 하는 과정에서 원소 중 max 값인 k를 k만큼 반복하게 되므로 $O(n+k)$가 된다. 만약 정렬하고자 하는 배열의 max 값이 배열의 개수보다 작다면 $O(n)$이 된다. 하지만 배열의 개수보다 커지면 커질수록 배열 공간만 차지하고 값이 들어있지 않는 sprase한 배열이 될 수 있고, 무의미한 공간도 탐색해야 하므로 시간 복잡도가 높아질 수 있는 것이다.
10. Tim Sort
Tim Sort는 삽입정렬과 병합정렬이 결합된 정렬 알고리즘이다. Tim Peter라는 자에게 의해 고안된 알고리즘으로 파이썬 내장 정렬 알고리즘으로 채택되어 있다. Tim Sort는 왜 다른 알고리즘에 비해 상대적으로 느린 삽입정렬을 사용할까? 삽입정렬의 경우 앞서 기술한 바와 같이 평균과 최악의 경우 $O(n^2)$로 다른 알고리즘에 비해 시간복잡도가 높아 잘 사용되지 않는다. 하지만 이러한 단점에도 불구하고 삽입정렬에는 참조 지역성이라는 주요한 성질이 있다. 운영체제 시간에 배우거나 신입 개발자 인터뷰에 때때로 물어보는 내용이다.
CPU가 빠른 연산을 위해 사용하는 캐시 메모리에 데이터를 담을 때 적중률을 높이기 위해 사용하는 원리다. 쉽게 말해 최근 참조했던 메모리와 인접한 메모리를 참조할 확률이 높으니 이들을 캐시 메모리에 미리 담아두는 것이며, 삽입정렬은 인접한 메모리와 비교를 반복하기에 참조 지역성의 원리를 잘 만족하고 있다고 할 수 있다. 또 삽입정렬은 원소가 많아질수록 느려지는 단점이 있지만 정렬 수가 적당히 작은 수라면 퀵정렬보다 빨라지는 장점이 있다. Tim Sort는 이러한 삽입정렬의 특성을 활용하여 전체 정렬 대상 원소들을 부분부분(divide)으로 작게 나눈 다음 삽입정렬을 수행하고 병합(conqure)을 수행하면 정렬이 조금 더 빠르지 않을까 하는 아이디어를 기반으로 만들어졌다. 이러한 Tim Sort는 실제로 시간복잡도를 최선의 경우 $O(n)$, 평균은 $O(n\log n)$, 최악의 경우 $O(n\log n)$를 갖는다.
Tim Sort에서는 이러한 삽입정렬을 그대로 사용하진 않고 속도를 개선한 이진삽입정렬을 사용한다. 이진삽입정렬을 사용하면 앞서 말한 참조 지역성이 떨어지게 되나 적당히 작은 수의 원소를 정렬한다면 참조 지역성이 크게 문제가 되지 않으면서 시간복잡도를 개선할 수 있게 된다.
Tim Sort의 수행절차는 아래 그림을 통해 대략적인 흐름을 이해할 수 있다. (출처: https://st-lab.tistory.com/276)
이를 코드로 구현하면 아래와 같다.
RUN = 32
def insert_sort(array, left, right):
for i in range(left + 1, right + 1):
key = array[i]
j = i - 1
while j >= left and array[j] > key:
array[j + 1] = array[j]
j -= 1
array[j + 1] = key
def merge(array, left, mid, right):
len1 = mid - left + 1,
len2 = right - mid
left_array, right_array = [], []
for i in range(0, len1):
left_array.append(array[left + i])
for i in range(0, len2):
right_array.append(array[mid + 1 + i])
i, j, k = 0, 0, left
while i < len1 and j < len2:
if left_array[i] <= right_array[j]:
array[k] = left_array[i]
i += 1
else:
array[k] = right_array[j]
j += 1
k += 1
while i < len1:
array[k] = left_array[i]
k += 1
i += 1
while j < len2:
array[k] = right_array[j]
k += 1
j += 1
def tim_sort(array):
""" Best: O(n) Average: O(nlogn) Worst: O(nlogn) | O(n) """
n = len(array)
for i in range(0, n, RUN):
insert_sort(array, i, min((i + RUN - 1), n - 1))
size = RUN
while size < n:
for left in range(0, n, size * 2):
mid = left + size - 1
right = min((left + size * 2 - 1), (n - 1))
merge(array, left, mid, right)
size = size * 2
return array
if __name__ == "__main__":
array = [5, 2, 8, 4, 1, 9, 6, 3, 7]
sorted_array = tim_sort(array)
print(sorted_array)
Reference
[01] 버블 정렬: https://jinhyy.tistory.com/9
[02] 삽입 정렬: https://velog.io/@delmasong/AlgorithmInsertion-Sort-삽입-정렬
[03] 선택 정렬: https://gfycat.com/ko/snappymasculineamericancicada
[04] 퀵 정렬: https://latte-is-horse.tistory.com/197
[05] 병합 정렬: https://velog.io/@delmasong/Algorithm-Merge-Sort-병합-정렬
[06] 카운팅 정렬: https://seongonion.tistory.com/130
[07] 카운팅 정렬: https://elrion018.tistory.com/37
[08] 힙 정렬: https://it-garden.tistory.com/128
[09] 힙 정렬: https://velog.io/@jaenny/자료구조-힙-최소힙-최대힙
[10] 힙 정렬: https://github.com/TheAlgorithms/Python/blob/master/sorts/heap_sort.py
[11] 힙 정렬: 『파이 썬 알고리즘 인터뷰』
[12] 셸 정렬: https://velog.io/@yusokk/algorithm-sort2
[13] 셸 정렬: https://mong9data.tistory.com/45
[14] 기수 정렬: https://week-year.tistory.com/206
[15] 기수 정렬: http://www-scf.usc.edu/~zhan468/public/Notes/sorting.html
[16] Tim 정렬: https://d2.naver.com/helloworld/0315536
[17] Tim 정렬: https://st-lab.tistory.com/276
'Computer Science > 자료구조' 카테고리의 다른 글
| [자료구조] 최소 신장 트리와 크루스칼 알고리즘 (0) | 2022.10.06 |
|---|---|
| [자료 구조] 최단 거리 알고리즘 정리 (다익스트라, 벨만 포드, 플로이드 워셜) (5) | 2022.09.20 |
| [자료구조] 링크드 리스트 (Linked List) (1) | 2022.09.05 |
| [자료구조] 이진 탐색 알고리즘 (Binary Search Algorithm) (0) | 2022.08.22 |