기타 정렬 알고리즘 - Merge-Sort, Quicksort : Recursive한 알고리즘
(ChatGPT) 두 알고리즘 모두 - 비교 기반 정렬 알고리즘 - Divide-and Conquer(분할 정복) 기법 활용 - Recursive한 알고리즘
1) MERGE-SORT
(ChatGPT) - Merge Sort는 분할 정복(Divide-and-Conquer)을 활용하는 정렬 알고리즘으로, 이 MERGE 함수는 두 개의 정렬된 부분 배열을 병합하여 최종적으로 정렬된 하나의 배열로 만드는 핵심 역할을 함 - Merge Sort는 재귀적으로 배열을 반으로 나누어 각각 정렬한 뒤, 그 정렬된 부분을 병합(merge)하는 과정에서 정렬을 완성 - 이 MERGE 함수는 두 개의 정렬된 배열을 받아 하나의 정렬된 배열로 합치는 역할을 함 - 두 배열이 이미 정렬된 상태이기 때문에, 각 배열의 첫 번째 원소를 비교하면서 작은 값을 먼저 합친다. - 이 과정은 O(n)의 시간 복잡도로 진행 (n : 두 배열의 총 원소 수)
MERGE-SORT(A, p, r)
(Chat GPT) - Merge Sort는 본질적으로 이미 정렬된 두 부분 배열을 병합(merge)하는 방식으로 작동 - 하지만 이 과정이 단순히 정렬된 배열을 병합하는 데 그치지 않고, 배열 전체를 재귀적으로 나눠 정렬하는 과정이 포함 1) 분할(Divide) : 배열을 절반으로 나누는데, 이 과정을 더 이상 나눌 수 없을 때까지 재귀적으로 반복 2) 정복(Conquer) : 배열이 길이가 1인 부분 배열로 나뉘면, 그 배열은 이미 정렬된 상태로 간주하고, 정렬된 두 부분 배열을 병합하여 다시 위로 올라감 3) 병합(Combine) : 두 개의 정렬된 부분 배열을 하나의 정렬된 배열로 만듦. 각 병합 단계에서는 두 부분 배열의 첫 번째 원소부터 비교하면서 작은 값을 먼저 결과 배열에 추가
(Merge Sort 예시)
[코드 전체 흐름]
배열을 두 부분으로 나눔(divide) : 중간 인덱스 q를 계산해 배열을 왼쪽과 오른쪽으로 재귀적으로 나눔
각 부분을 정복(conquer) : 배열의 크기가 1이 될 때까지 재귀 호출
두 부분을 병합(combine) : 재귀적으로 정렬된 두 부분을 병합하여 최종 정렬된 배열을 만든다.
(1) p, r : 배열의 시작과 끝 인덱스
- 이 조건은 배열에 두 개 이상의 원소가 있을 때에만 더 이상 분할 및 정렬이 필요하다는 것을 의미
- p >=r이면 배열의 크기가 1 이하이므로 이미 정렬된 상태
(2) 중간 인덱스 q를 계산
- ⌊(p + r) / 2⌋ : 배열을 반으로 나누기 위해 사용 (floor 연산 : 소수점 아래 버림)
(3) 배열의 왼쪽 절반(p부터 q까지)를 재귀적으로 정렬
- 이 호출은 계속해서 배열을 반으로 나누며 정렬
(4) 배열의 오른쪽 절반(q+1부터 r까지)를 재귀적으로 정렬
- 이 호출도 왼쪽 절반과 마찬가지로 계속해서 배열을 나누며 정렬합니다.
(5) 배열의 왼쪽 절반(p ~ q)과 오른쪽 절반(q + 1 ~ r)이 정렬된 상태로 병합 - 이 과정은 두 정렬된 부분을 하나의 정렬된 배열로 결합하는 단계 - 병합 과정에서는 두 배열의 첫 번째 원소부터 비교하여 작은 값을 먼저 복사
MERGE(A, p, q, r) : 두 개의 정렬된 배열을 받아서 하나의 배열로 정렬시키면서 합침
(1) ~ (3) : 보조 배열 생성 및 준비
(1) : 왼쪽 부분 배열의 길이를 계산 (p에서 q까지)
(2) : 오른쪽 부분 배열의 길이를 계산 (q+1에서 r까지)
(3) :L과 R이라는 두 개의 보조 배열을 만든다.
- 각각 왼쪽 절반(L)과 오른쪽 절반(R)을 저장할 공간
- 각각의 크기는 n1 + 1과 n2 + 1인데, 이때 +1은 무한대(∞)를 추가할공간을 미리 포함한 것
→ 이렇게 하면, 남아 있는 배열의 원소가 모두 처리된 이후에도 남은 원소가 있는지를 쉽게 판단 가능 (즉, 경계 조건을 단순화하는 역할)
(4) ~ (9) : 왼쪽과 오른쪽 배열 복사
(4) ~ (5) : A의 왼쪽 절반(p부터 q까지)의 데이터를 L에 복사
(6) ~ (7) : A의 오른쪽 절반(q+1부터 r까지)의 데이터를 R에 복사
(8) ~ (9) : 두 배열의 마지막에 무한대를 추가
(10) ~ (11) : 인덱스 초기화
- i : 보조배열 L의 인덱스
- j : 보조배열 R의 인덱스
(12) ~ (17) : 병합하면서 정렬
(12) : 배열 A의 p부터 r까지(즉, 정렬해야 할 전체 구간) 반복합니다.
(13) ~ (15) : L[i]가 R[j]보다 작거나 같으면,L[i]를 A[k]에 복사
- 그런 다음 i를 증가시켜 L의 다음 원소로 이동
(16) ~ (17) : 만약 R[j]가 더 작다면, R[j]를 A[k]에 복사
- 그런 다음 j를 증가시켜 R의 다음 원소로 이동
(결과)이 과정이 끝나면, A[p..r]에는 두 부분 배열이정렬된 상태로 병합
2) QUICKSORT
(Chat GPT)
1. 핵심 아이디어 - 퀵 정렬은 분할 정복(Divide-and-Conquer) 기법을 사용 - 배열에서 pivot(피벗)을 하나 선택하고, 이 피벗을 기준으로 작은 값과 큰 값을 나눈다 - 피벗보다 작거나 같은 값은 왼쪽, 큰 값은 오른쪽에 배치 - 이후 왼쪽과 오른쪽 부분 배열을 재귀적으로 정렬
2. Quick Sort의 과정
Merge Sort와 다른점 - Quick Sort는 분할 인덱스를 따로 지정할 필요가 없고, 왼쪽과 오른쪽 배열을 합칠 때 추가적인 정렬 과정이 필요하지 않음. 재귀 호출이 끝난 시점에서 이미 배열이 정렬된 상태로 완성됨 - 즉, Merge Sort는 분할 후 병합을 하는 반면, QuickSort는 정렬이 동시에 이루어지는 특징이 있음
3. 예시
- 피벗 원소와의 비교 정렬 이후 순서가 보존되지는 않음
QUICKSORT(A, p, r)
주어진 배열을 두 부분으로 나눈 뒤, 각 부분을 재귀적으로 정렬하는 방식으로 동작
- Partition 단계: 배열을 두 부분으로 나눔. 기준값(피벗, pivot)을 기준으로, 작은 값들은 왼쪽으로, 큰 값들은 오른쪽으로 이동 - 재귀 호출 단계: 나누어진 두 부분에 대해 다시 QuickSort를 호출하여 정렬을 완성
- 종료 조건: 배열의 크기가 1 이하일 때 정렬을 멈춘다.
(1) 종료 조건 : 배열의 크기가 1 이하일 때
(2) 배열을 분할하고 피벗 위치 반환
(3) 왼쪽 부분 정렬
(4) 오른쪽 부분 정렬
예시 코드 : QuickSort
def quicksort(A, p, r):
if p < r: # (1) 종료 조건: 배열의 크기가 1 이하일 때
q = partition(A, p, r) # (2) 배열을 분할하고 피벗 위치 반환
quicksort(A, p, q - 1) # (3) 왼쪽 부분 정렬
quicksort(A, q + 1, r) # (4) 오른쪽 부분 정렬
def partition(A, p, r):
x = A[r] # (1) 피벗 선택: 마지막 원소를 피벗으로
i = p - 1 # (2) 작은 값의 마지막 위치 추적
for j in range(p, r): # (3) 배열 순회
if A[j] <= x: # (4) 피벗보다 작거나 같으면
i = i + 1 # (5) i를 증가시키고
A[i], A[j] = A[j], A[i] # (6) A[i]와 A[j] 교환
A[i + 1], A[r] = A[r], A[i + 1] # (7) 피벗을 올바른 위치로 이동
return i + 1 # (8) 피벗의 최종 위치 반환
PARTITION(A, p, r)
- Lumoto Partition 방식(피벗을 마지막 원소로 선택)
→ hoare 방식 : 오리지널
- q를 찾는 알고리즘
x : 피벗
(1) ~ (2) : 피벗 선택과 i 인덱스 초기화
(1) 피벗 선택 : 배열의 마지막 원소를 피벗으로 선택함 - 이 값을 기준으로 작은 값과 큰 값을 나눌 것
- 피벗의 왼쪽에는 작은 값들이, 오른쪽에는 큰 값들이 위치하게 될 것
(2) i 인덱스 초기화
- 피벗보다 작은 값들의 마지막 위치를 추적하는 인덱스 → 처음에는 p - 1로 초기화 (아직은 작은 값이 발견되지 않았음을 의미)
(3) ~ (6) : 배열을 순회하며, 피벗보다 작은 값을 찾고 교환
(3) j 인덱스로 배열 순회
- 배열의 처음부터 피벗 직전까지 순회하면서, 각 원소가 피벗보다 작은지 확인
(4) 조건문으로 피벗과 비교
- 현재 원소 A[j]가 피벗 x보다 작거나 같으면, 이 원소는 피벗의 왼쪽 부분에 있어야 한다.
(5)~(6) 피벗보다 작은 원소가 발견되면, i를 하나 증가시킨 후 A[i]와 A[j]를 교환하여, 피벗보다 작은 값을 앞으로 이동시킨다. - 이 작업을 통해 작은 값들은 왼쪽으로, 큰 값들은 오른쪽에 남도록 만든다.
(7) 순회가 끝나면 피벗을 제자리에 배치
(8) 피벗의 위치를 반환하여 QuickSort가 재귀 호출됨
예시 코드 : Partition
1 x ← A[r] # (1) 피벗 선택
2 i ← p - 1 # (2) i 초기화 (피벗보다 작은 값들의 마지막 위치)
3 for j ← p to r - 1 # (3) j로 배열 순회 시작
4 if A[j] ≤ x # (4) A[j]가 피벗보다 작거나 같으면
5 i ← i + 1 # (5) i 인덱스 증가 (작은 값 위치 준비)
6 exchange A[i] ↔ A[j] # (6) A[i]와 A[j] 교환 (작은 값 앞으로 이동)
7 exchange A[i + 1] ↔ A[r] # (7) 피벗을 올바른 위치로 이동
8 return i + 1 # (8) 피벗의 최종 위치 반환
