안녕하세요, 루카입니다.
이번 포스트에서는 크래프톤 정글 WEEK01 에서 공부했던 정렬에 대해서 살펴보도록 하겠습니다.
목차
1. 버블 정렬(Bubble Sort)
2. 선택 정렬(Selection Sort)
3. 삽입 정렬(Insertion Sort)
4. 퀵 정렬(Quick Sort)
5. 병합 정렬(Merge Sort)
6. 힙 정렬(Heap Sort)
7. 계수 정렬(Counting Sort)
8. 기수 정렬(Radix sort)
버블 정렬(Bubble Sort)
❓버블 정렬(Bubble Sort)이란?
버블 정렬은 가장 간단한 정렬 알고리즘 중 하나입니다.
해당 원소(i)와 옆에 있는 원소(i + 1)와 비교해서 더 큰 값을 뒤로(또는 더 작은 값을 앞으로) 보내는 방식으로, 마치 물 속의 거품이 위로 올라가는 모습과 비슷해서 버블(Bubble) 이라는 이름이 붙었습니다.
⚙️ 정렬 과정
1. 첫 번째 반복
- 맨 앞 원소부터 시작해서, 바로 옆 원소와 비교합니다.
- 앞 원소가 더 크면 서로 교환
- 마지막 원소까지 반복 - 이 과정을 거치면 가장 큰 원소가 맨 뒤로 이동됩니다.
2. 두 번째 반복
- 마지막 원소는 이미 정렬됐으므로, 그 전까지만 반복합니다.
- 다시 같은 방식으로 가장 큰 값을 뒤로 보냅니다.
3. 이 과정을 배열의 길이 -1번 반복하면 해당 배열의 전체가 정렬됩니다.
💡시간 복잡도(Time Complexity)
- 최악(Worst)/평균(Average) 시간 복잡도 : O(n²)
- 최선(Best) 시간 복잡도 : O(n) (이미 정렬된 경우 - 이 때는 flag 사용 시)
💻 예제 코드 - Python
arr = [5, 3, 8, 4, 2]
n = len(arr)
for i in range(n):
# 마지막 i개는 이미 정렬되어 있으므로 그 전까지만 비교
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
# swap
arr[j], arr[j + 1] = arr[j + 1], arr[j]
print("정렬 결과:", arr)✅ 장점과 단점
- 장점 : 구현이 매우 간단하다.
- 단점 : 성능이 좋지 않아 실제로는 거의 사용되지 않는다.
선택 정렬(Selection Sort)
❓선택 정렬(Selection Sort)란?
선택 정렬은 가장 작은(또는 가장 큰) 원소를 선택해서 맨 앞으로 보내는 방식의 정렬 알고리즘 입니다.
한마디로, 정렬되지 않은 부분에서 가장 작은 값을 찾아 맨 앞으로 보내고, 그 부분을 점점 줄여나가는 방식입니다.
⚙️ 정렬 과정
- 배열의 첫 번째 위치부터 시작합니다.
- 현재 위치 이후의 요소 중 가장 작은 값을 찾아 현재 위치와 교환합니다.
- 다음 위치로 이동하여 같은 과정을 반복합니다.
- 배열의 끝까지 수행하면 전체가 정렬됩니다.
💡시간 복잡도(Time Complexity)
- 전체 시간 복잡도 : O(n²)
- 공간 복잡도 : O(1) - (추가 메모리를 거의 사용하지 않습니다.)
💻 예제 코드 - Python
arr = [5, 3, 8, 4, 2]
n = len(arr)
for i in range(n):
min_idx = i
# i 이후의 원소 중 가장 작은 원소를 찾음
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
# 가장 작은 원소를 i번째 원소와 교환
arr[i], arr[min_idx] = arr[min_idx], arr[i]
print("정렬 결과:", arr)✅ 장점과 단점 그리고 특징
- 장점 : 구현이 간단하고, 추가 공간이 거의 필요 없습니다.
- 단점 : 모든 경우에서 O(n²) 시간이 걸려 효율이 좋지 않습니다.
- 특징 : 교환 횟수가 최대 n번으로 비교적 적습니다.
삽입 정렬(Insertion Sort)
❓삽입 정렬(Insertion Sort)란?
삽입 정렬은 자료를 하나씩 확인하면서, 이미 정렬된 부분에 알맞은 위치해 삽입하는 방식의 알고리즘입니다.
마치 우리가 트럼프 카드를 한 장씩 손에 들고, 정렬된 순서로 끼워 넣는 방식과 비슷합니다.
⚙️ 정렬 과정
- 첫 번째 원소는 이미 정렬된 상태라고 가정합니다.
- 두 번째 원소부터 시작해서 "왼쪽(이미 정렬된 부분)"과 비교합니다.
- 현재 원소보다 큰 원소들을 오른쪽으로 한 칸씩 밀어주고, 알맞은 위치에 삽입합니다.
- 이 과정을 배열의 끝까지 반복합니다.
💡시간 복잡도(Time Complexity)
- 최악(Worst)/평균(Average) 시간 복잡도 : O(n²) (역순일 때)
- 최선(Best) 시간 복잡도 : O(n) (이미 정렬된 경우)
- 공간 복잡도 : O(1)
💻 예제 코드 - Python
arr = [5, 3, 8, 4, 2]
n = len(arr)
for i in range(1, n):
key = arr[i] # 현재 삽입할 값
j = i - 1
# key보다 큰 값들을 한 칸씩 뒤로 이동
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key # 삽입
print("정렬 결과:", arr)
✅ 장점과 단점 그리고 특징
- 장점 : 구현이 간단하고, 거의 정렬된 배열에 매우 빠릅니다.
- 단점 : 역순일 때 느립니다. (O(n²))
- 특징 : 안정 정렬(같은 값의 순서가 유지됨)
퀵 정렬(Quick sort)
❓퀵 정렬(Quick Sort)이란?
퀵 정렬은 분할 정복(Divide and Conquer) 기법을 사용하는 매우 빠른 정렬 알고리즘 입니다.
퀵 정렬에서는 피벗(Pivot)이 정말 중요한데요.! 이 의미를 한번 짚고 넘어가 보도록 하겠습니다.
피벗(Pivot)이란?
피벗(Pivot)은 퀵 정렬(Quick Sort)에서 기준이 되는 값 입니다.
- 배열을 작은 값과 큰 값으로 나누기 위해 사용하는 기준점 역할을 합니다.
- 피벗을 기준으로 왼쪽에는 피벗보다 작은 값, 오른쪽에는 피벗보다 큰 값을 배치합니다.
- 이렇게 나눈 뒤, 왼쪽과 오른쪽 배열을 각각 재귀적으로 다시 정렬합니다.
피벗(Pivot)이 왜 필요한가 ?
정렬 알고리즘의 핵심은 배열을 작은 단위로 나누는 것입니다.
피벗이 바로 이 "나누기"의 중심 역할을 하며, 분할 정복(Divide and Conquer) 전략을 가능하게 합니다.
✅ 퀵 정렬(Quick Sort)의 핵심
- 피벗(Pivot)을 하나 고릅니다.
- 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽에 분할합니다.
- 왼쪽과 오른쪽 부분 배열을 다시 퀵 정렬로 재귀적으로 정렬합니다.
⚙️ 정렬 과정
- 배열에서 피벗을 선택합니다.
- 배열을 피벗을 기준으로 작은 값/ 피벗 / 큰 값 세 구역으로 나눕니다.
- 왼쪽과 오른쪽 부분 배열에 대해 재귀적으로 같은 작업을 수행합니다.
- 더 이상 나눌 배열이 없으면 정렬이 완료됩니다.
💡시간 복잡도(Time Complexity)
- 평균(Average) 시간 복잡도 : O(n log n)
- 최악(Worst) 시간 복잡도 : O(n²) (피벗을 최악으로 선택한 경우, 예시로 이미 정렬된 배열에서 첫 번쨰 요소를 피벗으로 선택)
- 공간 복잡도 : O(log n) (호출 스택)
💻 예제 코드 - Python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0] # 첫 번째 요소를 피벗으로 선택
left = [x for x in arr[1:] if x <= pivot]
right = [x for x in arr[1:] if x > pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
arr = [5, 3, 8, 4, 2, 7, 1, 10]
sorted_arr = quick_sort(arr)
print("정렬 결과:", sorted_arr)
✅ 장점과 단점 그리고 특징
- 장점 : 평균적으로 매우 빠르고, 실무에서 많이 사용됩니다.
- 단점 : 최악의 경우 느려질 수 있습니다.(보완하기 위해 랜덤 피벗 선택을 하는 등 사용합니다.)
- 특징 : 비교 기반 정렬, 제자리(in-place) 정렬 가능 (추가 배열을 안 쓰고 포인터만 사용한다면)
병합 정렬(Merge Sort)
❓병합 정렬(Merge Sort)이란?
병합 정렬은 분할 정복(Divide and Conquer) 전략을 사용한 정렬 알고리즘 입니다.
큰 문제(배열)를 작은 부분 배열로 계속 나눈 다음, 각 부분 배열을 정렬하고, 마지막에 두 개씩 합치면서 정렬된 배열을 완성합니다.
⚙️ 정렬 과정
1️⃣ 분할(Divide)
- 배열을 반으로 계속 나눕니다.
- 원소가 1개가 될 때까지 나눕니다.
2️⃣ 정복(Conquer, 병합)
- 나눈 배열을 작은 순서대로 합치면서 정렬합니다.
3️⃣ 결합(Combine)
- 모든 배열을 병합하여 하나의 정렬된 배열을 완성합니다.
💡시간 복잡도(Time Complexity)
- 모든 경우(최악(Worst), 평균(Average), 최선(Best)) : O(n log n)
- 공간 복잡도 : O(n) (추가 배열 필요)
💻 예제 코드 - Python
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
# 두 리스트를 비교하며 작은 값을 result에 추가
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.extend(left[i:])
result.extend(right[j:])
return result
arr = [5, 3, 8, 4, 2, 7, 1, 6]
sorted_arr = merge_sort(arr)
print("정렬 결과:", sorted_arr)✅ 장점과 단점 그리고 특징
- 장점 : 항상 O(n log n), 데이터 크기에 상관없이 안정적입니다.
- 단점 : 추가 배열이 필요합니다. (메모리 공간을 많이 씀)
- 특징 : 안정 정렬 (같은 값의 순서가 유지됩니다.)
힙 정렬(Heap Sort)
❓힙 정렬(Heap Sort)이란?
힙 정렬은 완전 이진 트리 형태인 힙(Heap) 자료구조를 이용한 정렬 알고리즘입니다.
여기서 힙은 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 사용할 수 있는데, 보통 최대 힙을 사용해서 가장 큰 값을 하나씩 꺼내 뒤에서부터 채워나가는 방식으로 정렬합니다.
힙(Heap) 구조
- 최대 힙 : 부모 노드 ≥ 자식 노드 (루트가 가장 큽니다.)
- 최소 힙 : 부모 노드 ≤ 자식 노드 (루트가 자장 작습니다.)
힙(Heap)은 배열로 구현할 때, 인덱스 기반 완전 이진 트리로 표현됩니다.
- 부모 노드 : i
- 왼쪽 자식 : 2i + 1
- 오른쪽 자식 : 2i + 2
⚙️ 정렬 과정
1️⃣ 배열을 힙 구조로 변환(힙화, Heapify)
- 전체 배열을 최대 힙으로 만듭니다.
2️⃣ 힙의 루트(최댓값)를 배열 끝으로 보냅니다.
- 루트 값(가장 큰 값)을 마지막 값과 교환합니다.
- 배열 크기를 1 줄이고, 다시 힙화(Heapify)합니다.
3️⃣ 과정 반복
- 전체 배열이 정렬될 때까지 계속 반복합니다.
💡시간 복잡도(Time Complexity)
- 전체 시간 복잡도 : O(n log n)
- 공간 복잡도 : O(1) (제자리 정렬)
💻 예제 코드 - Python
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# 힙 빌드
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 루트와 마지막 원소 교환 후 힙화 반복
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print("정렬 결과:", arr)✅ 장점과 단점 그리고 특징
- 장점 : 추가 메모리가 거의 필요 없습니다, 항상 O(n log n).
- 단점 : 안정 정렬이 아닙니다. (같은 값의 순서가 보장되지 않아요.)
- 특징 : 완전 이진 트리 형태, 제자리 정렬.
계수 정렬(Counting Sort)
❓계수 정렬(Counting Sort)이란?
계수 정렬은 정수나 정수 형태로 표현할 수 있는 값들을 정렬할 때 사용합니다.
각 원소가 가질 수 있는 최대값과 최소값 범위를 알고 있을 때 효과적입니다.
⚙️ 정렬 과정
1️⃣ 카운트 배열(Counting Array) 생성
- 원본 배열의 각 값이 몇 번 나오는지 세어서 카운트 배열에 저장합니다.
2️⃣ 카운트 배열 누적합 계산
- 해당 값보다 작은 값이 몇 개 있는지를 알기 위해 누적합을 구합니다.
3️⃣ 출력 배열 생성
- 누적합 정보를 이용해 원본 배열의 값을 정렬된 위치에 배치합니다.
💡시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)
- 시간 복잡도 : O(n + k)
- n : 입력 배열 크기
- k : 정수의 최댓값
- 공간 복잡도 : O(n + k)
⚠️ 제한점 : 값의 범위(k)가 매우 크면 메모리 사용이 커져서 비효율적!
💻 예제 코드 - Python
def counting_sort(arr):
max_val = max(arr)
count = [0] * (max_val + 1)
# 카운트 배열에 각 값의 개수 기록
for num in arr:
count[num] += 1
# 카운트 배열 누적합
for i in range(1, len(count)):
count[i] += count[i - 1]
result = [0] * len(arr)
# 뒤에서부터 순회하며 안정적으로 정렬
for num in reversed(arr):
result[count[num] - 1] = num
count[num] -= 1
return result
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print("정렬 결과:", sorted_arr)✅ 장점과 단점 그리고 특징
- 장점 : 매우 빠르고, O(n + k) 시간에 정렬이 가능합니다.
- 단점 : 범위(k)가 큰 경우 공간 낭비가 심합니다.
- 특징 : 안정 정렬 (같은 값의 원래 순서를 유지합니다.)
기수 정렬(Radix Sort)
❓기수 정렬(Radix Sort)이란?
기수 정렬은 자리수(Digit)별로 정렬을 반복하면서 전체를 정렬하는 알고리즘입니다.
주로 정수나 문자열 등, 자릿수나 길이가 정해져 있는 데이터에 사용됩니다.
⚙️ 정렬 과정
1️⃣ 가장 낮은 자리수(Least Significant Digit, LSD) 부터 시작해서,
- 원본 배열의 각 값이 몇 번 나오는지 세어서 카운트 배열에 저장합니다.
2️⃣ 한 자리씩 올라가면서 같은 방식으로 정렬합니다.
3️⃣ 마지막 자리까지 진행하면 전체가 정렬됩니다.
⚠️ 각 자리별 정렬 시 안정 정렬(Stable Sort) 을 사용해야 합니다. (예: 계수 정렬)
💡시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)
- 시간 복잡도 : O(d * (n + k))
- d : 최대 자리수
- n : 데이터 개수
- k : 자릿수 범위 (예 : 0~9)
- 공간 복잡도 : O(n + k)
💻 예제 코드 - Python
def counting_sort_digit(arr, digit):
n = len(arr)
output = [0] * n
count = [0] * 10 # 0~9 숫자
# 해당 자리수 값의 개수 세기
for num in arr:
idx = (num // digit) % 10
count[idx] += 1
# 누적합
for i in range(1, 10):
count[i] += count[i - 1]
# 안정적으로 배열에 넣기 (뒤에서부터)
for i in range(n - 1, -1, -1):
idx = (arr[i] // digit) % 10
output[count[idx] - 1] = arr[i]
count[idx] -= 1
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
max_num = max(arr)
digit = 1
while max_num // digit > 0:
counting_sort_digit(arr, digit)
digit *= 10
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("정렬 결과:", arr)
✅ 장점과 단점 그리고 특징
- 장점 : 비교 기반이 아니어서, 큰 데이터에 대해 O(n) 근처 속도 가능
- 단점 : 자리수가 긴 경우 느릴 수 있고, 추가 공간이 필요합니다.
- 특징 : 안정 정렬(자리별 정렬이 안정 정렬일 때)
여기까지 다양한 정렬 알고리즘을 알아보았습니다.
정렬은 알고리즘의 기본 중의 기본인데요..! 최대한 잘 활용해서 알고리즘을 맛있게 풀어봅시다 !!
화이팅..!
'크래프톤 정글' 카테고리의 다른 글
| 크래프톤 정글 Week0 - 회고록(미니 프로젝트) (1) | 2025.07.10 |
|---|