All
퀵정렬
분할정복 방식으로 동작하는 정렬 알고리즘으로 하나의 배열을 특정기준(pivot) 중심으로 작은 값과 큰값으로 나누고, 나눠진 배열에 재귀적으로 졍렬 반복
동작원리
•
Pivot(피벗): 배열을 나누는 기준이 되는 값. 보통 배열의 첫 번째 요소를 피벗으로 사용하지만, 임의로 선택할 수도 있음
•
분할(Divide): 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동시켜 피벗이 제자리를 찾도록 정렬
•
정복(Conquer): 나눠진 두 부분 배열을 다시 퀵 정렬로 정렬.
•
재귀적으로 반복하면서 전체 배열을 정렬하게 됩니다.
입력 배열: 30 45 20 15 40 25 35 10
피벗: 30
→ 분할 후: 25 10 20 15 30 40 35 45
설명:
- 피벗 30 기준
- 30보다 작은 값들: 25 10 20 15 → 왼쪽
- 30보다 큰 값들: 40 35 45 → 오른쪽
- 피벗 30은 제자리
- 이후 왼쪽과 오른쪽 배열에 대해 다시 퀵 정렬 반복
Plain Text
복사
성능
최악의 경우 O(n2)
•
항상 극심하게 불균형적으로 분할되는 경우
•
배열이 항상 0:n-1 또는 n-1:0으로 분할되는 경우
◦
즉, 매번 피벗이 가장 크거나 가장 작은 값을 선택했을 때 발생
◦
예를 들어 배열이 이미 오름차순이나 내림차순으로 정렬된 경우, 맨 앞 요소를 계속 피벗으로 지정하면 발생함
•
점화식:
입력 배열: [10, 15, 20, 25, 30, 35, 40, 45] (이미 오름차순 정렬)
피벗 선택 방식: 항상 첫 번째 원소
1번째 분할:
피벗: 10 → 분할: [] | 10 | [15, 20, 25, 30, 35, 40, 45] → (0 : n-1) 분할
2번째 분할:
피벗: 15 → 분할: [] | 15 | [20, 25, 30, 35, 40, 45] → (0 : n-2) 분할
... 계속 반복해서 분할
Plain Text
복사
최선의 경우 O(nlogn)
•
항상 균형적으로 분할
•
배열이 매번 n/2 : n/2로 나뉘는 경우
•
피벗이 매번 중앙값(median)을 선택하여 두 부분배열이 정확히 반반씩 나누어질 때
•
점화식:
평균적인 경우
•
피벗이 중앙값이 아니라도 극단적인 최소/최대값을 피해서 피벗이 선택될때
•
평균적으로 균형잡힌 분할이 일어나고 평균 수행 시간이 O(nlogn)유지
특징
•
피벗 선택의 임의성만 보장되면 최악의 성능이 아닌 평균적인 성능 O(nlogn)을 보일 가능성이 매우 높은 정렬 알고리즘
•
최악 O(n2) 이지만 평균적 O(nlogn)
•
제자리 정렬
•
불안정 정렬
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 = [30, 45, 20, 15, 40, 25, 35, 10]
sorted_arr = quick_sort(arr)
print("정렬된 배열:", sorted_arr)
Python
복사
합병정렬
분할 정복 방식을 활용한 정렬 알고리즘으로, 원본 배열을 계속해서 두개의 부분배열로 나누고 각각 정렬한뒤 정렬된 부분 배열을 합쳐서 하나의 정렬된 배열을 만들어내는 방식
동작 원리
•
분할(Divide): 주어진 배열을 동일한 크기(거의 절반)의 두 부분배열로 나눔
•
정복(Conquer): 각 부분 배열에 순환적으로 합병 정렬을 적용하여 정렬
•
결합(Merge): 정렬된 두 부분 배열을 합병하여 하나의 정렬된 배열을 만듦
퀵 정렬과 달리 합병 정렬은 마지막 결합 단계에서 실질적인 정렬이 완료
입력 배열: [30, 45, 20, 15, 40, 25, 35, 10]
(1) 분할 단계:
[30, 45, 20, 15] | [40, 25, 35, 10]
↓
[30, 45] | [20, 15] | [40, 25] | [35, 10]
↓
[30] [45] [20] [15] [40] [25] [35] [10]
(2) 정복 및 결합 단계(합병):
[30,45] [15,20] [25,40] [10,35]
↓
[15,20,30,45] [10,25,35,40]
↓
최종 정렬된 배열:
[10,15,20,25,30,35,40,45]
Plain Text
복사
합병 함수 Merge()
•
두 개의 이미 정렬된 부분 배열을 받아서 이들을 하나의 정렬된 배열로 합쳐주는 역할
•
합병 함수의 시간 복잡도는 Θ(n) (두 배열의 모든 원소를 한번씩만 비교하며 이동하기 때문)
성능
•
점화식:
•
시간 복잡도:
◦
ALL O(n log n)
•
합병 정렬은 배열의 상태에 상관없이 항상 일정하게 높은 성능 보장
•
안정 정렬
•
합병 단계에서 정렬된 두 부분배열을 저장하기 위해 입력크기 n만큼의 추가저장공간이 필요 > 제자리 정렬이 아님
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에 추가
result.extend(left[i:])
result.extend(right[j:])
return result
# 사용 예시
arr = [30, 45, 20, 15, 40, 25, 35, 10]
sorted_arr = merge_sort(arr)
print("정렬된 배열:", sorted_arr)
Python
복사