H-Log
[알고리즘] 정렬 알고리즘 본문
반응형
정렬 알고리즘
- 합병 정렬 (Merge sort) : O(nlogn)
- 퀵 정렬 (Quick sort) : O(n^2)
- 립 정렬 (Heap sort) : O(nlogn)
합병 정렬 (Merge sort)
- 입력을 2개의 부분 문제로 분할하며 크기가 1/2 씩 감소하는 분할 정복 알고리즘(DC) 이다
- 정렬이 안되어있는 배열 S를 비내림차순으로 정렬하는 과정
- S를 반으로 나누어 A와 B로 명명
- 나눠진 배열을 각각 정렬 (이 때 A가 끝날 때 까지 B는 정렬하지 않음)
- 배열이 1개씩 남을 때 까지 반복 (분할)
- A와 B에 각각 비내림차순 정렬
- A와 B의 앞 index의 수를 비교하며 병합 진행 (정복)
- 시간 복잡도
- 최선의 경우 : A와 B가 이미 정렬이 이미 되어있던 경우 ⇒ A번 또는 B번
- 최악의 경우 : 모든 원소의 비교가 필요한 경우 ⇒ A+B
- 분할
void mergesort (int n, keytype S[]) {
const int h = n/2, m = n-h; // h = 중간 값
keytype A[1..h], B[1..m]; // 중간 값을 기준으로 A와 B로 나눔
if (n > 1) {
copy S[1] through S[h] to A[1] through A[h];
copy S[h+1] through S[n] to B[1] through B[m];
mergesort(h,A); // 배열 A 먼저 모두 분해
mergesort(m,B); // 배열 A 끝난 후 B 모두 분해
merge(h,m,A,B,S); // 병합 함수로 전달
}
}
- 병합
void merge(int h, int m, const keytype A[], const keytype B[], const keytype S[]) {
index i = 1, j = 1, k = 1;
while (i <= h && j <= m) { // h: A배열의 수 , m: B배열의 수
if (A[i] < B[j]) { // A의 배열의 원소가 더 작을 때
S[k] = A[i]; // S에 추가
i++; // A배열의 비교 할 인덱스 위치 +1
} else {
S[k] = B[j]; // B의 배열의 원소가 더 작을 때
j++; // B배열의 비교 할 인덱스 위치 +1
}
k++; // S에 넣을 위치 k에 +1
}
if (i > h)
copy B[j] through B[m] to S[k] through S[h+m];
else
copy A[i] through A[h] to S[k] through S[h+m];
}
- 분석
- 단위연산: merge에서 발생하는 비교연산
- 입력크기: 배열 S에 있는 항목의 개수 n
- T(n): 최악의 경우 ⇒ O(n logn)
퀵 정렬 (Quick sort)
- Partition 알고리즘 이라고도 한다
- 서로의 위치를 교환해가며 정렬한다
Produre partition(p, j){
integer p, j, i
global A(p, j) // p ~ j 위치까지 있는 배열 A (맨 앞 : p, 맨 뒤 : j)
x = A(p) // x: partition element
i = p // 맨 앞 위치인 p (pivot)부터 시작
loop
loop1 i = i+1 until A(i) >= x repeat // i에 1을 더해가며 앞에서부터 기준 값 x보다 큰게 있으면 멈춤
loop2 j = j-1 until A(j) <= x repeat // j에서 1을 빼가며 뒤에서부터 기준 값 x보다 작은게 있으면 멈춤
if i<j then // i가 j보다 작을 땐 A의 i위치와 j위치의 원소 교환
call INTERCHANGE(A(i), A(j))
else exit // i가 j보다 커졌을 때 = 모든 원소를 비교했을 때
repeat // 비교가 끝나지 않았으면 loop1로 가서 다시 비교
A(p) = A(j) // A의 j위치 원소를 맨 앞(x의 위치)으로
A(j) = x // A의 j위치에 기준값 x를 넣어 j와 x 값 교환
}
- partition x를 기준으로 좌/우로 구분만 한 상태가 된다
- 이후 x를 기준으로 좌/우 배열로 나누어 quick sort 진행 (이 때에도 한쪽이 모두 끝날 때 까지 반대쪽은 진행하지 못한다)
- 분석
- 시간 복잡도 : 최악의 경우 O(n^2) / 평균의 경우 O(nlogn
- 시간 복잡도 : 최악의 경우 O(n^2) / 평균의 경우 O(nlogn
반응형
'dev-log > cs' 카테고리의 다른 글
[알고리즘] Dijkstra 알고리즘 (0) | 2023.10.21 |
---|---|
[알고리즘] Greedy 알고리즘 (0) | 2023.10.21 |
[알고리즘] Divaide-and-Conquer (0) | 2023.10.21 |
[알고리즘] 점근적 표기 Big-Oh (0) | 2023.10.21 |
[알고리즘] 시간 복잡도 (0) | 2023.10.20 |
Comments