정렬 알고리즘을 처음 배울 때는 보통 버블 정렬, 선택 정렬, 삽입 정렬부터 본다. 셋 다 실무에서 대규모 데이터를 정렬할 때 쓰기에는 비효율적이지만, 배열을 순회하고 값을 비교하고 위치를 바꾸는 기본 감각을 익히기 좋다.
버블 정렬
버블 정렬(Bubble Sort)은 인접한 두 요소를 비교해서 순서가 잘못되어 있으면 서로 바꾸는 방식이다. 한 번의 순회가 끝날 때마다 가장 큰 값이 배열의 뒤쪽으로 밀려난다. 큰 값이 물방울처럼 끝으로 떠오른다는 의미에서 버블 정렬이라고 부른다.
구현 아이디어는 단순하다. 아직 정렬되지 않은 구간을 왼쪽부터 오른쪽까지 훑으면서 nums[j]와 nums[j + 1]을 비교한다. 앞의 값이 더 크면 두 값을 교환한다. 이 과정을 반복하면 뒤쪽부터 하나씩 정렬이 확정된다.
시간 복잡도는 평균과 최악 모두 O(n²)이다. 이해하기 쉽고 구현도 간단하지만, 큰 배열에서는 비교와 교환이 너무 많이 발생한다.
def bubble_sort(nums):
for i in range(len(nums) - 1, 0, -1):
for j in range(i):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums
print(bubble_sort([5, 3, 8, 4, 2])) # [2, 3, 4, 5, 8]
print(bubble_sort([20, -5, 3, 2])) # [-5, 2, 3, 20]선택 정렬
선택 정렬(Selection Sort)은 정렬되지 않은 구간에서 가장 작은 값을 찾아 현재 위치로 가져오는 방식이다. 첫 번째 자리에는 전체 배열에서 가장 작은 값을 놓고, 두 번째 자리에는 남은 값 중 가장 작은 값을 놓는 식으로 진행한다.
버블 정렬처럼 시간 복잡도는 O(n²)이지만, 교환 횟수는 상대적으로 적다. 대신 매 단계마다 남은 구간 전체를 확인해야 하므로 큰 데이터에는 여전히 비효율적이다.
def selection_sort(nums):
for i in range(len(nums)):
min_index = i
for j in range(i + 1, len(nums)):
if nums[j] < nums[min_index]:
min_index = j
nums[i], nums[min_index] = nums[min_index], nums[i]
return nums
print(selection_sort([29, 10, 14, 37, 13])) # [10, 13, 14, 29, 37]
print(selection_sort([5, 3, 8, 4, 2])) # [2, 3, 4, 5, 8]삽입 정렬
삽입 정렬(Insertion Sort)은 값을 하나씩 보면서, 이미 정렬된 왼쪽 구간의 적절한 위치에 현재 값을 끼워 넣는 방식이다. 카드를 손에 들고 순서대로 정리하는 과정과 비슷하다.
평균과 최악의 시간 복잡도는 O(n²)이지만, 배열이 거의 정렬되어 있다면 꽤 빠르게 동작한다. 그래서 작은 데이터나 거의 정렬된 데이터에서는 생각보다 실용적인 경우가 있다.
def insertion_sort(nums):
for i in range(1, len(nums)):
key = nums[i]
j = i - 1
while j >= 0 and nums[j] > key:
nums[j + 1] = nums[j]
j -= 1
nums[j + 1] = key
return nums
print(insertion_sort([8, 5, 6, 2, 4])) # [2, 4, 5, 6, 8]
print(insertion_sort([1, 3, 7, 9, 2])) # [1, 2, 3, 7, 9]세 알고리즘을 비교하면 차이가 더 명확하다. 버블 정렬은 인접한 값을 계속 바꾸고, 선택 정렬은 매번 최소값을 선택하고, 삽입 정렬은 현재 값을 정렬된 구간 안에 끼워 넣는다. 모두 O(n²)이지만, 동작 방식이 달라서 배열을 다루는 기본 패턴을 익히기에 좋다.