クイックソートとは
ソートのアルゴリズムの一つにマージソートがあります。
マージソートは数列の二分割を繰り返していき、二つずつの数列を並べ替え、最後に並べ替えた数列を整理しながら合併させていきます。
以下の配列を例に見ていきましょう。
添え字 |
[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] |
[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;
}