マージソート
本日のアルゴリズムは【マージソート】です。
マージソートは分割統治法を用いたソートアルゴリズムです。
分割統治法とは、そのままでは解決できない問題を小さな問題に分割していき、問題を解決していく方法。
クイックソートよりも遅いとも言われるマージソートですが、クイックソートよりもスタックの消費が少ないのでマージソートを使うケースも多いです。
#include
/* 定数の定義 */
#define MERGE_DATA 10
/* 関数のプロトタイプ宣言 */
void MergeSort( int *array, int left, int right );
void main()
{
int i;
int array[MERGE_DATA] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
/* マージソートを行う */
MergeSort( array, 0, MERGE_DATA - 1 );
for( i = 0; i < MERGE_DATA; i++ ) {
printf( "%d\n", array[i] );
}
}
void MergeSort( int *array, int left, int right ) {
int center;
int i;
int j;
int k;
int temp[ERGE_DATA];
if( left >= right ) {
return;
}
center = ( left + right ) / 2;
MergeSort( array, left, center );
MergeSort( array, center + 1, right );
for( i = left; i <= center; i++ ) {
temp[i] = array[i];
}
for( i = center + 1, j = right; i <= right; i++, j-- ) {
temp[i] = array[i];
}
i = left;
j = right;
for( k = left; k <= right; k++ ) {
if( temp[i] <= temp[j] ) {
array[k] = temp[i++];
}else{
array[k] = temp[j--];
}
}
}
