알고리즘 요약
병합정렬 (merge sort)
-리스트를 반으로 나누고, 각 리스트가 크기가 1이 될 때까지 반으로 나누면서 정렬 후 병합
-안정적이고 대규모 데이터에서도 속도 빠름.
-시간복잡도: O(n log n)
정렬과정 설명
[3, 2, 5, 4, 1] :숫자열이 있을 경우,
[3, 2], [5, 4, 1] :배열을 반으로 나눈다.
[ [3],[2] ], [ [5], [ [4], [1] ] ] : 하나씩 될 때까지 계속 나눈다.
[ 2, 3 ] [ 5, [1, 4] ] : 각값을 비교하면서 병합하면 부분적으로 정렬이 된다.
[2, 3], [1, 4, 5] : 각각 정렬된 부분들을 하나씩 꺼내면서 비교해서 정렬
[1, 2, 3, 4, 5] : 정렬 끝
# 분리된 목록을 정렬해서 병합하는 함수
def merge(left, right):
i, j = 0, 0
l_left, l_right = len(left), len(right) # 좌우 목록 크기
a = [] # 병합해서 저장할 리스트
while i < l_left and j < l_right: # 좌우 목록중 비교값이 끝날 때 까지 루프
if left[i] < right[j]: # 좌측값이 작으면 그 값을 가져옴
a.append(left[i])
i += 1
else: # 우측목록에 있는 값이 작으면 그 값을 가져옴
a.append(right[j])
j += 1
# 좌우 리스트에 남은 항목이 있으면 모두 차례로 가져옴
while i < l_left:
a.append(left[i])
i += 1
while j < l_right:
a.append(right[j])
j += 1
return a
# 목록을 하나가 될 때 까지 반복해서 분리한 후 merge를 불러 병합된 값을 리턴
def merge_sort(a):
if len(a) < 2: # 목록이 하나면 재귀 끝
return a
mid = len(a) // 2 # 목록크기의 반값을 찾고
left, right = a[:mid], a[mid:] # 목록을 left, right 두개로 분리
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
# 함수 테스트
a = [6, 2, 3, 4, 1]
print(merge_sort(a))
#include <stdio.h>
#define max_len 100 // 숫자배열 최대크기를 100으로 선언
// 나누어진 배열을 정렬해서 병합하는 함수
void merge(int a[], int start, int mid, int end) {
int b[max_len];
int i = start; //좌측 시작
int j = mid + 1; //우측 시작
int k = 0; // 배열 b 인덱스
while (i <= mid && j <= end) { //좌우 비교하는 배열 인덱스값이 둘 중 하나가 끝날때 까지 루프
if (a[i] <= a[j]) b[k++] = a[i++]; //좌측배열에 있는 값이 작으면 그 값을 가져옴
else b[k++] = a[j++]; // 우측배열에 있는 값이 작으면 그값을 가져옴.
}
// 남은 배열이 있으면 차례로 채움(병합)
while (i <= mid) b[k++] = a[i++]; // 촤측 배열
while (j <= end) b[k++] = a[j++];
while (--k >= 0) { //배열 b의 내용을 원배열 a에 대입
a[start + k] = b[k];
}
}
void merge_sort(int a[], int start, int end) {
int mid;
if (start < end) {
mid = (start + end) / 2; // 중간 인덱스값을 찾고
merge_sort(a, start, mid); //좌측 배열 분리
merge_sort(a, mid + 1, end); //우측 배열 분리
merge(a, start, mid, end); // 분리된 배열 정렬+병합 처리
}
}
// 변합정렬 함수 테스트
int main() {
int i, a[] = {6, 2, 3, 4, 1}, len = sizeof(a) / sizeof(a[0]);
merge_sort(a, 0, len - 1);
for (i = 0; i< len; i++) printf("%d ", a[i]); // 결과: 1 2 3 4 6
return 0;
}