[C언어 알고리즘] 4.3 병합 정렬(Merge Sort) 알고리즘
이번에는 병합 정렬 알고리즘을 살펴봅시다.
병합 정렬 알고리즘은 배열을 작은 단위의 배열로 분할한 후에 분할한 배열을 정렬하고 이들을 다시 정렬하면서 전체 배열을 정렬하는 알고리즘입니다.
병합 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)
ah:= n/2
bh:= n - ah;
조건(n이 1보다 작거나 같으면) 종료
병합정렬(base,ah,compare)
병합접열(base+ah,bh,compare)
tbase에 동적 메모리 할당(원소크기*원소개수)
메모리 복사(tbase,base)
ai:=0
bi:=ah
i:=0
반복(ai가 ah보다 작으면서 bi가 n보다 작다)
조건(tbase[ai]가 tbase[bi]보다 작거나 같으면
base[i] := base[ai]
ai:= ai+1
아니면
base[i]:= base[bi]
bi:= bi+1
i:=i+1
반복(ai가 ah보다 작다)
base[i]:= tbase[ai]
i:=i+1
ai:=ai+1
반복(bi가 n보다 작다)
base[i]:= tbase[bi]
i:=i+1
bi:=bi+1
[C언어 알고리즘] 4.3.1 병합 정렬 알고리즘 성능 분석
[C언어 알고리즘] 4.3.2 병합 정렬 알고리즘 구현
[C언어 알고리즘] 4.3.3 병합 정렬 알고리즘 소스 코드
'언어 자료구조 알고리즘 > 디딤돌 알고리즘 (C언어)' 카테고리의 다른 글
[C언어 알고리즘] 5.1 인접 행렬로 방향성 없는그래프 (0) | 2016.12.01 |
---|---|
[C언어 알고리즘] 5.그래프(Graph) (0) | 2016.12.01 |
[C언어 알고리즘] 4.3.3 병합 정렬 알고리즘 소스 코드 (0) | 2016.12.01 |
[C언어 알고리즘] 4.3.2 병합 정렬 알고리즘 구현 (0) | 2016.12.01 |
[C언어 알고리즘] 4.3.1 병합 정렬 알고리즘 성능 분석 (0) | 2016.12.01 |
[C언어 알고리즘] 4.2.1 이진 탐색 알고리즘 소스 코드 (0) | 2016.12.01 |
[C언어 알고리즘] 4.2 이진 탐색 알고리즘 (0) | 2016.12.01 |
[C언어 알고리즘] 4.1.1 최소값(최대값) 찾기 알고리즘 소스 코드 (0) | 2016.12.01 |
[C언어 알고리즘] 4.1 최소값(최대값) 찾기 알고리즘 (0) | 2016.12.01 |
[C언어 알고리즘] 4. 분할정복 알고리즘 (0) | 2016.12.01 |