در دو پست قبل مفهوم مرتب سازی و مرتب سازی حبابی (Bubble sort)   را بررسی کردیم  .امروز می خواهیم به  مرتب سازی سریع  (Quick sort ) بپدازیم .قبل از این که به ادامه بحث بپردازیم یک مرور بکنیم از سایر الگوریتم ها که در روز های آینده آن ها را بررسی خواهیم کرد:

– مفهوم مرتب سازی

–bubble sort

-insertion sort

-merge sort

-quick sort

-Distribution sorts

– Concurrent sorts

– Heap sort

-Radix sort

– Counting sort

مرتب سازی سریع یکی از بهترین الگوریتم های مرتب سازی  است است که سرعت بسیار مناسبی دارد و اگر درست پیاده سازی شود یکی از سریع ترین الگوریتم ها خواهد بود . Quick sort  یک روش سورت بازگشتی است ، البته ممکن است این سوال برای شما پیش بیاید اگر بازگشتی است پس چرا می گوییم از لحاظ حافظه و سرعت خوب است دلیلش این است که این الگوریتم دقیقا فیت کش است .

هسته quick sort تابع patition  است .

تابع  partition   :

//partition function
int partition( int A[], int p, int q)
{
	int temp;
	int x = A[p];
	int i = p;
	for (int j = p+1; j <= q; j++)
	{
		if (A[j] <= x)
		{
			i++;
			temp = A[j];
			A[j] = A[i];
			A[i] = temp;
		}
	}
	temp = A[i];
	A[i] = A[p];
	A[p] = temp;
	return i;
}
//

این تابع عنصر اول بازه ای را که قرار است رویش عمل کند را در نظر می گیرد  و بعد این تابع عنصر ها رو به ۲ دسته تقسیم می کند آن هایی که بزرگ تر از عنصر اول هستند و آن هایی که کوچک تر از عنصر اول هستند و عنصر اول را بین این دو دسته قرار می دهد و بعد مکانی را که عنصر ما بین این دو دسته قرار دارد را بر می گرداند . اول کد بالا را خوب نگاه کنید و بعد عکس های زیر را ببینید تا تابع partition  را بهتر درک کنید :

حالا می رویم سراغ خود تابع مرتب سازی سریع   Quick sort  :

//quick sort
void Quick_sort( int A[], int p,int r)
{
	int q;
	if( p<r)
	{
		q = partition(A,p,r);
		Quick_sort( A, p, q-1);
		Quick_sort( A, q+1, r);
	}
}
//

همین طور که می بینید quick sort  یک الگوریتم بازگشتی است که مرتب  partition  و خود را را فرا می خواند این کار را می کند تا زمانی که  آرایه هایی به طول یک به دست آید  و آرایه به طول یک خود مرتب است و اینگونه است که با استفاده از روش تقسیم و حل می توانیم آرایه را سورت کنیم.

در کد زیر تابع پارتیشن (تقسیم) و مرتب سازی سریع به همراه یک تست در Main  آمده است :

// quick sort.cpp : open-mind.ir
// farhad dalirani
//

#include "stdafx.h"
#include <iostream>

using namespace std;
//partition function
int partition( int A[], int p, int q)
{
	int temp;
	int x = A[p];
	int i = p;
	for (int j = p+1; j <= q; j++)
	{
		if (A[j] <= x)
		{
			i++;
			temp = A[j];
			A[j] = A[i];
			A[i] = temp;
		}
	}
	temp = A[i];
	A[i] = A[p];
	A[p] = temp;
	return i;
}
//

//quick sort
void Quick_sort( int A[], int p,int r)
{
	int q;
	if( p<r)
	{
		q = partition(A,p,r);
		Quick_sort( A, p, q-1);
		Quick_sort( A, q+1, r);
	}
}
//

int main()
{
	//one example
	int i;
	int A[9] = {9,5,7,3,2,1,4,6,0};

	//print array before sort
	for (int i = 0; i < 9; i++)
	{
		cout << A[i]<<" ";
	}
	cout << endl;
	//

	Quick_sort(A,0,8);

	//print array after sort
	for (int i = 0; i < 9; i++)
	{
		cout << A[i]<<" ";
	}
	cout << endl;
	//

	return 0;
}