Algorithm(3):クイックソート

高速順序付け(Quicksort)は発泡順序付けの改良である.C.A.R.Hoareが1962年に提出した.その基本思想は:1回のソートを通じてソートするデータを独立した2つの部分に分割し、その中の一部のすべてのデータは他の部分のすべてのデータよりも小さく、それからこの方法でこの2つの部分のデータをそれぞれ迅速にソートし、ソートの経過全体を再帰的に行うことができ、これによってデータ全体が秩序あるシーケンスになることを達成することである.
c++コード実装

int partition(int* array, int left, int right)
{
	int index = left;
	int pivot = array[index];
	swap(array[index], array[right]);

	for (int i=left; i<right; ++i)
	{
		// ascending sort
		if (array[i] < pivot)
		{
			swap(array[index++], array[i]);
		}
	}

	swap(array[right], array[index]);
	// index is pivot's position in array
	return index;
}

void qsort(int* array, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int index = partition(array, left, right);
	qsort(array, left, index - 1);
	qsort(array, index + 1, right);
}

int main(int argc, char* argv[])
{
	int arr[] = { 23, 24, 1, 3, 32 };

	qsort(arr, 0, 4);

	for (int i=0; i<5; ++i)
		cout << arr[i] << "	";
	cout << endl;

	system("pause");

	return 0;
}

改善されたpartition関数は,分治論理ごとに交換動作を1回減少させる

int partition(int* array, int left, int right)
{
	int index = left + 1;
	int pivot = array[left];

	for (int i=left + 1; i<=right; ++i)
	{
		// ascending sort
		if (array[i] < pivot)
		{
			swap(array[index++], array[i]);
		}
	}

	swap(array[left], array[index - 1]);
	// index is pivot's position in array
	return index - 1;
}