Sorting
개요
정렬이란 규칙 없이 나열된 것들을 어떤 규칙을 만족하도록 순서대로 나열하는 것을 뜻합니다.
알고리즘의 종류
정렬 알고리즘에서는 여러 종류가 있으며, 시간 복잡도 이외에도 고려해야 할 부분이 있으므로 상황에 맞게 섞어서 사용하는 것이 가장 빠릅니다.
예를 들어 파이썬에서는 병합 정렬과 삽입 정렬을 같이 사용하는 Timsort를, C++에서는 퀵 정렬, 힙 정렬, 삽입 정렬을 같이 사용하는 Introsort를 사용합니다.
알고리즘은 오름차순으로 정렬하는 것을 기준으로 설명하겠습니다.
시간 복잡도 설명에서
중요한 몇 가지 알고리즘들만 소개하겠습니다.
버블 정렬(Bubble Sort)
첫 번째 원소와 두 번째 원소를 비교하여 두 번째 원소가 더 크도록 정렬합니다. 이어서 두 번째 원소와 세 번째 원소도 똑같이 정렬하고, 마지막 원소까지 이를 반복합니다.
한 번 이를 마치고 나면 최댓값이 가장 오른쪽으로 오게 됩니다.
다시 첫 번째 원소와 두 번째 원소를 비교하여 두 번째 원소가 더 크도록 정렬합니다. 이번에는 마지막에서 두 번째 원소까지 이를 반복합니다.
이제 두 번째로 큰 원소까지 정렬되었습니다.
이를 계속 반복해서 정렬하면 됩니다.
def bubble_sort(arr):
n = len(arr)
for step in range(n - 1):
for i in range(n - step - 1):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]제일 큰 값을 오른쪽으로 보내는 데
따라서 총
최댓값이 오른쪽으로 이동하는 것이 거품이 올라오는 것 같다고 하여 버블 정렬이라는 이름이 붙게 되었습니다.
삽입 정렬(Insertion Sort)
구간 [0, 0]의 부분배열이 이미 정렬된 것으로 보고 두 번째 원소를 정렬이 유지되도록 삽입합니다.
구간 [0, 1]의 부분배열이 이미 정렬된 것으로 보고 세 번째 원소를 정렬이 유지되도록 삽입합니다.
이를 반복하여 정렬합니다.
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
j = i - 1
value = arr[i]
while arr[j] > value and j >= 0:
arr[j + 1] = arr[j] # 원래 있던 값을 오른쪽으로 밀어내기
j = j - 1
arr[j + 1] = value최대
그러나 배열의 크기가 작고 어느 정도 정렬되어 있다면 비교를 적게 하므로 버블 정렬이나 선택 정렬보다 빠르게 동작합니다.
병합 정렬(Merge Sort)
폰 노이만이 개발한 정렬 알고리즘입니다.
이미 정렬된 두 배열을 정렬이 유지되도록 한 배열로 합쳐 봅시다.
두 배열마다 앞부분을 비교해서 더 작은 원소를 뽑아내서 배열에 담는 것을 반복하면 됩니다.
def merge(A, B):
ret = []
i = 0
j = 0
while i < len(A) and j < len(B):
if A[i] < B[j]:
ret.append(A[i])
i += 1
else:
ret.append(B[i])
j += 1
while i < len(A):
ret.append(A[i])
i += 1
while j < len(B):
ret.append(B[i])
j += 1
return ret두 배열의 앞부분을 가리키는 인덱스 ret에 원소를 하나씩 담으므로 두 배열의 길이를 각각
병합 정렬은 병합과 분할 정복을 이용해서 빠르게 정렬합니다. 이미 정렬된 두 부분 배열을 병합하는 것은 처음부터 모두 정렬하는 것 보다 쉬우므로 배열을 반으로 쪼개 먼저 졍렬한 후 병합하는 방법입니다. 이때 쪼갠 부분 배열을 정렬할 때에도 똑같이 병합 정렬을 사용합니다.
def merge_sort(arr: list):
def sort(start, end):
if start == end:
return
mid = (start + end) // 2
sort(start, mid)
sort(mid + 1, end)
merge(start, end)
def merge(start: int, end: int):
temp = [0] * (end - start + 1)
i = 0
mid = (start + end) // 2
j = start
k = mid + 1
while j <= mid and k <= end:
if arr[j] <= arr[k]:
temp[i] = arr[j]
j += 1
else:
temp[i] = arr[k]
k += 1
i += 1
while j <= mid:
temp[i] = arr[j]
i += 1
j += 1
while k <= end:
temp[i] = arr[k]
i += 1
k += 1
for i in range(end - start + 1):
arr[start + i] = temp[i]
sort(0, len(arr) - 1)길이
이때 배열을 반으로 나누어 각각 병합 정렬을 하고 합치므로
이를
공식을 적용해서
퀵 정렬(Quick Sort)
일반적으로 가장 빠르다고 알려진 정렬 방식입니다.
먼저 pivot이라고 하는 기준점을 적당히 잘 잡습니다. 이제 이를 기준으로 작은 값은 pivot의 왼쪽으로, 큰 값은 pivot의 오른쪽으로 옮깁니다. 이제 pivot으로 인해 쪼개진 두 부분을 각각 퀵 정렬하면 됩니다.
def quick_sort(arr: list):
def sort(start: int, end: int):
if start == end:
return
pivot = arr[(start + end) // 2]
lo = start
hi = end
# pivot보다 큰 최소 인덱스와 pivot보다 작은 최대 인덱스를 계속 교환
while lo <= hi:
while arr[lo] < pivot:
lo += 1
while arr[hi] > pivot:
hi -= 1
if lo <= hi:
arr[lo], arr[hi] = arr[hi], arr[lo]
lo += 1
hi -= 1
sort(start, lo - 1)
sort(lo, end)
sort(0, len(arr) - 1)sort 함수에서 재귀적으로 자신을 호출하는 부분을 빼고 시간 복잡도가
pivot을 항상 절묘하게 잘 잡아서 쪼개진 두 부분의 크기가 각각
그러나 만약 pivot을 최솟값이나 최댓값으로 계속 고르게 된다면 최악의 경우 시간 복잡도는
그런데도 평균적으로 다른 알고리즘들에 비해 가장 좋은 성능을 보이는 이유는 추가적인 메모리를 필요로 하지 않는다는 점입니다. 병합 정렬은 임시 배열을 필요로 하는 데 반해 퀵 정렬은 임시 배열을 필요로 하지 않습니다. 따라서 알고리즘의 메모리 지역성이 높아 CPU의 캐시 히트 적중률이 높고 더 빨리 작동합니다.
계수 정렬(Counting Sort)
원소의 개수를 세어 정렬하는 방식입니다.
def counting_sort(arr: list[int]):
max_value = max(arr)
min_value = min(arr)
count = [0] * (max_value - min_value + 1)
for number in arr:
count[number - min_value] += 1
i = 0
j = min_value
while j <= max_value:
for _ in range(count[j - min_value]):
arr[i] = j
i += 1
j += 1정수로 이루어진 배열 속 최댓값과 최솟값의 차가
