앞서 호로비츠의 Merge Pass를 이용한 Merge Sort를 보았는데, 이번에는 일반적인 병합정렬 방법을 이용한 프로그램이다.
병합정렬의 규칙은 간단하다.
정렬될 배열을 반으로 나누어 각각을 다시 병합정렬하는 것이다.
이 때, 배열의 원소가 하나가 되면, 그 때 반으로 나눈 2개의 배열을 합치는데, 이 때 크기를 비교하여 정렬이 이루어진다.
아래 프로그램에서는 정렬할 배열과 정렬할 배열의 시작위치와 끝 위치를 받아 병합정렬을 수행한다.
|
#include <iostream>
using namespace std;
void mergeSort(int* list, int s, int e); void merge(int* list, int s1, int e1, int s2, int e2);
int main() { int list[] = {5, 7, 1, 3, 2, 9, 8}; mergeSort(list, 0, 6);
for (int i = 0; i < 7; i++) cout << list[i] << " "; }
void mergeSort(int* list, int s, int e) { if (s == e) return;
int m = (s + e) / 2; mergeSort(list, s, m); mergeSort(list, m + 1, e);
merge(list, s, m, m + 1, e); }
void merge(int* list, int s1, int e1, int s2, int e2) { int i1 = s1; int i2 = s2; int i = 0; const int n = e2 - s1 + 1; int* tempList = new int[7]{};
for (int j = 0; j < n; j++) tempList[j] = 0;
while (i1 <= e1 && i2 <= e2) { if (list[i1] < list[i2]) { tempList[i] = list[i1]; i1++; } else { tempList[i] = list[i2]; i2++; } i++; }
while (i1 <= e1) { tempList[i] = list[i1]; i1++; i++; }
while (i2 <= e2 && i < n) { tempList[i] = list[i2]; i2++; i++; } cout << "i = " << i << endl; cout << "n = " << n << endl;
int ic = 0;
for (int j = s1; j <= e2; j++) { cout << tempList[ic] << " "; list[j] = tempList[ic]; ic++; }
cout << endl;
delete[] tempList; } |