[알고리즘] 정렬 알고리즘 - 버블정렬(Bubble), 선택정렬(Selection), 삽입정렬(Insertion)
[파이썬 자료구조와 알고리즘] 시간 복잡도, 빅오 표기법(자료구조, 정렬 알고리즘의 시간 복잡프로그램을 개발할때에는 같은 결과를 만들어 내는 코드라도 실행 속도는 천차만별이다. 예를 들
sdesign416.tistory.com
이 전 글에선 정렬중에서도 안정 정렬에 해당하는 삽입 정렬, 버블 정렬, 병합 정렬을 보았다.
이번 글에서는 안정 정렬인 병합정렬과, 불안정 정렬인 퀵 정렬에 대해 살펴 볼 예정이다.
💡 안정 정렬(Stable Sort) 이란?
정렬 후에도 값이 같은 원소들의 순서가 그대로 유지되는 정렬 방식이다.
※ 원래 순서 : 정렬 전의 상대적인 위치
1. 재귀 함수(Recursive Function)란?
재귀 함수는 함수가 자기 자신을 다시 호출하여 문제를 해결하는 방식이다.
복잡한 문제를 더 작고 동일한 형태의 하위 문제로 분해할 수 있으며
하위 문제를 해결하면서 전체 문제를 해결하는 분할 정복 방식이다.
파이썬에서 재귀함수는 1000번까지 횟수가 정해져있어 1000번이상 호출될 경우 오류가 발생하는 규칙이 있다.
재귀 함수를 사용하는 대표적인 알고리즘으로는 퀵 정렬과 병합 정렬이 있다.
1_1) 일반 함수와 재귀 함수의 차이
일반 함수는 외부에서 호출되어 내부의 로직을 수행하고 결과를 반환한다.
재귀 함수는 함수 내부에서 자기 자신을 다시 호출하는 방식으로
복잡한 문제를 더 작은 단위로 쪼개 해결하는 방식이다.
즉, 두 함수의 차이는 함수가 자기 자신을 호출하냐 안하냐의 차이다.
1_2) 재귀 함수와 반복문의 차이
재귀와 반복문은 둘 다 특정 작업을 반복하는 같은 목적을 가지고있긴 하지만
동작하는 방식과 메모리 구조에 차이가 있다.
즉, 반복 작업을 진행하는 방법에 차이가 크다.
| 구분 | 반복문 | 재귀 |
| 동작 방식 | 같은 코드를 반복 실행 | 함수가 자기 자신을 호출 |
| 종료 조건 | 반복 조건이 거짓이 되면 종료 | 종료 조건 만족 시 종료 |
| 메모리 사용 | 적음 | 많음 |
| 속도 | 일반적으로 빠름 | 일반적으로 느림 |
| 코드 길이 | 길어질 수 있음 | 짧고 간결할때가 많음 |
❓ 재귀를 왜 사용할까?
반복문은 같은 작업을 여러번 수행하는 단순 반복 처리에 적합하지만
재귀는 문제를 더 작은 문제로 나눠 해결할 때 적합하다.
일반적인 반복 작업은 반복문을 사용하는것이 좋지만
트리 구조 탐색같은 문제를 계속 분할해야하는 경우엔 재귀를 사용하는것이 더 효율적이다.
1_3) 재귀 함수 종료 조건 (Base Case)
재귀를 사용할때는 종료 조건이 꼭 필요하다.
종료 조건이 없을경우 함수가 계속 자기 자신을 호출하게 되어 무한 반복처럼 동작한다.
그래서 재귀 함수를 작성할때는 종료 조건을 먼저 작성하는것이 좋다.
1_4) 재귀 함수의 장단점
👍 재귀함수 장점
- 문제를 작은 단위로 나눠 해결할 수 있다.
- 트리 구조, 폴더 탐색등 문제를 분할하는 알고리즘 구현에 적합하다.
👎 재귀함수 단점
- 함수 호출이 반복되기 때문에 메모리 사용량이 증가한다.
- 반복문보다 실행속도가 느릴수도 있다.
- 종료 조건을 누락하거나 잘못 작성하면 무한 호출이 발생한다.
- 재귀 호출이 너무 깊어지면 에러가 발생할 수 있다. (Recursion Error)
재귀 함수 사용 예시 1) 팩토리얼 (Factorial)
팩토리얼은 1부터 특정 숫자까지 모두 곱한 값이다.
5! = 5 × 4 × 3 × 2 × 1 = 120
✅ 기능 1) 종료 조건
재귀 함수의 특성상 종료조건이 필요하기 때문에
팩토리얼을 구할 때 더이상 계산할 수 없는 가장 작은값인 1에서 종료조건을 실행시킨다.
❓ 왜 1을 return할까?
팩토리얼은 곱셉 연산으로 이루어져있다.
그렇기 때문에 마지막 값이 1이어야 전체 결과가 유지되기 때문이다.
만약 0을 반환하면 전체 결과가 0이 되기 때문에 팩토리얼의 결과가 잘못된다.
if n == 1:
return 1
✅ 기능 2) 재귀 호출
팩토리얼을 구하는 핵심부분으로 n과 n-1의 팩토리얼 결과를 곱하는 코드이다.
return n * factorial(n-1)
❓ n은 어떻게 줄어들까?
여기서 factorial(n-1) 을 통해 n이 줄어드는데
n 자체가 감소하는것이 아니라,
n보다 1 작은 값을 가진 새로운 함수가 다시 호출되는 구조인것이다.
factorial(n-1)
# 실행 흐름
factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1
= 120즉, 현재 문제를 더 작은 동일한 문제로 계속 나누는 재귀의 방식을 사용한것이다.
- 현재 숫자(n) : 결과를 곱해주는 용도
- factorial(n-1) : 더 작은 문제로 나누는 용도
💡 팩토리얼 최종 코드
def factorial(n):
# 종료 조건
if n == 1:
return 1
# 재귀 호출
return n * factorial(n-1)
print(factorial(5))실행결과 ▶
재귀 함수 사용 예시 2) 피보나치 수열 (Fibonacci)
피보나치 수열은 앞의 숫자를 더해 다음 숫자를 만들어내는 수열이다.
현재 값 = 이전 값 + 이전의 이전 값
1, 1, 2, 3, 5, 8, 13 ...
✅ 기능 1) 종료 조건
피보나치 수열에선 첫 번째와 두 번째 값이 이미 정해져있기 때문에
종료조건을 n이 2 이하일때로 설정하고
더이상 하위 문제로 나누지 않고 수열의 시작 값인 1을 바로 반환한다.
if n <= 2:
return 1
❓ 왜 n <= 2일까?
f(1) = 1
f(2) = 1이건 피보나치 수열 시작의 특성으로
처음과 두번째는 이미 값이 정해져있어 값을 계산 할 필요가 없다.
그래서 1과 2는 그대로 1을 반환하도록 하는것이며,
2일때 종료를 하도록 하는것이다.
✅ 기능 2) 재귀 호출
피보나치 수열의 공식은 f(n) = f(n-1) + f(n-2) 이것과 같은데
이걸 코드로 표현하면 아래와 같아진다.
return fibonacci(n-1) + fibonacci(n-2)
❓ n은 어떻게 줄어들까?
팩토리얼처럼 n이 감소하는 구조가 아닌
더 작은 문제 두개로 나뉘어 새로운 함수가 호출이 되는 구조가 된다.
fibonacci(n-1)
fibonacci(n-2)
# 실행 흐름
fibonacci(5)
= fibonacci(4) + fibonacci(3)
= (fibonacci(3) + fibonacci(2))
+
(fibonacci(2) + fibonacci(1))
# 트리 구조로 확인하기
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
- f(n-1) → 바로 이전 값
- f(n-2) → 두 칸 이전 값
💡 피보나치 수열 최종 코드
def fibonacci(n):
# 종료 조건
if n <= 2:
return 1
# 재귀 호출
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(7))실행결과 ▶
2. 병합 정렬(Merge Sort)
병합 정렬을 대표적인 안정 정렬 알고리즘 중 하나로 분할 정복 방식을 사용한다.
데이터를 더이상 나눌 수 없는 가장 작은 단위로 나눈 뒤, 정렬된 상태로 합치는 방식으로
분할(Divide), 정렬(Sort), 병합(Merge) 3단계의 과정으로 작동한다.
2_1) 병합 정렬의 정렬과정
- 배열을 가운데를 기준으로 절반씩 분할한다.
- 배열의 크기가 1이 될 때 까지 분할을 반복한다.
- 분할된 배열들을 하나씩 합치면서 값을 비교하여 정렬한다.
- 정렬된 배열을 계속 합쳐가면서 전체 정렬을 진행한다.
# 병합 정렬 예시 리스트
[5, 3, 8, 2]
# [1단계 분할]
# 분할 1
# : 중앙을 기준으로 나눈다
[5, 3] [8, 2]
# 분할 2
# : 나눈 리스트에서 또 중앙을 기준으로 나눈다(원소가 1개 될 때 까지)
[5] [3] [8] [2]
# [2단계 정렬, 병합]
# 정렬1
# : 5와 3을 비교 후 정렬, 병합
[3, 5]
# 정렬2
# : 8과 2를 비교 후 정렬, 병합
[2, 8]
# 정렬3
# : [3,5]와 [2,8] 비교 후 정렬, 병합
[2, 3, 5, 8]
# 최종결과
[2, 3, 5, 8]
2_2) 병합 정렬의 시간복잡도와 공간복잡도
2_2_a) 시간 복잡도
병합 정렬은 데이터를 분할하고 병합하는 과정이 일관되게 이뤄진다.
그렇기 때문에 데이터의 정렬 상태와 관계없이 항상 동일한 시간 복잡도를 가진다.
- 평균 / 최선 / 최악 : O(n log n)
2_2_b) 공간 복잡도
병합 정렬은 다시 합치는 과정에서 새로운 리스트를 또 만들어야한다.
그래서 원본 데이터의 크기만큼 추가 메모리가 필요하기 때문에 O(n)의 공간복잡도를 가진다.
- 공간복잡도 : O(n)
2_3) 병합 정렬의 장단점
👍 병합정렬 장점
- 시간 복잡도가 o(n log n)이기 때문에 대규모 데이터에서도 빠른 성능을 유지할 수 있다.
- 최악의 경우에도 O(n log n)의 시간복잡도를 보장한다.
- 같은 값의 순서는 바뀌지 않는다.
👎 병합정렬 단점
- 임시로 하위 배열을 저장하기 위한 추가 메모리 공간이 필요하다.
- 재귀 호출과 병합 프로세스 오버헤드가 발생할 수 있어 소규모 프로젝트에선 오히려 효율성이 떨어진다.
2_4) 병합 정렬 파이썬 코드로 구현하기
병합 정렬의 경우 배열을 분할하고 다시 합치는 과정으로 진행되기 때문에
배열을 반으로 분할하는 함수와 분할이 끝난 뒤 다시 합쳐 줄 함수 2개가 필요하다.
✅ 기능 1) merge_divide_asc함수 if문 : 종료 조건 설정
배열의 길이가 1 이하라면 더 이상 나눌 수 없으며 이미 정렬된 상태이므로 그대로 반환한다.
if len(arr) <= 1: # 탈출 조건
return arr
✅ 기능 2) 배열 절반으로 분할
병합 정렬은 배열을 계속 절반으로 나누어 가장 작은 단위까지 분할한다.
배열의 중간 위치를 구한 후 왼쪽과 오른쪽으로 나누어 각각 다시 병합 정렬을 진행한다.
# 배열의 중간 위치
mid = len(arr) // 2
# 배열의 왼쪽 절반을 정렬(재귀)
left = arr[:mid]
# 배열의 오른쪽 절반을 정렬(재귀)
right = arr[mid:]
✅ 기능 3) merge_combine함수 while문 : 두 배열 비교하며 병합
분할이 끝난 배열들은 하나의 원소만 가지게 된다.
왼쪽 배열과 오른쪽 배열을 앞에서부터 비교하며 더 작은 값을 result에 추가한다.
# 왼쪽과 오른쪽 숫자 남아있을때까지 반복
while i < len(left) and j < len(right):
# 만약 왼쪽 목록 현재 숫자가 오른쪽 현재 숫자보다 작으면
if left[i] < right[j]:
# : 왼쪽 목록의 숫자를 result에 넣고
result.append(left[i])
# : 왼쪽 목록 다음 숫자로 넘어감
i += 1
# 그렇지 않으면 오른쪽을 수행
else:
result.append(right[j])
j += 1
✅ 기능 4) 남은 데이터 추가
한쪽 배열의 모든 데이터를 사용했다면 다른 배열에 남아있는 데이터는 이미 정렬된 상태이므로 그대로 뒤에 붙여준다.
# 반복 끝난 후 왼쪽, 오른쪽 목록에 남은 숫자들 모두 result뒤에 붙임
result += left[i:]
result += right[j:]
✅ 기능 5) 오름차순과 내림차순
부등호만 변경하면 내림차순 정렬을 구현할 수 있다.
# 오름차순
if left[i] < right[j]:
# 내림차순
if left[i] > right[j]:
💡 병합 정렬 최종코드 : 오름차순
# 오름차순 최종코드
import random
# 배열을 계속 반으로 나눌 함수
def merge_divide_asc(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_divide_asc(arr[:mid])
right = merge_divide_asc(arr[mid:])
return merge_combine_asc(left, right)
# 분할이 끝난 배열을 합치는 함수
def merge_combine_asc(left, right): # 이미 정렬된 왼쪽, 오른쪽
result = [] # 합친 결과 담을 빈 목록
i = 0 # 왼쪽 목록의 현재 위치
j = 0 # 오른쪽 목록의 위치
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
random_data = random.sample(range(1,101),5)
print("병합 정렬 전:" , random_data)
print("병합 정렬 후:", merge_divide_asc(random_data))실행결과 ▶ 랜덤 데이터이기 때문에 실행할때마다 결과가 바뀐다.
💡병합 정렬 최종코드 : 내림차순
# 내림차순 최종코드
import random
# 배열을 계속 반으로 나눌 함수
def merge_divide_desc(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_divide_desc(arr[:mid])
right = merge_divide_desc(arr[mid:])
return merge_combine_desc(left, right)
# 분할이 끝난 배열을 합치는 함수
def merge_combine_desc(left, right): # 이미 정렬된 왼쪽, 오른쪽
result = [] # 합친 결과 담을 빈 목록
i = 0 # 왼쪽 목록의 현재 위치
j = 0 # 오른쪽 목록의 위치
while i < len(left) and j < len(right):
if left[i] > right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
random_data = random.sample(range(1,101),5)
print("병합 정렬 전:" , random_data)
print("병합 정렬 후:", merge_divide_desc(random_data))실행결과 ▶ 랜덤 데이터이기 때문에 실행할때마다 결과가 바뀐다.
3. 퀵 정렬(Quick Sort)
퀵 정렬은 분할 정복 알고리즘으로 기준값(Pivot)을 하나 정해서 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누는 방식이다.
나눈뒤엔 왼쪽과 오른쪽의 영역에서 또 같은 방식으로 반복을 진행하며 정렬한다.
퀵정렬은 재귀를 사용하는 대표적인 알고리즘이다.
💡 피벗(Pivot)이란?
피벗은 기준값을 말한다.
퀵정렬에서 사용되는 용어로
피벗보다 작은 값은 왼쪽, 피벗보다 크거나 같은 값은 오른쪽으로 보낸다.
즉, 피벗은 왼쪽과 오른쪽 사이에 위치한다.
3_1) 퀵 정렬의 정렬과정
- 기준값(Pivot)을 하나 선택한다.
- 기준값보다 작으면 왼쪽, 크면 오른쪽으로 분할한다.
- 분할된 배열에서 다시 기준값을 선택하여 과정을 반복한다.
- 배열의 크기가 1이 될 때 까지 분할한 후 다시 결합하여 정렬을 진행한다.
# 퀵 정렬 예시 리스트
[5, 3, 8, 4, 2]
# 1회전
# : 피벗을 첫번째 값인 5로 선택
[3, 2, 4] → 5보다 작은 값(왼쪽)
[8] → 5보다 큰 값(오른쪽)
→ [3, 2, 4] + [5] + [8]
# 2회전
# : 왼쪽 리스트에서 첫번째 값 3 선택
[2] → 3보다 작은 값(왼쪽)
[4] → 3보다 큰 값(오른 쪽)
→ [2] + [3] + [4]
# 3회전
# : 오른쪽 리스트인 8은 값이 1개 → 정렬된것으로 봄
# 최종결과
[2, 3, 4, 5, 8]
3_2) 퀵 정렬의 시간복잡도
3_2_a) 시간 복잡도
퀵 정렬의 시간 복잡도는 피벗 선택에 따라 달라진다.
피벗을 항상 첫번째 값으로 선택하는 경우에
이미 정렬된 리스트가 주어지면 매번 피벗은 가장 작은 값이 된다. [1, 2, 3, 4, 5]
그렇게 될 경우 피벗기준 왼쪽은 계속 비어있고 오른쪽으로만 데이터가 쏠리게 되는데
이렇게 되면 퀵 정렬로 나누는 의미가 없으며 시간복잡도가 O(n²)이 되는것이다.
- 평균 / 최선 : O(n log n)
- 최악 : O(n²)
3_2_b) 공간 복잡도
퀵 정렬은 재귀 호출 스택을 사용하여 스택의 깊이에 따라 공간 복잡도가 결정된다.
배열이 균형 있게 분할될경우 스택의 깊이는 log n이 되고
불균형하게 분할될때는 n이 될 수 있다.
- 평균 / 최선 : O(log n)
- 최악 : O(n)
3_3) 퀵 정렬의 장단점
👍 퀵정렬 장점
- 평균적으로 빠른 속도로 정렬할 수 있다.
- 추가 메모리가 적게 필요하다.
👎 퀵정렬 단점
- 안정 정렬이 아니기 때문에 동일한 값의 순서가 보장되지 않는다.
- 최악의 경우 성능이 좋지않기 때문에 Pivot 선택이 중요하다.
3_4) 퀵 정렬 파이썬 코드로 구현하기
✅ 기능 1) 종료 조건 설정
퀵 정렬은 재귀를 사용하고 있기 때문에 종료조건이 필요하여 종료조건을 추가해주었다.
배열의길이가 1이하일 경우 이미 정렬된 상태이기에 그대로 반환하며 종료
if len(arr) <= 1:
return arr
✅ 기능 2) Pivot(기준값) 선택
퀵 정렬의 기준이 되는 Pivot값을 하나 선택한다.
보통 첫번째값이나 마지막값 또는 중앙값을 사용하는데
예제에선 첫번째 값을 Pivot으로 선택하여 사용하였다.
pivot = arr[0]
✅ 기능 3) 데이터 분할
Pivot 보다 작은값은 왼쪽으로 큰 값은 오른쪽으로 데이터를 분할하여
각각 left, right 리스트에 담는다.
left = []
right = []
#피벗을 제외한 나머지 숫자들 확인
for i in range(1,len(arr)):
# 피벗보다 작으면 left에추가
if arr[i] < pivot:
left.append(arr[i])
# 피벗보다 크면 right에 추가
else:
right.append(arr[i])
✅ 기능 4) 재귀 호출, 결과 결합
left목록을 퀵 정렬한 결과와 right를 퀵 정렬한 결과 사이에
pivot을 넣어 하나의 리스트로 합친 후 반환한다.
return quick_sort(left) + [pivot] + quick_sort(right)
✅ 기능 5) 오름차순과 내림차순
for문 안의 if문 비교연산자 부등호만 바꾸면 사용할 수 있다.
# 오름차순
if arr[i] < pivot:
# 내림차순
if arr[i] > pivot:
💡 퀵 정렬 최종코드 : 오름차순
# 오름차순 최종코드
import random
def quick_asc(array):
if len(array) <= 1:
return array
pivot = array[0]
left = []
right = []
for i in range(1,len(array)):
if array[i] < pivot:
left.append(array[i])
else:
right.append(array[i])
return quick_asc(left) + [pivot] + quick_asc(right)
random_data = random.sample(range(1,101),5)
print("퀵 정렬 전:" , random_data)
print("퀵 정렬 후:", quick_asc(random_data))실행결과 ▶ 랜덤 데이터이기 때문에 실행할때마다 결과가 바뀐다.
💡 퀵 정렬 최종코드 : 내림차순
# 내림차순 최종코드
import random
def quick_desc(array):
if len(array) <= 1:
return array
pivot = array[0]
left = []
right = []
for i in range(1,len(array)):
if array[i] > pivot:
left.append(array[i])
else:
right.append(array[i])
return quick_asc(left) + [pivot] + quick_asc(right)
random_data = random.sample(range(1,101),5)
print("퀵 정렬 전:" , random_data)
print("퀵 정렬 후:", quick_desc(random_data))실행결과 ▶ 랜덤 데이터이기 때문에 실행할때마다 결과가 바뀐다.
4. 퀵 정렬과 병합 정렬 비교
💡 퀵 정렬이 유리한 경우
평균적으로 빠른 속도가 필요한 경우 퀵 정렬이 더 유리하다.
또한 추가 메모리를 많이 쓰고싶지 않을 때(메모리가 한정적일때)에도 퀵 정렬이 더 유리하다.
💡 병합 정렬이 유리한 경우
항상 안정적인 성능을 유지해야할 때 병합 정렬이 유리하다.
최악의 경우에도 O(n log n)의 시간복잡도를 보장해야하는 상황일 때 병합 정렬이 더 유리하며
안정 정렬이 필요한 경우 퀵 정렬보다 병합 정렬이 더 유리하다.
'Python > 자료구조 & 알고리즘' 카테고리의 다른 글
| [알고리즘] 탐색 알고리즘② - 깊이 우선 탐색 (DFS), 너비 우선 탐색 (BFS) (0) | 2026.06.16 |
|---|---|
| [알고리즘] 탐색 알고리즘① - 선형 탐색(Linear), 이진 탐색(Binary) (0) | 2026.06.11 |
| [알고리즘] 정렬 알고리즘① - 버블정렬(Bubble), 선택정렬(Selection), 삽입정렬(Insertion) (0) | 2026.06.10 |
| [자료구조] 힙(Heap)- 힙 동작과정, 힙의 시간복잡도, 파이썬 코드로 구현하기 (0) | 2026.06.08 |
| [자료구조와 알고리즘] 공간 복잡도 (0) | 2026.06.07 |