アルゴリズム

クイックソート

更新日:

クイックソートとは

ソートのアルゴリズムの一種です。
名前の通り高速なアルゴリズムと言われています。

クイックソートは列の中央にとった基準値より大きいか小さいかで並べる位置を振り分けていきます。それにより中央よりも前には基準値より小さいものが、後ろには基準値より大きいものが並びます。
その後、前半分と後ろ半分に対してそれぞれ同様の処理を要素が1になるまで繰り返します。
以上がクイックソートのアルゴリズムです。

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

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

まずは中央値の[2]を基準値とします。

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

次に基準値より添え字の小さいものの中で値が大きいものと、添え字が大きく値が小さいものを探し、入れ替えます。

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

 

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

次に基準値の前後でそれぞれ同じことをします。
前半は揃っているので交換の必要はありません。

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

これでソートは完了です。

ソースコード

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

quicksort_sample.c

#include <stdio.h>

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

void quicksort(int a[], int left, int right)
{

	int p;	//中央値
	int L = left, R = right;		//ループ中で変化するleft、right
	int temp;
	p = a[(left + right) / 2];

	while (1)
	{
		while (a[L] < p) L++; while (a[R] > p)
			R--;
		
		if (L >= R)
			break;

		temp = a[R];
		a[R] = a[L];
		a[L] = temp;

		L++;
		R--;
	}

	show(a);

	if (left < L - 1) quicksort(a, left, L - 1); if (right > R + 1)
		quicksort(a, R + 1, right); 
	
}

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

	quicksort(a, 0, a_len - 1);

	return 0;
}

このように同じ処理を繰り返す場合、再帰関数を用いるのが便利です。



-アルゴリズム

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