정렬은 데이터를 일정한 순서로 배치하는 작업이다. Python에서는 보통 sorted()나 리스트의 sort()를 사용하지만, 정렬 알고리즘을 직접 구현해 보면 반복문, 조건문, 시간 복잡도를 함께 이해할 수 있다.
- 버블 정렬(Bubble Sort)
- 선택 정렬(Selection Sort)
- 삽입 정렬(Insertion Sort)
각 알고리즘을 오름차순과 내림차순으로 구현하고, 같은 랜덤 데이터를 사용해 실행 시간을 비교한다.
1. 핵심 특징 비교
| 알고리즘 | 최선 | 평균 | 최악 | 안정 정렬 | 적응형 | 주요 특징 |
|---|---|---|---|---|---|---|
| 버블 정렬 | O(n) | O(n²) | O(n²) | O | O | 인접한 값을 반복해서 교환 |
| 선택 정렬 | O(n²) | O(n²) | O(n²) | X | X | 최솟값 또는 최댓값을 선택 |
| 삽입 정렬 | O(n) | O(n²) | O(n²) | O | O | 정렬된 영역의 알맞은 위치에 삽입 |
버블 정렬의 최선 시간 복잡도
O(n)은 교환 여부를 확인하여 이미
정렬된 경우 반복을 종료하는 최적화를 적용했을 때의 결과다.
세 알고리즘의 정렬 작업 자체는 추가 배열 없이 수행할 수 있으므로 공간 복잡도는 O(1)이다. 이 글의 함수는 원본 데이터를 보존하기 위해 data.copy()를 사용하므로, 함수 전체를 기준으로 보면 복사본에 O(n)의 추가 공간이 필요하다.
원본 데이터를 보존하는 이유 : 나중에 동일한 데이터로 성능을 비교할 때 원본 데이터가 유지되어야 하기 때문이다.
안정 정렬이란?
값이 같은 데이터의 기존 순서를 유지하는 정렬이다.
(80점, 철수), (80점, 영희)점수만 정렬한 뒤에도 철수가 영희보다 앞에 있다면 안정 정렬이다.
적응형 정렬이란?
데이터가 이미 정렬되어 있거나 거의 정렬되어 있을 때 작업량이
줄어드는 정렬을 의미한다.
2. 버블 정렬
버블 정렬은 서로 인접한 두 값을 비교하여 순서가 잘못되어 있으면 교환한다. 한 번의 반복이 끝날 때마다 가장 큰 값이 배열의 오른쪽으로 이동한다.
오름차순 동작 과정
초기 데이터: [5, 3, 8, 4]
5와 3 비교 후 교환: [3, 5, 8, 4]
5와 8 비교 : [3, 5, 8, 4]
8과 4 비교 후 교환: [3, 5, 4, 8]
↑ 가장 큰 값 확정이 과정을 아직 정렬되지 않은 구간에 반복한다.
구현
reverse=False이면 오름차순, reverse=True이면 내림차순으로 정렬한다.
def bubble_sort(data, reverse=False):
# 원본 리스트가 변경되지 않도록 복사본을 만든다.
# 나중에 성능 비교를 위해 원본 리스트를 유지.
result = data.copy()
length = len(result)
# 반복이 끝날 때마다 뒤쪽 값 하나가 정렬되므로 범위를 줄인다.
for end in range(length - 1, 0, -1):
# 교환 여부를 확인해 이미 정렬된 경우 일찍 종료한다.
is_swap = False
# 인접한 두 값을 차례로 비교한다.
for index in range(end):
# 오름차순은 앞의 값이 클 때, 내림차순은 작을 때 교환한다.
if reverse:
swap = result[index] < result[index + 1]
else:
swap = result[index] > result[index + 1]
if swap:
# 현재 값과 다음 값의 위치를 바꾼다.
result[index], result[index + 1] = result[index + 1], result[index]
is_swap = True
# 교환이 없었다면 이미 정렬이 완료된 상태다.
if not is_swap:
break
return resultis_swap이 False라면 한 번의 반복 동안 교환이 없었다는 뜻이다.
이미 정렬이 완료된 상태이므로 반복을 즉시 종료할 수 있다.
장점
- 구현 원리가 단순하여 정렬의 기본 개념을 익히기 좋다.
- 인접한 값만 교환하므로 안정 정렬이다.
- 이미 정렬된 데이터는
O(n)에 처리할 수 있다.
단점
- 평균과 최악의 시간 복잡도가
O(n²)이다. - 데이터가 많아지면 비교와 교환 횟수가 급격하게 증가한다.
- 실무의 일반적인 정렬 작업에는 거의 사용하지 않는다.
3. 선택 정렬
선택 정렬은 정렬되지 않은 영역에서 가장 작은 값을 찾아 맨 앞의 값과 교환한다. 내림차순에서는 가장 큰 값을 선택한다.
오름차순 동작 과정
초기 데이터: [5, 3, 8, 4]
전체에서 최솟값 3 선택: [3, 5, 8, 4]
남은 값에서 4 선택 : [3, 4, 8, 5]
남은 값에서 5 선택 : [3, 4, 5, 8]왼쪽의 정렬된 영역이 한 칸씩 증가한다.
구현
def selection_sort(data, reverse=False):
# 원본 데이터를 보호하기 위해 복사본을 만든다.
# 나중에 성능 비교를 위해 원본 리스트를 유지.
result = data.copy()
length = len(result)
# start 앞쪽은 이미 정렬된 영역이다.
for start in range(length - 1):
# 남은 영역의 첫 번째 위치를 우선 선택한다.
selected = start
# 남은 영역에서 최솟값 또는 최댓값의 위치를 찾는다.
for index in range(start + 1, length):
# 오름차순은 작은 값, 내림차순은 큰 값을 선택한다.
if reverse:
select = result[index] > result[selected]
else:
select = result[index] < result[selected]
if select:
selected = index
# 선택한 값을 정렬되지 않은 영역의 맨 앞으로 이동한다.
if selected != start:
result[start], result[selected] = result[selected], result[start]
return result오름차순에서는 최솟값의 위치를, 내림차순에서는 최댓값의 위치를
selected에 저장한다.
장점
- 구현과 동작 방식이 비교적 단순하다.
- 각 회차에 최대 한 번만 교환하므로 교환 횟수가 적다.
- 입력 데이터의 정렬 상태와 관계없이 실행 흐름이 일정하다.
단점
- 이미 정렬된 데이터도 모든 구간을 비교하므로 항상
O(n²)이다. - 멀리 떨어진 값을 교환하면서 같은 값의 기존 순서가 바뀔 수 있다.
- 기본 구현은 안정 정렬이 아니다.
4. 삽입 정렬
삽입 정렬은 왼쪽 영역이 이미 정렬되어 있다고 가정하고, 현재 값을 왼쪽의 알맞은 위치에 삽입한다. 카드를 한 장씩 뽑아 손에 든 카드 사이의 적절한 위치에 넣는 과정과 비슷하다.
오름차순 동작 과정
초기 데이터: [5, 3, 8, 4]
3을 5 앞에 삽입: [3, 5, 8, 4]
8은 현재 위치 유지: [3, 5, 8, 4]
4를 3과 5 사이에 삽입: [3, 4, 5, 8]구현
def insertion_sort(data, reverse=False):
# 원본 리스트 대신 복사본을 정렬한다.
# 나중에 성능 비교를 위해 원본 리스트를 유지.
result = data.copy()
# 첫 값은 정렬되었다고 보고 두 번째 값부터 시작한다.
for index in range(1, len(result)):
# 정렬된 영역에 삽입할 현재 값을 임시로 보관한다.
current = result[index]
position = index - 1
# 현재 값이 들어갈 위치를 찾으며 앞쪽 값을 이동한다.
while position >= 0:
# 정렬 방향에 따라 오른쪽으로 이동할 값을 결정한다.
if reverse:
move = result[position] < current
else:
move = result[position] > current
# 더 이동할 필요가 없다면 삽입 위치를 찾은 것이다.
if not move:
break
result[position + 1] = result[position]
position -= 1
# 이동 후 생긴 빈자리에 현재 값을 삽입한다.
result[position + 1] = current
return result현재 값보다 큰 값을 오른쪽으로 한 칸씩 이동한 뒤 생긴 자리에 현재
값을 넣는다. 내림차순에서는 현재 값보다 작은 값을 이동한다.
장점
- 구현이 간단하고 안정 정렬이다.
- 이미 정렬된 데이터의 시간 복잡도는
O(n)이다. - 데이터가 적거나 거의 정렬되어 있을 때 효율적이다.
- 값을 매번 교환하지 않고 이동시키므로 버블 정렬보다 빠른 경우가 많다.
단점
- 역순처럼 정렬 상태가 나쁘면 이동 횟수가 많아진다.
- 평균과 최악의 시간 복잡도가
O(n²)이다. - 데이터가 많은 일반적인 정렬에는 적합하지 않다.
5. 오름차순과 내림차순 실행 결과
다음 배열을 세 알고리즘으로 정렬
sample = [5, 3, 8, 4, 2, 7, 1, 6]결과 :
원본: [5, 3, 8, 4, 2, 7, 1, 6]
버블 정렬 오름차순: [1, 2, 3, 4, 5, 6, 7, 8]
버블 정렬 내림차순: [8, 7, 6, 5, 4, 3, 2, 1]
선택 정렬 오름차순: [1, 2, 3, 4, 5, 6, 7, 8]
선택 정렬 내림차순: [8, 7, 6, 5, 4, 3, 2, 1]
삽입 정렬 오름차순: [1, 2, 3, 4, 5, 6, 7, 8]
삽입 정렬 내림차순: [8, 7, 6, 5, 4, 3, 2, 1]6. 랜덤 데이터 성능 비교
구현 방법 (아직 미구현) :
- time, random module 사용
- time.time 각 함수의 시작 시간과 끝나는 시간의 차이를 구해서 성능 비교
- 데이터의 개수를 10개, 100개, 1,000개로 늘려가면서 비교
- 주의 : radom 으로 데이터를 생성할 때 같은 데이터를 불러와야 함으로 seed 설정
7. 어떤 정렬을 선택해야 할까?
버블 정렬
실제 성능이 중요한 작업에서는 선택할 이유가 많지 않다.
선택 정렬
쓰기 또는 교환 비용이 비교 비용보다 큰 상황에서 장점이 있을 수 있다. 하지만 데이터의 기존 순서를 유지해야 한다면 기본 선택 정렬은 적합하지 않다.
삽입 정렬
데이터가 작거나 거의 정렬된 경우 세 알고리즘 중 가장 실용적이다.고성능 정렬 알고리즘에서도 작은 부분 배열을 처리하는 용도로 활용된다.
실제 Python 프로그램
실제 프로그램에서는 직접 구현한 O(n²) 정렬보다 Python의 내장 정렬을
사용하는 것이 일반적이다.
numbers = [5, 3, 8, 4]
ascending = sorted(numbers)
descending = sorted(numbers, reverse=True)Python의 sorted()와 list.sort()는 안정 정렬이며, 평균 및 최악의
시간 복잡도가 O(n log n)인 Timsort를 사용한다.
마무리
버블 정렬, 선택 정렬, 삽입 정렬은 모두 평균 시간 복잡도가 O(n²)인 기본 정렬 알고리즘이다. 데이터가 많을 때는 비효율적이지만 각 알고리즘의 비교, 교환, 이동 방식을 직접 구현하면 정렬과 시간 복잡도를 이해하는 데 도움이 된다.
핵심 차이는 다음과 같이 요약할 수 있다.
- 버블 정렬: 인접한 값을 비교하고 교환한다.
- 선택 정렬: 남은 영역에서 최솟값 또는 최댓값을 선택한다.
- 삽입 정렬: 현재 값을 정렬된 영역의 알맞은 위치에 삽입한다.
세 알고리즘 중에서는 작은 데이터나 거의 정렬된 데이터를 처리할 때 삽입 정렬이 가장 유용하다. 일반적인 실무 코드에서는 직접 구현하기보다 Python의 sorted() 또는 list.sort()를 사용하는 것이 좋다.
코드 구현을 완료하고 든 생각 : 내림차순 정렬은 그냥 오름차순 정렬을 하고 배열을 역순으로 저장해주면 된다는 걸 깨달았다 ㅜㅜ
