در این مطلب از وب سایت اوپن مایند می خواهیم کمی بیشتر از Quick-sort صحبت کنیم. اگر از Quick-sort چیزی نمی دانید ابتدا این مطلب را بخوانید.

در الگوریتم Quick-sort، بدترین حالت (با درجه زمانی (O(n^2) برای ما دردسر ساز و بهترین حالت (با درجه زمانی ((O(nlg(n)، بهترین زمان اجرا را دارد! در شکل زیر بدترین حالت نشان داده شده است و آن به این صورت است که عنصر شاخص راست ترین عنصر انتخاب می شود و آرایه از قبل به صورت صعودی مرتب شده است. به صورت کلی اگر عنصر شاخص چپ ترین یا راست ترین عنصر انتخاب شود و آرایه از قبل مرتب (چه صعودی چه نزولی) باشد، الگوریتم Quick-sort بدترین زمان اجرای خود را تقدیم شما خواهد کرد! البته منظور من Quick-sort به روش پیاده سازی استاندارد و متداول است.

برای جلوگیری از ایجاد بدترین حالت، یک بهینه سازی با عنوان میانه سه پیشنهاد می شود. به این صورت که برای انتخاب عنصر شاخص دقت بیشتری به خرح می دهیم و در هر فراخوانی میانه عناصر اول، وسط و آخر بخش مورد نظر از آرایه را به عنوان عنصر شاخص انتخاب می کنیم.

این کار در میل کردن به بهترین حالت هم مفید است چرا که امکان دارد اندیس نهایی میانه ای که به عنوان شاخص انتخاب می شود، کمی (یا خیلی!) نزدیک به وسط آرایه باشد و همین موجب می شود در فراخوانی بعدی Quick-sort آرایه تقریباً به دو نیم تقسیم شود که این یعنی نزدیک شدن به بهترین حالت الگوریتم.

به سراغ کد برویم؛ با فرض این که  الگوریتم متداول Quicksort به چشمتان آشناست، بیشتر توضیحات داخل کد به صورت نام گذاری های واضح و کامنت گذاری ارائه شده است.

تابع 

(...)GetMedian

 برای انتخاب عنصر میانه است.

int GetMedian(int * Array, int startIndex, int middle, int endIndex)
{
	if (Array[startIndex] <= Array[middle])
	{
		if (Array[middle] <= Array[endIndex])
			return middle;
		else if (Array[startIndex] <= Array[endIndex])
			return endIndex;
		else
			return startIndex;
	}
	else
	{
		if (Array[startIndex] <= Array[endIndex])
			return startIndex;
		else if (Array[middle] <= Array[endIndex])
			return endIndex;
		else
			return middle;
	}
}

پیاده سازی تابع

(...)Partition

 :

int Partition(int * Array, int startIndex, int endIndex)
{
	int temp;				// Temporary variable to use in exchanges
	int lowerRangeIndex = startIndex - 1;	// The lowerRangeIndex variable hold the last index of lower-than-pivot range from startIndex to it

	// The pivotIndex will assign to the index of median of three element of part that sholud be sorted (the first, middle and last element)	
	int pivotIndex = GetMedian(Array, startIndex, startIndex + ((endIndex - startIndex) / 2), endIndex);
	int pivotValue = Array[pivotIndex];

	// Exchanging the pivot and last element of Array (in range [startIndex ... endIndex]) for simplicity
	temp = Array[pivotIndex];
	Array[pivotIndex] = Array[endIndex];
	Array[endIndex] = temp;

	for (int tempIndex = startIndex; tempIndex < endIndex; tempIndex++)
	{
		if (Array[tempIndex] <= pivotValue)
		{
			// The next place of lowerRangeIndex is the correct place to hold the next lower-than-pivot element
			lowerRangeIndex = lowerRangeIndex + 1;

			//Exchanging Array[lowerRangeIndex] and an element that is lower than pivot
			temp = Array[lowerRangeIndex];
			Array[lowerRangeIndex] = Array[tempIndex];
			Array[tempIndex] = temp;
		}
	}

	// Putting the pivot to correct place
	if (lowerRangeIndex != endIndex)
	{
		// The next place of lowerRangeIndex is the correct place to hold the pivot
		lowerRangeIndex = lowerRangeIndex + 1;

		// Exchanging the pivot and current value in pivot's correct place
		temp = Array[lowerRangeIndex];
		Array[lowerRangeIndex] = Array[endIndex];
		Array[endIndex] = temp;
	}

	return lowerRangeIndex;
}

و اما تابع 

(...)QuickSort_MedianOfThree

 :

void QuickSort_MedianOfThree(int * Array, int startIndex, int endIndex)
{
	if (startIndex < endIndex)
	{
		// After running partition() an element called pivot get the correct place in array,
		// then we will partition the Array in two parts corresponding the pivot index
		int pivotIndex = Partition(Array, startIndex, endIndex);

		// Partitioning the Array to two parts, first before the pivot, second after the pivot
		QuickSort_MedianOfThree(Array, startIndex, pivotIndex - 1);
		QuickSort_MedianOfThree(Array, pivotIndex + 1, endIndex);
	}
}

اگر در مشاهده کدها در این صفحه مشکلی داشتید، روی github (در اینجا) در اختیارتان هستند!

[مطلب پویا]:

دلیل وجود این برچسب در عنوان مطلب این است که من توضیحی مختصر در رایطه با Quicksort with median-of-three را در اینجا و اینجا خواندم و بدون دیدن کدهای پیاده سازی شده، اولین پیاده سازی که به ذهن خودم رسید را انجام دیدم؛ اما با دیدن پیاده سازی های دیگر، گمان می کنم این بهترین پیاده سازی نیست! حالا می خواهم کسانی را که به تحقیق در الگوریتم ها مشتاق هستند، درگیر این مطلب آموزشی کنم تا به صورت پویا به بهترین پیاده سازی برسیم. برای شروع لینک های زیر را در اختیارتان می گذارم و سپس منتظر نظر های شما هستم!
هر زمان به نتیجه ای رسیدیم، با اضافه شدن نام های دوستانی که مشارکت کرده اند و برداشتن برچسب [مطلب پویا] مطلب را تکمیل می کنیم.
بخوانید:

StackOverFlow: median 3 quicksort implementation

Algorithms in C#: quick sort (part three)

Quick Sort Implementation with median-of-three partitioning and cutoff for small arrays

Algorithm of the Week: Quicksort – Three-way vs. Dual-pivot

Quicksort optimizations