정렬 알고리즘은 실제로 직접 구현해야 할 일은 없지만 알고리즘 지식에 대한 기초로, 어떤 원리이며 각 시간 복잡도는 어떤 지 정도는 기본적으로 알고 있어야 한다. 그 중에서도 안정된 정렬 알고리즘(Stable Sort)과 안정하지 않은 (Unstable Sort)가 있다.
안정적인 정렬 vs 안정적이지 않은 정렬
안정적인 정렬은 동일한 값을 가진 요소들의 원래 순서가 정렬 후에도 유지되는 정렬이며, 안정적이지 않은 정렬은 동일한 값을 가진 요소들의 원래 순서가 정렬 후에 보장되지 않는 정렬이다.
동일한 키 값을 가진 요소들 사이의 원래 순서가 필요하다면 안정된 정렬을, 필요하지 않다면 안정적이지 않은 정렬을 사용한다. 보통 안정적이지 않은 정렬의 속도가 더 빠르다.
버블 정렬 (Bubble Sort)
배열 내의 인접한 요소들을 비교하고 필요에 따라 위치를 교환하여 정렬하는 알고리즘. 더 큰 요소들이 배열의 끝으로 '떠오르는' 모습을 연상하기에 버블 정렬이라고 부른다. 구현이 단순하며 알고리즘 역시 단순하지만, 효율성이 정렬 알고리즘 중 가장 낮다.
알고리즘 작동 원리는
1. 배열의 첫 번째 요소부터 시작해 인접한 요소들을 비교한다.
2. 만약 인접한 요소가 순서대로 정렬되어 있지 않다면, 이들의 위치를 서로 교환한다.
3. 배열의 끝까지 이 과정을 반복한다.
4. 다시 배열의 처음부터 모든 요소가 정렬될 때 까지 반복한다.
배열의 크기 n에 대해, 이 알고리즘은 시간 복잡도 평균 및 최악에서 \(O(N^2)\)를 가진다. 또한, 안정적인 정렬이다.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
삽입 정렬 (Insertion Sort)
한 번에 하나의 항목을 취하여 이미 정렬된 부분에 적절한 위치를 찾아 삽입하는 정렬 알고리즘. 카드 게임에서 손에 들고 있는 카드를 정렬하는 것과 비슷하다고 생각하면 된다.
작동 원리는
1. 배열의 두 번째 요소부터 시작해 현재 요소를 key로 정의한다.
2. 이 key를 이미 정렬된 배열 부분의 적절한 위치에 삽입한다.
3. 배열의 모든 요소에 대해 반복한다.
배열의 길이 n에서 평균 및 최악에서 시간 복잡도 \(O(N^2)\)이며 안정적인 정렬 방법이다.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
# Move elements of arr[0..i-1
선택 정렬 (Selection Sort)
배열의 최솟값 또는 최댓값을 찾아 맨 앞의 요소와 교환하는 방식으로 간단한 정렬 알고리즘이다.
작동 원리는
1. 배열 전체에서 최솟값을 찾는다.
2. 이 최솟값을 배열의 첫 번째 위치에 있는 요소와 교환한다.
3. 다음으로, 첫 번째 위치를 제외한 나머지 배열에서 최솟값을 찾아 두 번째 위치의 요소와 교환한다.
4. 모든 요소가 정렬될 때 까지 반복한다.
평균 및 최악의 경우에서 모두 시간 복잡도 \(O(N^2)\)를 가지며 안정적인 정렬 방법이 아니다.
def selection_sort(arr):
for i in range(len(arr)):
# Find the minimum element in remaining unsorted array
min_idx = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
# Swap the found minimum element with the first element
arr[i], arr[min_idx] = arr[min_idx], arr[i]
병합 정렬 (Merge Sort)
분할 정복 (divide and conquer) 방식을 사용한 정렬 알고리즘으로, 큰 문제를 작은 문제로 나눈 후, 각각을 해결하고 그 결과를 합쳐 전체 문제를 해결하는 방식이다.
작동 원리는
1. 배열을 두 개의 동일한 크기의 배열로 분할한다. 이 과정을 하위 배열이 충분히 작아질 때까지 재귀적으로 수행한다.
2. 각각의 하위 배열을 정렬한다. 배열의 크기가 충분히 작아진다면, 정렬은 간단해진다.
3. 정렬된 하위 배열들을 다시 합쳐 전체를 정렬된 배열로 만든다.
평균 및 최악의 경우에서 시간 복잡도 \(O(n log n)\)를 가지며 위 방법들에 비해 효율적이다. 또한, 안정적인 정렬 방법이다.
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
# 병합 과정
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# L에 남은 요소들을 배열에 추가
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
# R에 남은 요소들을 배열에 추가
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
퀵 정렬 (Quick Sort)
퀵 정렬 역시 분할 정복을 사용한 효율적인 정렬 알고리즘이다.
작동 원리는
1. 배열에서 하나의 요소를 pivot으로 선택한다.
2. 배열을 두 부분으로 나누어 한 부분은 피벗보다 작거나 같은 요소들, 다른 부분은 피벗보다 큰 요소들이 오도록 한다.
3. 분할된 두 부분을 1-2의 퀵 정렬으로 다시 정렬한다. 각 부분의 크기가 작아지면 완료된다.
4. 정렬된 부분들을 결합해 다시 정렬된 전체의 배열로 만든다.
시간 복잡도의 경우 평균에서 \(O(n log n)\)이지만, 최악의 경우 \(O(n^2)\)이 될 수 있다.
또한 안정적이지 않은 정렬 방법이다.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
힙 정렬 (Heap Sort)
힙 정렬은 힙 자료구조를 사용한 정렬 알고리즘으로, 이진 힙, 최대 힙 또는 최소 힙을 사용하여 요소를 정렬한다.
작동 원리는
1. 주어진 배열로부터 최대 힙 또는 최소 힙을 구축한다.
2. 힙의 루트를 배열의 마지막 요소와 교환한 후, 힙의 크기를 줄이며 수정된 힙에 대해 힙 속성을 복원한다.
3. 힙이 빌 때까지 이 과정을 반복한다.
시간 복잡도는 평균적으로 \(O(n log n)\) 을 가지며 안정적인 정렬 방법이 아니다.