정렬 알고리즘
1. 버블 정렬(Bubble Sort)
서로 인접해 있는 요소 간의 대소 비교를 통해 정렬한다. 버블 정렬은 정렬 알고리즘 중 가장 단순한 알고리즘으로, 단순한 만큼 비효율적이다.
✔️ 시간 복잡도: 최고, 평균, 최악 모두 O(n^2)
✔️ 공간 복잡도: O(n)
1
2
3
4
5
6
def bubble_sort(array):
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
- 삽입 정렬(Insert Sort)
정렬을 진행할 원소의 index보다 낮은 곳에 있는 원소들을 탐색하며 알맞은 위치에 삽입해주는 정렬 알고리즘이다. 알고리즘이 동작하는 동안 계속해서 정렬이 진행되므로 반드시 맨 왼쪽 index까지 탐색하지 않아도 된다는 장점이 있다.
✔️ 시간 복잡도: O(n)
✔️ 공간 복잡도: O(n)
1
2
3
4
5
6
def insert_sort(array):
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
3. 선택 정렬 (Selection Sort)
배열에서 최소값을 반복적으로 찾아 정렬하는 알고리즘
✔️ 시간 복잡도: 최고, 평균, 최악 모두 O(n^2)
✔️ 공간 복잡도: O(n)
1
2
3
4
5
6
7
8
def selection_sort(array):
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
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이 된다면 가장 정렬 완료된 것이므로 분할된 배열을 합쳐 줌으로써 정렬을 마친다.
✔️ 시간 복잡도: 최고:O(nlogn), 평균:O(nlogn), 최악: O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def quick_sort(array : list) -> list:
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]와 같이 정렬이 완료되면서 알고리즘이 종료된다.
✔️ 시간 복잡도: 최고:O(nlogn), 평균:O(nlogn), 최악: O(nlogn)
✔️ 공간 복잡도: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def merge_sort(array: list) -> list:
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
6. 힙 정렬 (Heap Sort)
힙이란 트리 기반의 자료구조로서, 두 개의 노드를 가진 완전 이진 트리를 의미한다. 따라서 힙 정렬이란 완전 이진 트리를 기반으로 하는 정렬 알고리즘이다. 힙의 분류는 크게 최대 힙과 최소 힙 두 가지로 나뉜다. 최대 힙은 내림차순 정렬에 사용하며, 최소 힙은 오름차순 정렬에 사용한다.
최대힙의 경우 부모 노드가 항상 자식노드 보다 크다는 특징을 가진다. 반대로 최소힙의 경우 부모 노드가 항상 자식노드 보다 작다는 특징을 가진다.
힙은 완전 이진 트리기 때문에 적절히 중간 레벨의 노드를 추출하면 중앙값에 가까운 값을 근사치로 빠르게 추출할 수 있다는 장점을 갖고 있다. 때문에 힙은 배열에 순서대로 표현하기 적합하다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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]
📑 참고 자료