アルゴリズム

マージソート

更新日:

クイックソートとは

ソートのアルゴリズムの一つにマージソートがあります。
マージソートは数列の二分割を繰り返していき、二つずつの数列を並べ替え、最後に並べ替えた数列を整理しながら合併させていきます。

以下の配列を例に見ていきましょう。

添え字 [0] [1] [2] [3] [4] [5] [6] [7]
7 2 6 9 0 5 8 1

この配列をソートします。

添え字 [0] [1] [2] [3]
7 2 6 9
添え字 [0] [1] [2] [3]
0 5 8 1

まずは半分ずつに分割していきます。

添え字 [0] [1]
7 2
添え字 [0] [1]
6 9
添え字 [0] [1]
0 5
添え字 [0] [1]
8 1

このように更に分割します。

添え字 [0] [1]
2 7
添え字 [0] [1]
6 9
添え字 [0] [1]
0 5
添え字 [0] [1]
1 8

次にこれらをそれぞれ並べ替えます。

添え字 [0] [1] [2] [3]
2 6 7 9
添え字 [0] [1] [2] [3]
0 1 5 8

並べ替えた配列を合併します。

添え字 [0] [1] [2] [3] [4] [5] [6] [7]
0 1 2 5 6 7 8 9

更に合併します。
これでソートは完了です。

ソースコード

以下がソースコードです。

margesort_sample.c

#include <stdio.h>

#define A_LEN 10

int temp[A_LEN];

void show(int a[])
{
	for (int i = 0; i < 10; i++)
		printf("%d ", a[i]);
	printf("\n");
}

void margesort(int a[], int a_len, int left, int right)
{
	int i, j, mid, L, R;
	
	if (right <= left)
		return;
	
	mid = (left + right) / 2; 
	margesort(a, mid, left, mid);
	margesort(a, a_len - mid, mid + 1, right);
	
	for (i = left; i <= mid; i++)
		temp[i] = a[i];
	for (i = mid + 1, j = right; i <= right; i++, j--)
		temp[i] = a[j];

	L = left;
	R = right;

	for (i = left; i <= right; i++)
	{
		if (temp[L] <= temp[R])
		{
			a[i] = temp[L];
			L++;
		}
		else
		{
			a[i] = temp[R];
			R--;
		}
	}
}

int main(void)
{
	int a[] = { 7, 9, 6, 8, 0, 1, 5, 10, 3, 0 };

	int a_len = A_LEN;

	margesort(a, a_len, 0, a_len - 1);

	for (int i = 0; i < 10; i++)
		printf("%d ", a[i]);

	return 0;
}



-アルゴリズム

Copyright© ツナのエンジニアブログ , 2024 All Rights Reserved Powered by AFFINGER5.