정렬 알고리즘
느린 순서부터 빠른 순서대로 정렬하기
- 버블 정렬
- 선택 정렬
- 삽입 정렬
- 합병 정렬
- 퀵 정렬
모든 설명은 오름차순 정렬 기준으로, 모든 리스트는 n개의 요소를 갖는다고 가정하고 설명한다.
버블 정렬
버블 정렬은 뒤에서부터 큰 값이 비눗방울이 떠오르듯이 정렬된다고 하여 붙여진 이름이다.
원리
- 리스트의 가장 앞부터 시작하여 j번째 요소와 j + 1번째 요소를 비교한다.
- 만약 j + 1번째 요소가 j번째 요소보다 크다면, 두 요소의 위치를 바꾼다(swap).
- 이 과정을 리스트의 길이 - 1번만큼 반복한다.
시간 복잡도
리스트의 길이만큼, j번째와 j + 1번을 비교하는 과정이 n번 반복되고 그것을 n번 반복하기때문에 n^2의 시간복잡도를 가진다. 특별히 최적화가 이루어지지 않을 경우, 매 경우마다 탐색을 시도하므로 최선 및 최악의 경우에도 n^2만큼의 시간복잡도를 갖는다. n^2의 시간 복잡도를 갖는 다른 정렬 알고리즘에 비해서도 느린 편에 속하는데, 그 이유는 스왑하는 과정이 반복적으로 일어나기 때문이다.
최적화
가장 앞쪽부터 차례대로 탐색을 하는 버블 정렬의 특성상, 더 이상 스왑이 일어나지 않았다면, 완벽하게 정렬되었다는 뜻이기 때문에 스왑 과정이 일어나지 않았다면 바로 정렬 과정을 종료할 수 있다. 이 경우 최선의 시간복잡도는 n(이미 정렬되어 있을 경우)이 된다.
코드
def bubble_sort(arr):
length = len(arr)
for i in range(length):
flag = True
# 가장 뒤는 이미 정렬이 되어 있는 상태이므로 다시 확인할 필요가 없다.
for j in range(length - i):
if j + 1 >= length:
continue
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
flag = False
print(arr)
if flag:
break선택 정렬
선택 정렬은 가장 작은 값을 갖는 인덱스를 찾고, 그 값을 현재 인덱스와 바꾸는 정렬 방법이다.
원리
- 현재 인덱스를 가장 작은 값을 갖는 인덱스로 설정한다.
- 현재 인덱스부터 n - 1번 인덱스까지 탐색하며,
arr[min_idx] > arr[j]를 만족하면,min_idx를 갱신한다. - 현재 인덱스(i)번의 값과 min_idx의 값을 서로 바꾼다.
- 이 과정을 n번 반복한다.
시간 복잡도
선택 정렬 역시 반복문을 두 번 순회해야 하기 때문에 평균적으로 N**2의 시간 복잡도를 갖는다. 다만 평균적으로 따졌을 때 버블 정렬보다는 빠른데, 그 이유는 스왑 과정이 버블 정렬보다 적게 일어나기 때문이다. 그러나 버블 정렬은 최적화가 가능하지만, 선택 정렬은 따로 최적화가 가능하지 않다는 특징이 있다. 왜냐하면 현재 인덱스가 와 min_idx가 같다고 해서 뒤 요소들이 순서대로 정렬되어있다는 보장이 없기 때문이다.
코드
# 선택 정렬의 경우 최악의 경우와 최선의 경우, 평균 모두 O(n**2)의 시간복잡도를 가진다.
def selection_sort(arr: list[int | float]):
for i in range(len(arr)):
min_index = i
for j in range(i + 1, len(arr)):
if arr[min_index] > arr[j]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
print(arr)삽입 정렬
삽입 정렬은 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 요소들과 비교하여 자신의 위치를 찾아 삽입하는 알고리즘이다.
원리
- 배열의 0번이 아닌 1번 인덱스부터 참조한다. 1번 인덱스부터 참조하는 이유는 탐색하려는 요소의 왼쪽은 이미 정렬되어있다고 가정하기 때문이다. 물론 0번부터 탐색한다고 해서 에러가 발생하진 않는다.
- 현재 인덱스 i부터 차례대로 j번째와 j - 1번째 요소를 비교한다. 만약 j - 1번째 요소가 더 크다면 j번째와 j - 1번째 요소를 스왑한다. 이 과정을 0번 인덱스까지 반복한다.
- 0번 인덱스까지 비교하는 과정을 마쳤으면, 다음 i + 1번째 요소 역시 같은 방법으로 비교한다
시간 복잡도
삽입 정렬은 평균적으로 n2의 시간복잡도를 갖지만, n2의 시간복잡도를 갖는 다른 알고리즘에 비하여 가장 빠른 편에 속한다. 그래서 배열을 정렬할 때 길이가 10 이하인 배열은 삽입 정렬로, 더 긴 길이는 퀵 정렬을 이용하여 복합적으로 정렬 알고리즘을 구성하기도 한다. 최선의 경우는 n이며, 최악의 경우는 n**2이다.
코드
# 삽입 정렬은 최선의 경우 O(n)의 시간 복잡도를 가진다.
# 최악의 경우 O(n^2)이지만, O(n^2) 정렬 알고리즘 중 가장 빠른 편이다.
def insertion_sort(arr):
for i in range(1, len(arr)):
for j in range(i, 0, -1):
# 현재 위치의 값이 바로 이전 위치보다 작다면,
# j번째와 j - 1번째 값을 스왑한다.
# 0번 인덱스까지 반복하고, 더 이상 j번째가 j - 1번째보다 작지 않다면 멈춘다.
if arr[j] < arr[j - 1]:
arr[j], arr[j - 1] = arr[j - 1], arr[j]
else:
break
arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
insertion_sort(arr)합병 정렬
합병 정렬은 분할정복 기법을 이용한 알고리즘으로, 배열을 더 이상 쪼갤 수 없을 때 까지 나눈 뒤, 두 배열을 합쳐 정렬된 하나의 배열로 만드는 기법이다. 분할 + 정복 과정으로 나누어져있다.
원리
- 하나의 배열을 더 이상 쪼갤 수 없을 때까지 쪼갠다.
- 쪼개진 두 배열은 내부적으로 정렬이 되어있는 상태이므로, 두 배열의 상태를 저장하는 하나의 캐싱 배열을 만들고, 두 배열의 요소를 비교하여 캐싱한다.
- 비교 과정이 끝나고 남은 배열 요소들을 캐싱 배열에 삽입한다.
- 이 과정을 반복한다.
시간 복잡도
두 배열을 분리하는 과정 (log(n)), 두 배열을 비교하여 합치는 과정(n)이 함께 일어나므로 시간 복잡도는 nlog(n)으로 빠른 편에 속한다. 합병 정렬은 최선 및 최악의 경우에도 nlog(n)의 시간 복잡도를 만족한다. 다만, 배열의 상태를 저장하기 위하여 길이 N만큼의 배열이 추가로 필요하다는 점에서 공간 복잡도 측면에서 불리함이 있다.
코드
def merge_sort(arr):
if len(arr) < 2:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
left_idx = 0
right_idx = 0
ret = []
# 두 배열을 비교하여 둘 중 작은 값을 새로운 배열에 삽입한다.
# 이 과정이 끝나게되면 적어도 하나의 배열 내 요소들은 전부 새로운 배열에 삽입된다.
while left_idx < len(left) and right_idx < len(right):
if left[left_idx] <= right[right_idx]:
ret.append(left[left_idx])
left_idx += 1
else:
ret.append(right[right_idx])
right_idx += 1
while left_idx < len(left):
ret.append(left[left_idx])
left_idx += 1
while right_idx < len(right):
ret.append(right[right_idx])
right_idx += 1
return ret
arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
print(merge_sort(arr))퀵 정렬
퀵 정렬의 기본 원리는 하나의 기준점을 잡고, 기준점의 왼쪽에는 기준점의 값보다 낮은 값을 배치하고, 오른쪽은 기준점의 값보다 높은 값이 오도록 배치하는 것이 원리이다. 합병 정렬처럼 분할 + 정복 기법이며, 합병 정렬은 정확히 배열을 절반으로 나누어 진행하지만 퀵 정렬은 피벗을 이용하여 배열을 두 부분으로 나눈다는 차이가 있다.
원리
- 배열 내부에서 하나의 피벗을 설정한다. 일반적으로 가장 왼쪽에 있는 값을 피벗으로 설정하게 된다.
- 처음 start index를 left, end index를 right으로 설정한 뒤, left는 오른쪽 방향으로, right는 왼쪽 방향으로 탐색한다. left는 arr[left] > arr[pivot]을 만족하면 멈추고, right는 arr[right] < arr[pivot]을 만족하면 멈춘다.
- left index가 right index와 엇갈리게되면, arr[left] > arr[pivot], arr[right] < arr[pivot]을 만족하는 값이 없다는 뜻이므로, arr[pivot]과 둘 중 더 작은값의 위치를 바꾼다.(피벗의 왼쪽은 피벗값보다 작은 값들이 놓여야하고, 피벗의 오른쪽은 피벗보다 큰 값들이 놓여야하므로) left < right인 시점에서 arr[right]가 arr[left]보다 더 작아지기 때문에 arr[right]값과 스왑한다.
- pivot을 기준으로 좌, 우로 나누어 과정을 반복한다.
코드
arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(arr, start, end):
# basecase
if start >= end:
return
pivot = start
left = start
right = end
while left <= right:
while left <= end and arr[left] <= arr[pivot]:
left += 1
while right > start and arr[right] >= arr[pivot]:
right -= 1
if left > right:
arr[pivot], arr[right] = arr[right], arr[pivot]
else:
arr[left], arr[right] = arr[right], arr[left]
quick_sort(arr, start, right - 1)
quick_sort(arr, right + 1, end)
arr = [9, 8, 7, 6, 5, 4, 3, 2, 1]
quick_sort(arr, 0, len(arr) - 1)
print(arr)시간 복잡도
피벗을 기준으로 배열을 분할하고, 내부에서 다시 정렬을 진행하므로 평균적으로 O(nlog(n)), 최선의 경우 역시 O(nlog(n))의 시간복잡도를 갖는다. 또, (nlog(n)) 정렬 알고리즘 중에서 가장 빠르며, 합병 정렬처럼 추가적인 배열이 필요로 하지 않기 때문에 재귀로 인한 공간 복잡도 (O(log(n)))만 가진다. 다만 최악의 경우 (O(n**2))의 시간복잡도를 갖는데, 피벗의 최솟값 또는 최댓값을 가질 경우이다. (배열이 순차 또는 역순으로 정렬되어 있을 때)
이 경우 각 요소에 대하여 left인덱스는 움직이지 않고, right index가 left index까지 이동할 것이다. 다음 피벗 역시 left는 움직이지 않고 right index만 움직이는 과정을 반복하므로 배열의 데이터 개수만큼 진행하게 되고, 역시 내부에서 n - 1개의 데이터와 비교하는 과정을 거치므로, n ** 2의 시간복잡도를 갖게 되는 것이다.
표로 나타내기
| 평균 시간복잡도 긴 순으로 정렬 | 시간복잡도(최선) | 시간복잡도(평균) | 시간복잡도(최악) | 공간복잡도 |
|---|---|---|---|---|
| 버블 정렬 | O(n) | O(n**2) | O(n**2) | O(1) |
| 선택 정렬 | O(n**2) | O(n**2) | O(n**2) | O(1) |
| 삽입 정렬 | O(n) | O(n**2) | O(n**2) | O(1) |
| 합병 정렬 | O(nlog(n)) | O(nlog(n)) | O(nlog(n)) | O(n) |
| 퀵 정렬 | O(nlog(n)) | O(nlog(n)) | O(n**2) | O(log(n)) |
