정렬은 n개의 원소를 순서대로 배열하는 것으로 프로그래밍을 할 때 많이 사용되는 알고리즘 중 하나이다. 데이터가 정렬되어 있으면 검색, 비교, 분석이 훨씬 쉬워지는 등 이점이 있다. 정렬 알고리즘에는 다양한 종류가 있으며 이번 포스트에서 대표적인 정렬 알고리즘인 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬에 대해 알아보려한다.
1. 선택 정렬 (Selection Sort)
선택 정렬은 가장 간단한 정렬 알고리즘 중 하나이다. 배열에서 최솟값을 찾아 선택하여 배열의 첫 번째 원소와 교체하고, 그 다음 최솟값을 찾아 두 번째 원소와 교체한다. 이를 배열 전체를 순회하며 수행하면 정렬된 배열이 완성된다.
배열에서 최솟값을 찾아 선택하는 과정 때문에 이름이 선택 정렬인 것 같다. 이를 파이썬 코드로 구현하면 아래와 같다.
def selection_sort(arr:list, n: int):
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr선택 정렬의 시간 복잡도는 O(n^2)이며 배열의 크기가 커질수록 정렬하는데 오랜 시간이 걸린다. 하지만 코드가 간단하고 구현하기 쉽기 때문에 자주 사용된다.
버블 정렬 (Bubble Sort)
버블 정렬은 선택정렬과 마찬가지로 간단한 정렬 알고리즘이다. 배열을 순회하며 인접한 두 원소를 비교하고, 크기가 더 작은 원소를 앞으로 이동시킨다. 이를 배열의 끝까지 수행하면 가장 큰 원소가 배열의 맨 뒤로 이동하게 되고, 이를 반복하면서 정렬을 완성한다.
def bubble_sort(arr: list, n: int):
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr버블 정렬의 시간 복잡도는 선택정렬과 마찬가지로 O(n^2)이다.
삽입 정렬 (Insertion Sort)
삽입 정렬은 배열에 새로운 원소를 더하며 정렬된 배열을 만드는 식으로 동작한다. 배열의 두 번째 요소부터 시작해 이전 요소들과 비교하여 자신의 위치를 찾아 삽입한다. 이를 배열의 모든 원소에 대해 반복해 정렬을 수행한다.
정렬을 수행 중 arr[i]의 위치를 찾을 때 arr[i - 1] 까지는 항상 정렬이 되어있다. 아래는 삽입 정렬을 구현한 코드이다.
def insertion_sort(arr: list, n: int):
for i in range(1, n): # 1
key = arr[i]
j = i-1
while j >= 0 and arr[j] > key: # 2
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr첫 번째 반복문은 n-1번 순환한다. 그리고 내부의 while 루프에서 현재 선택된 arr[i]를 가장 왼쪽까지 이동시키는 경우 i-1번 반복해야 한다. 하지만 arr[i]를 이동할 필요가 없으면 내부의 while 루프는 동작하지 않아도 된다. 즉 배열이 거의 정렬된 상태라면 삽입 정렬은 매우 빠르게 동작한다. 따라서 삽입 정렬의 시간 복잡도는 최악의 경우 O(n^2)이지만, 배열이 이미 정렬되어 있는 경우에는 효율적으로 동작하는 정렬 방법이다.