الفرق بين المراجعتين لصفحة: «Algorithms/quick sort»

مراجعة 10:10، 22 نوفمبر 2019

تتبع خوارزمية الترتيب السريع أسلوب (فرق تسد Divide and Conquer) إذ تنتقي عنصرًا من عناصر المصفوفة وتجعله محورًا pivot ثمّ تقسّم المصفوفة المعطاة حول ذلك العنصر. وهناك أشكال متعددة لخوارزمية البحث السريع وتنتقي كلّ منها العنصر المحوري بطريقة مختلفة:

اختيار العنصر الأول في المصفوفة كمحور دائمًا.
اختيار العنصر الأخير في المصفوفة كمحور دائمًا.
اختيار عنصر عشوائي كمحور.
اختيار الوسيط median كمحور.

عملية التقسيم partition()‎ هي جوهر خوارزمية الترتيب السريع. لو كان لدينا مصفوفة وعنصر x في هذه المصفوفة كمحور، فإنّ عملية التقسيم تضع العنصر x في مكانه الصحيح في المصفوفة المرتبة ثم تضع جميع العناصر التي تكون أصغر من العنصر x قبله، وتضع جميع العناصر التي تكون أكبر من العنصر x بعده، ويجب أن يتمّ ذلك كله في تعقيد زمني خطّي.

خوارزمية التقسيم

هناك طريقتان شائعتان لتقسيم المصفوفة المراد ترتيبها باستخدام خوارزمية الترتيب السريع.

طريقة لوموتو Lomuto's Method
طريقة هواري Hoare's Method

طريقة لوموتو

تبدأ طريقة التقسيم هذه من العنصر الموجود في أقصى يسار المصفوفة ثم تتعقّب المواقع التي تحتوي على العناصر التي تكون مساوية لقيمة العنصر المختار أو أصغر منه، وعند العثور على عنصر أصغر من العنصر المختار يجري التبديل بين موقعي العنصرين ويجري اختيار العنصر arr[i]‎، وأما إن كا ن العنصر الحالي أصغر فنبقي على العنصر المختار.

C++‎:

#include<bits/stdc++.h> 
using namespace std; 

/* تأخذ هذه الدالة العنصر الأخير كعنصر محوري ثم تضعه في موقعه الصحيح
في المصفوفة المرتبة، ثم تضع جميع العناصر التي تكون أصغر من العنصر المحوري
إلى يساره، وتضع جميع العناصر التي تكون أكبر من العنصر المحوري إلى يمينه */
int partition(int arr[], int low, int high) 
{ 
	int pivot = arr[high]; // العنصر المحوري 
	int i = (low - 1); // موقع العنصر الأصغر 

	for (int j = low; j <= high- 1; j++) 
	{ 
		// إن كان العنصر الحالي أصغر من العنصر المحوري أو مساويًا له 
		if (arr[j] <= pivot) 
		{ 
			i++; // زيادة موقع العنصر الأصغر بمقدار 
			swap(arr[i], arr[j]); 
		} 
	} 
	swap(arr[i + 1], arr[high]); 
	return (i + 1); 
} 

/* هذه هي الدالة الرئيسية التي تنفّذ عملية الترتيب السريع
arr[] --> المصفوفة المراد ترتيبها
low --> موقع البداية
hight --> موقع النهاية  */
void quickSort(int arr[], int low, int high) 
{ 
	if (low < high) 
	{ 
		/* pi --> موقع التقسيم
		يتخذ العنصر arr[p]‎ موقعه الصحيح الآن */
		int pi = partition(arr, low, high); 

		// ترتيب العناصر كلّاً على حدة
		// قبل التقسيم وبعده 
		quickSort(arr, low, pi - 1); 
		quickSort(arr, pi + 1, high); 
	} 
} 

/* تطبع الدالة عناصر المصفوفة المعطاة */
void printArray(int arr[], int size) 
{ 
	int i; 
	for (i=0; i < size; i++) 
		printf("%d ", arr[i]); 
	printf("\n"); 
} 

// اختبار الدوال السابقة 
int main() 
{ 
	int arr[] = {10, 7, 8, 9, 1, 5}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	quickSort(arr, 0, n-1); 
	printf("Sorted array: \n"); 
	printArray(arr, n); 
	return 0; 
}

بايثون:

''' 
تنفّذ هذه الدالة عملية الترتيب السريع
arr: - المصفوفة المراد ترتيبها
start: - موق البداية
stop: موقع النهاية
'''
def quicksort(arr, start , stop): 
	if(start < stop): 
		
		# موقع العنصر المحوري ضمن المصفوفة
		pivotindex = partition(arr, start, stop) 
		
		# ليست المصفوفة مرتبة بالكامل حول العنصر المحوري في هذه المرحلة
		# ترتيب النصفين الأيمن والأيسر من المصفوفة كلًّا على حدة
		quicksort(arr , start , pivotindex - 1) 
		quicksort(arr, pivotindex + 1, stop) 
		
''' 
تأخذ هذه الدالة العنصر الأول كعنصر محوري
وتضعه في موقعه المصحيح ضمن المصفوفة المرتبة
يعاد ترتيب جميع العناصر نسبة إلى العنصر المحوري
توضع العناصر التي تكون أصغر من العنصر المحوري إلى يساره
والعناصر التي تكون أكبر من العنصر المحوري إلى يمينه
'''
def partition(arr,start,stop): 
	pivot = arr[start] # pivot 
	i = start - 1 # a variable to memorize where the 
				# partition in the array starts from. 
	for j in range(start, stop - 1): 
		
		# يزاح العنصر الحالي إلى الجهة اليسرى من المصفوفة المجزئة
		# إذا كان أصغر من العنصر المحوري أو مساويًا له
		if arr[j] <= pivot: 
			arr[i] , arr[j] = arr[j] , arr[i] 
			i = i + 1
	arr[stop] , arr[i + 1] = arr[i + 1] , arr[stop] 
	return (i + 1) 

# اختبار الدالتين السابقتين
if __name__ == "__main__": 
	array = [10, 7, 8, 9, 1, 5] 
	quicksort(array, 0, len(array) - 1) 
	print(array)

جافا:

import java.io.*; 

class GFG 
{ 

// يبدل التابع بين موقعي العنصرين المعطيين في المصفوفة
static void Swap(int[] array, 
				int position1, 
				int position2) 
{ 

	// نسخ موقع العنصر الأول
	int temp = array[position1]; 
	
	// يأخذ العنصر الأول موقع العنصر الثاني
	array[position1] = array[position2]; 
	
	// يأخذ العنصر الثاني موقع العنصر الأول
	// Assign to the first element 
	array[position2] = temp; 
} 

/* تأخذ هذه الدالة العنصر الأخير كعنصر محوري ثم تضعه في موقعه الصحيح
في المصفوفة المرتبة، ثم تضع جميع العناصر التي تكون أصغر من العنصر المحوري
إلى يساره، وتضع جميع العناصر التي تكون أكبر من العنصر المحوري إلى يمينه */
static int partition(int []arr, int low, 
								int high) 
{ 
	int pivot = arr[high]; // العنصر المحوري
	
	// // موقع العنصر الأصغر 
	int i = (low - 1); 

	for (int j = low; j <= high- 1; j++) 
	{ 
		// إن كان العنصر الحالي أصغر من العنصر المحوري أو مساويًا له
		if (arr[j] <= pivot) 
		{ 
			i++; // زيادة موقع العنصر الأصغر بمقدار واحد 
			Swap(arr, i, j); 
		} 
	} 
	Swap(arr, i + 1, high); 
	return (i + 1); 
} 

/* هذه هي الدالة الرئيسية التي تنفّذ عملية الترتيب السريع
arr[] --> المصفوفة المراد ترتيبها
low --> موقع البداية
hight --> موقع النهاية */
static void quickSort(int []arr, int low, 
								int high) 
{ 
	if (low < high) 
	{ 
		/* pi --> موقع التقسيم
		يتخذ العنصر arr[p]‎ موقعه الصحيح الآن */
		int pi = partition(arr, low, high); 

		// ترتيب العناصر كلّاً على حدة
		// قبل التقسيم وبعده
		quickSort(arr, low, pi - 1); 
		quickSort(arr, pi + 1, high); 
	} 
} 

/* تطبع الدالة عناصر المصفوفة المعطاة */
static void printArray(int []arr, int size) 
{ 
	int i; 
	for (i = 0; i < size; i++) 
	System.out.print(" " + arr[i]); 
	System.out.println(); 
} 

// اختبار الدوال السابقة 
static public void main (String[] args) 
{ 
	int []arr = {10, 7, 8, 9, 1, 5}; 
	int n = arr.length; 
	quickSort(arr, 0, n-1); 
	System.out.println("Sorted array: "); 
	printArray(arr, n); 
} 
}

طريقة هواري

تعمل طريقة هواري في تقسيم المصفوفة على تهيئة موقعين في طرفي المصفوفة، ثم يتحرك الموقعان باتجاه بعضهما البعض إلى أن يحصل انقلاب (أي تصبح القيمة الصغرى في الجانب الأيسر والكبرى في الجانب الأيمن). عند حصول الانقلاب تبدّل الخوارزمية بين موقعي القيمتين وتعاد العملية مرة أخرى.

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

C++‎:

#include<bits/stdc++.h> 
using namespace std; 

/* تأخذ هذه الدالة العنصر الأخير كعنصر محوري ثم تضعه في موقعه الصحيح
في المصفوفة المرتبة، ثم تضع جميع العناصر التي تكون أصغر من العنصر المحوري
إلى يساره، وتضع جميع العناصر التي تكون أكبر من العنصر المحوري إلى يمينه */
int partition(int arr[], int low, int high) 
{ 
	int pivot = arr[low]; 
	int i = low - 1, j = high + 1; 

	while (true) 
	{ 
		// العثور على العنصر الموجود في أقصى اليسار
		// والذي يكون أكبر من العنصر المحوري أو مساويًا له
		do
		{ 
			i++; 
		} while (arr[i] < pivot); 

		// العثور على العنصر الموجود في أقصى اليمين
		// والذي يكون أصغر من العنصر المحوري أو مساويًا له
		do
		{ 
			j--; 
		} while (arr[j] > pivot); 

		// إن تقابل المؤشران 
		if (i >= j) 
			return j; 

		swap(arr[i], arr[j]); 
	} 
} 

/*  هذه هي الدالة الرئيسية التي تنفّذ عملية الترتيب السريع
arr[] --> المصفوفة المراد ترتيبها
low --> موقع البداية
hight --> موقع النهاية */
void quickSort(int arr[], int low, int high) 
 
	if (low < high) 
	{ 
		/* pi --> موقع التقسيم
		يتخذ العنصر arr[p]‎ موقعه الصحيح الآن */
		int pi = partition_r(arr, low, high); 

		// ترتيب العناصر كلّاً على حدة
		// قبل التقسيم وبعده
		quickSort(arr, low, pi); 
		quickSort(arr, pi + 1, high); 
	} 
} 

/* تطبع الدالة عناصر المصفوفة المعطاة */
void printArray(int arr[], int n) 
{ 
	for (int i=0; i < n; i++) 
		printf("%d ", arr[i]); 
	printf("\n"); 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int arr[] = {10, 7, 8, 9, 1, 5}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	quickSort(arr, 0, n-1); 
	printf("Sorted array: \n"); 
	printArray(arr, n); 
	return 0; 
}

بايثون:

'''
تنفّذ هذه الدالة عملية الترتيب السريع باستخدام طريقة هاوري للتقسيم
arr: - المصفوفة المراد ترتيبها
start: - موق البداية
stop: موقع النهاية
'''
def quicksort(arr, start, stop): 
	if(start < stop): 
		
		# موقع العنصر المحوري في المصفوفة
		pivotindex = partition(arr, start, stop) 
		
		# ليست المصفوفة مرتبة بالكامل حول العنصر المحوري في هذه المرحلة
		# ترتيب النصفين الأيمن والأيسر من المصفوفة كلًّا على حدة
		quicksort(arr , start , pivotindex) 
		quicksort(arr, pivotindex + 1, stop) 

''' 
تأخذ هذه الدالة العنصر الأول كعنصر محوري
وتضعه في موقعه المصحيح ضمن المصفوفة المرتبة
يعاد ترتيب جميع العناصر نسبة إلى العنصر المحوري
توضع العناصر التي تكون أصغر من العنصر المحوري إلى يساره
والعناصر التي تكون أكبر من العنصر المحوري إلى يمينه
'''
def partition(arr,start,stop): 
	pivot = arr[start] # العنصر المحوري
	i = start - 1
	j = stop + 1
	while True: 
		while True: 
			i = i + 1
			if arr[i] >= pivot: 
				break
		while True: 
			j = j - 1
			if arr[j] <= pivot: 
				break
		if i >= j: 
			return j 
		arr[i] , arr[j] = arr[j] , arr[i] 

# اختبار الدوال السابقة
if __name__ == "__main__": 
	array = [10, 7, 8, 9, 1, 5] 
	quicksort(array, 0, len(array) - 1) 
	print(array)

جافا:

// Java implementation of QuickSort 
// using Hoare's partition scheme 
import java.io.*; 

class GFG 
{ 
	
/* تأخذ هذه الدالة العنصر الأخير كعنصر محوري ثم تضعه في موقعه الصحيح
في المصفوفة المرتبة، ثم تضع جميع العناصر التي تكون أصغر من العنصر المحوري
إلى يساره، وتضع جميع العناصر التي تكون أكبر من العنصر المحوري إلى يمينه */
static int partition(int []arr, int low, 
								int high) 
{ 
	int pivot = arr[low]; 
	int i = low - 1, j = high + 1; 

	while (true) 
	{ 
		// العثور على العنصر الموجود في أقصى اليسار 
		// والذي يكون أكبر من العنصر المحوري أو مساويًا له 
		do
		{ 
			i++; 
		} while (arr[i] < pivot); 

		// العثور على العنصر الموجود في أقصى اليمين 
		// والذي يكون أصغر من العنصر المحوري أو مساويًا له 
		do
		{ 
			j--; 
		} while (arr[j] > pivot); 

		// إن تقابل المؤشران. 
		if (i >= j) 
			return j; 
		int temp = arr[i]; 
		arr[i] = arr[j]; 
		arr[j] = temp; 
		// التبديل بين موقعي العنصرين
	} 
} 

/*  هذه هي الدالة الرئيسية التي تنفّذ عملية الترتيب السريع
arr[] --> المصفوفة المراد ترتيبها
low --> موقع البداية
hight --> موقع النهاية */
static void quickSort(int []arr, int low, 
								int high) 
{ 
	if (low < high) 
	{ 
		/* pi --> موقع التقسيم
		يتخذ العنصر arr[p]‎ موقعه الصحيح الآن */
		int pi = partition(arr, low, high); 

		// ترتيب العناصر كلّاً على حدة
		// قبل التقسيم وبعده 
		quickSort(arr, low, pi); 
		quickSort(arr, pi + 1, high); 
	} 
} 

/* تطبع الدالة عناصر المصفوفة المعطاة */
static void printArray(int []arr, int n) 
{ 
	for (int i=0; i < n; i++) 
	System.out.print(" " + arr[i]); 
	System.out.println(); 
} 

// اختبار التوابع السابقة 
static public void main (String[] args) 
{ 
	int []arr = {10, 7, 8, 9, 1, 5}; 
	int n = arr.length; 
	quickSort(arr, 0, n - 1); 
	System.out.println("Sorted array: "); 
	printArray(arr, n); 
} 
}

ملاحظة:

إن تعديل طريقة هاوري لاختيار العنصر الأخير كعنصر محوري قد يؤدي إلى الدخول في حلقة تعاودية غير منتهية، فعلى سبيل المثال إن كان العنصر المحوري في المصفوفة ‎{10, 5, 6, 20}‎ هو arr[high]‎ فإن الموقع المعاد سيكون دائمًا هو الموقع الأعلى وستستدعى دالة الترتيب السريع نفسها في كل مرة. ولمعالجة العنصر المحوري العشوائي، يجب تبديل العنصر العشوائي مع العنصر الأول دائمًا ثم اتباع خطوات الخوارزمية أعلاه.

طريقة هاوري مقابل طريقة لوموتو

تظهر طريقة هاوري كفاءة أعلى من طريقة لوموتو وذلك لأنّ الأخيرة تجري في المعدل ثلاث عمليات تبديل أكثر من طريقة هاوري، إلى جانب أن طريقة هاوري تقسم المصفوفة بكفاءة حتى إن كانت جميع القيم فيها متساوية.

تتشابه الطريقتان في أنّهما تتسببان في تحويل التعقيد الزمني لخوارزمية الترتيب السريع إلى المقدار O(n^2)‎ عندما تكون المصفوفة المدخلة مرتّبة أصلًا، إلى جانب أن الخوارزمية لن تنتج ترتيبًا مستقرًا.

ويجدر الانتباه إلى أنّ الموقع النهائي للعنصر المحوري في طريقة هاوري قد لا يكون في الموقع المعاد سابقًا بالضرورة، وأنّ القطعتين التاليتين اللتين تنفّذ عليهما الخوارزمية تعاوديًا هما (lo..p) و (p+1..hi)، أما في طريقة لوموتو فالقطعتان هما: (lo..p-1) و (p+1..hi).

تنفيذ الخوارزمية

يمكن تنفيذ خوارزمية البحث السريع بطريقتين: التعاودية والتكرارية.

الطريقة التعاودية

تعرض الأمثلة التالية طريقة تنفيذ خوارزمية الترتيب السريع تعاوديًا في عدد من لغات البرمجة:

C++‎:

#include <bits/stdc++.h> 
using namespace std; 

// دالة مساعدة للتبديل بين عنصرين
void swap(int* a, int* b) 
{ 
	int t = *a; 
	*a = *b; 
	*b = t; 
} 

/* تأخذ الدالة في المثال التالي العنصر الأخير كعنصر محوري
ثم تضعه في مكانه الصحيح ضمن المصفوفة المرتّبة
ثم تضع جميع العناصر التي تكون أصغر منه إلى يساره
والعناصر التي تكون أكبر منه إلى يمينه
*/
int partition (int arr[], int low, int high) 
{ 
	int pivot = arr[high]; // المحور 
	int i = (low - 1); // موقع عنصر أصغر

	for (int j = low; j <= high - 1; j++) 
	{ 
		// إن كان العنصر الحالي أصغر من المحور أو مساويًا له
		if (arr[j] <= pivot) 
		{ 
			i++; // نزيد موقع العنصر الأصغر بمقدار واحد 
			swap(&amp;arr[i], &amp;arr[j]); 
		} 
	} 
	swap(&amp;arr[i + 1], &amp;arr[high]); 
	return (i + 1); 
} 

/* الدالة الرئيسية التي تنفّذ عملية الترتيب السريع 
arr[] --> المصفوفة المراد ترتيبها, 
low --> موقع البداية, 
high --> موقع النهاية */
void quickSort(int arr[], int low, int high) 
{ 
	if (low < high) 
	{ 
        /* pi موقع عملية التقسيم هو
        والعنصر المحور في موقعه الصحيح الآن */
		int pi = partition(arr, low, high); 

		// ترتيب العناصر قبل المحور
        // وبعد المحور كلّا على حدة
		quickSort(arr, low, pi - 1); 
		quickSort(arr, pi + 1, high); 
	} 
} 

/* طباعة محتويات المصفوفة */
void printArray(int arr[], int size) 
{ 
	int i; 
	for (i = 0; i < size; i++) 
		cout << arr[i] << " "; 
	cout << endl; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int arr[] = {10, 7, 8, 9, 1, 5}; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	quickSort(arr, 0, n - 1); 
	cout << "Sorted array: \n"; 
	printArray(arr, n); 
	return 0; 
}

بايثون:

# تأخذ الدالة في المثال التالي العنصر الأخير كعنصر محوري
# ثم تضعه في مكانه الصحيح ضمن المصفوفة المرتّبة
# ثم تضع جميع العناصر التي تكون أصغر منه إلى يساره
# والعناصر التي تكون أكبر منه إلى يمينه

def partition(arr,low,high): 
	i = ( low-1 )		 # موقع عنصر أصغر 
	pivot = arr[high]	 # المحور

	for j in range(low , high): 

		# إن كان العنصر الحالي أصغر من المحور أو مساويًا له
		if arr[j] <= pivot: 
		
			# نزيد موقع العنصر الأصغر بمقدار واحد 
			i = i+1
			arr[i],arr[j] = arr[j],arr[i] 

	arr[i+1],arr[high] = arr[high],arr[i+1] 
	return ( i+1 ) 

# arr[] --> المصفوفة المراد ترتيبها, 
# low --> موقع البداية, 
# high --> موقع النهاية

# الدالة التي تؤدي عملية الترتيب السريع
def quickSort(arr,low,high): 
	if low < high: 

		# pi موقع عملية التقسيم هو
        # والعنصر المحور في موقعه الصحيح الآن
		pi = partition(arr,low,high) 

		# ترتيب العناصر قبل 
		# ترتيب العناصر قبل المحور
        # وبعد المحور كلّا على حدة
		quickSort(arr, low, pi-1) 
		quickSort(arr, pi+1, high) 

# اختبار الدوال السابقة
arr = [10, 7, 8, 9, 1, 5] 
n = len(arr) 
quickSort(arr,0,n-1) 
print ("Sorted array is:") 
for i in range(n): 
	print ("%d" %arr[i]),

جافا:

class QuickSort 
{ 
	/* تأخذ الدالة في المثال التالي العنصر الأخير كعنصر محوري
	ثم تضعه في مكانه الصحيح ضمن المصفوفة المرتّبة
	ثم تضع جميع العناصر التي تكون أصغر منه إلى يساره
	والعناصر التي تكون أكبر منه إلى يمينه
	*/
	int partition(int arr[], int low, int high) 
	{ 
		int pivot = arr[high]; 
		int i = (low-1); // موقع عنصر أصغر 
		for (int j=low; j<high; j++) 
		{ 
			// إن كان العنصر الحالي أصغر من المحور أو مساويًا له
			if (arr[j] <= pivot) 
			{ 
				i++; 

				// نبدل مواقع العنصرين
				int temp = arr[i]; 
				arr[i] = arr[j]; 
				arr[j] = temp; 
			} 
		} 
		
        // نبدل مواقع العنصر التالي والعنصر المحور
		int temp = arr[i+1]; 
		arr[i+1] = arr[high]; 
		arr[high] = temp; 

		return i+1; 
	} 


	/* الدالة الرئيسية التي تنفّذ عملية الترتيب السريع 
	arr[] --> المصفوفة المراد ترتيبها,
	low --> موقع البداية, 
	high --> موقع النهاية */
	void sort(int arr[], int low, int high) 
	{ 
		if (low < high) 
		{ 
			/* pi موقع عملية التقسيم هو
	        والعنصر المحور في موقعه الصحيح الآن */

			int pi = partition(arr, low, high); 

            // ترتيب العناصر قبل المحور
            // وبعد المحور كلّا على حدة

			sort(arr, low, pi-1); 
			sort(arr, pi+1, high); 
		} 
	} 

	/* دالة مساعدة لطباعة عناصر المصفوفة */
	static void printArray(int arr[]) 
	{ 
		int n = arr.length; 
		for (int i=0; i<n; ++i) 
			System.out.print(arr[i]+" "); 
		System.out.println(); 
	} 

	// اختبار الدوال السابقة
	public static void main(String args[]) 
	{ 
		int arr[] = {10, 7, 8, 9, 1, 5}; 
		int n = arr.length; 

		QuickSort ob = new QuickSort(); 
		ob.sort(arr, 0, n-1); 

		System.out.println("sorted array"); 
		printArray(arr); 
	} 
}

خوارزمية الترتيب السريع ثلاثية الطرق

تعمل خوارزمية الترتيب السريع عن طريق اختيار عنصر كمحور ثم تقسيم المصفوفة حول هذا المحور وإعادة هذه العملية مع المصفوفات الناتجة من عملية التقسيم.

ولكن لنفترض مصفوفة تحتوي على العديد من العناصر المتكررة. لو اخترنا العنصر ٤ ليكون المحور، فإنّنا سنصحح موقع عنصر واحد فقط ونعالج بقية الأرقام تعاوديًا.

تقسم المصفوفة arr[l..r]‎ في خوارزمية الترتيب السريع ثلاثية الطرق ‎3-way QuickSot‎ إلى ثلاثة أجزاء:

١. العناصر arr[l..i]‎ التي تكون أقل من العنصر المحور.

٢. العناصر arr[i+1..j-1]‎ التي تكون مساوية للعنصر المحور.

٣. العناصر arr[j..r]‎ التي تكون أكبر من العنصر المحور.

تعرض الشيفرة التالية كيفية تنفيذ هذه الطريقة في لغة C++‎.

تقسم الدالة partition()‎ المصفوفة المعطاة a[]‎ إلى أجزاء ثلاثة هي:

a[l..i]‎: ويتضمن جميع العناصر التي تكون أصغر من المحور.
a[i+1..j-1]‎: ويتضمن جميع مواقع ظهور المحور في المصفوفة.
a[j..r]‎: ويتضمّن جميع العناصر التي تكون أكبر من المحور.

وتتضمن الشيفرة كذلك حلقة while رئيسية تضمّ بداخلها حلقتي while. مهمة الحلقة الأولى هي العثور على أول عنصر يكون أكبر من v أو مساويًا له من جهة اليسار. وهذه الحلقة سوف تتوقف عن العمل لأنّ v هو العنصر الأخير.

أما الحلقة الثانية فتبدأ من جهة اليمين بحثًا عن أول عنصر يكون أصغر من v أو مساويًا له.

#include <bits/stdc++.h> 
using namespace std; 


void partition(int a[], int l, int r, int &amp;i, int &amp;j) 
{ 
	i = l-1, j = r; 
	int p = l-1, q = r; 
	int v = a[r]; 

	while (true) 
	{ 
		while (a[++i] < v); 

		while (v < a[--j]) 
			if (j == l) 
				break; 

		// إن تقاطع الموقعان
        // i و j
        // ينتهي عمل الخوارزمية
		if (i >= j) break; 

		// نبدل مواقع العناصر بحيث يذهب العنصر الأصغر إلى اليسار والأكبر إلى اليمين
		swap(a[i], a[j]); 

		// نقل جميع حالات الظهور للعنصر المحوري في الجهة اليسرى إلى بداية المصفوفة
        // p والاستمرار بالعد باستخدام
		if (a[i] == v) 
		{ 
			p++; 
			swap(a[p], a[i]); 
		} 

		// نقل جميع حالات الظهور للعنصر المحوري في الجهة اليمنى إلى نهاية المصفوفة
        // p والاستمرار بالعد باستخدام

		if (a[j] == v) 
		{ 
			q--; 
			swap(a[j], a[q]); 
		} 
	} 

	// تحريك العنصر المحوري إلى موقعه الصحيح في المصفوفة 
	swap(a[i], a[r]); 

	// تحريك جميع حالات الظهور المشابهة في الجزء الأيسر
    // arr[i] إلى الموقع المجاور لـ
    j = i-1; 
	for (int k = l; k < p; k++, j--) 
		swap(a[k], a[j]); 

	// تحريك جميع حالات الظهور المشابهة في الجزء الأيمن
    // arr[i] إلى الموقع المجاور لـ
	i = i+1; 
	for (int k = r-1; k > q; k--, i++) 
		swap(a[i], a[k]); 
} 

void quicksort(int a[], int l, int r) 
{ 
	if (r <= l) return; 

	int i, j; 

	// كإشارة i و j يمرر 
	partition(a, l, r, i, j); 

	quicksort(a, l, j); 
	quicksort(a, i, r); 
} 

// دالة مساعدة لطباعة عناصر المصفوفة
void printarr(int a[], int n) 
{ 
	for (int i = 0; i < n; ++i) 
		printf("%d ", a[i]); 
	printf("\n"); 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int a[] = {4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4}; 
	int size = sizeof(a) / sizeof(int); 
	printarr(a, size); 
	quicksort(a, 0, size - 1); 
	printarr(a, size); 
	return 0; 
}

الطريقة التكرارية

يمكن إجراء عملية الترتيب السريع بطريقة تكرارية iterative وذلك بالاستعانة بمكدس مساعد، وتعرض الأمثلة التالية كيفية تنفيذ ذلك في عدد من لغات البرمجة:

#include <bits/stdc++.h> 
using namespace std; 

// دالة مساعدة للتبديل بين العناصر
void swap(int* a, int* b) 
{ 
	int t = *a; 
	*a = *b; 
	*b = t; 
} 

/* تستخدم الدالة نفسها في الطريقتين التكرارية والتعاودية */
int partition(int arr[], int l, int h) 
{ 
	int x = arr[h]; 
	int i = (l - 1); 

	for (int j = l; j <= h - 1; j++) { 
		if (arr[j] <= x) { 
			i++; 
			swap(&amp;arr[i], &amp;arr[j]); 
		} 
	} 
	swap(&amp;arr[i + 1], &amp;arr[h]); 
	return (i + 1); 
} 

/* 
arr[] --> المصفوفة المراد ترتيبها, 
low --> موقع البداية, 
high --> موقع النهاية
*/
void quickSortIterative(int arr[], int l, int h) 
{ 
	// إنشاء المكدس المساعد 
	int stack[h - l + 1]; 

	// تهيئة قمة المكدس 
	int top = -1; 

	// إدراج القيم الابتدائية لموقعي البداية والنهاية في المكدس
	stack[++top] = l; 
	stack[++top] = h; 

	// الاستمرار في إزالة العناصر من المكدس ما دامت هنالك عناصر في المكدس 
	while (top >= 0) { 
		// إزالة موقعي البداية والنهاية
		h = stack[top--]; 
		l = stack[top--]; 

		// وضع العنصر المحوري في موقعه الصحيح في المصفوفة المرتبة
		int p = partition(arr, l, h); 

		// إن كان هناك عناصر في الجانب الأيسر من العنصر المحوري
        // فسنضيف الجانب الأيسر إلى المكدس
		if (p - 1 > l) { 
			stack[++top] = l; 
			stack[++top] = p - 1; 
		} 

		// إن كان هناك عناصر في الجانب الأيمن من العنصر المحوري
        // فسنضيف الجانب الأيمن إلى المكدس
		if (p + 1 < h) { 
			stack[++top] = p + 1; 
			stack[++top] = h; 
		} 
	} 
} 

// دالة مساعدة لطباعة محتويات المصفوفة 
void printArr(int arr[], int n) 
{ 
	int i; 
	for (i = 0; i < n; ++i) 
		cout << arr[i] << " "; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int arr[] = { 4, 3, 5, 2, 1, 3, 2, 3 }; 
	int n = sizeof(arr) / sizeof(*arr); 
	quickSortIterative(arr, 0, n - 1); 
	printArr(arr, n); 
	return 0; 
}

بايثون:

# تستخدم دالة التقسيم نفسها في الطريقتين التكرارية والتعاودية
def partition(arr, l, h):
    i = (l - 1)
    x = arr[h]

    for j in range(l, h):
        if arr[j] <= x:
            # تحريك موقع العنصر الأصغر إلى الأمام خطوة واحدة
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[h] = arr[h], arr[i + 1]
    return i + 1


# arr[] --> المصفوفة المراد ترتيبها, 
# low --> موقع البداية, 
# high --> موقع النهاية
# الدالة التي تؤدي عملية الترتيب السريع


def quickSortIterative(arr, l, h):
    # إنشاء المكدس المساعد
    size = h - l + 1
    stack = [0] * size

    # تهيئة قمة المكدس
    top = -1

    # إدراج القيم الابتدائية لموقعي البداية والنهاية في المكدس
    top = top + 1
    stack[top] = l
    top = top + 1
    stack[top] = h

    # إزالة العناصر من المكدس واحدًا تلو الآخر ما دامت العناصر موجودة فيه
    while top >= 0:
        # إزالة موقعي البداية والنهاية
        h = stack[top]
        top = top - 1
        l = stack[top]
        top = top - 1

    # وضع العنصر المحوري في مكانه الصحيح ضمن المصفوفة المرتبة
        p = partition(arr, l, h)

        
        # إن كان هناك عناصر في الجانب الأيسر من العنصر المحوري
        # فسنضيف الجانب الأيسر إلى المكدس

        if p - 1 > l:
            top = top + 1
            stack[top] = l
            top = top + 1
            stack[top] = p - 1

	    # إن كان هناك عناصر في الجانب الأيمن من العنصر المحوري
        # فسنضيف الجانب الأيمن إلى المكدس

        if p + 1 < h:
            top = top + 1
            stack[top] = p + 1
            top = top + 1
            stack[top] = h


# اختبار الدوال السابقة
arr = [4, 3, 5, 2, 1, 3, 2, 3]
n = len(arr)
quickSortIterative(arr, 0, n - 1)
print("Sorted array is:")
for i in range(n):
    print("% d" % arr[i]),

جافا:

public class Main {
    
    /* تأخذ الدالة في المثال التالي العنصر الأخير كعنصر محوري
	ثم تضعه في مكانه الصحيح ضمن المصفوفة المرتّبة
	ثم تضع جميع العناصر التي تكون أصغر منه إلى يساره
	والعناصر التي تكون أكبر منه إلى يمينه
	*/
    
    static int partition(int[] arr, int low,
                         int high)
    {
        int temp;
        int pivot = arr[high];

        // موقع العنصر الأصغر
        int i = (low - 1);
        for (int j = low; j <= high - 1; j++) {
            // إن كان العنصر الحالي أصغر من العنصر المحور أو مساويًا له
            if (arr[j] <= pivot) {
                i++;

                // التبديل بين الموقعين
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // التبديل بين
        // arr[i+1] و arr[high]
        // (أو العنصر المحوري)

        temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    /* A[] --> المصفوفة المراد ترتيبها,
	l --> موقع البداية, 
	h --> موقع النهاية */
    static void quickSortIterative(int[] arr,int l, int h)
    {
        // إنشاء المكدس المساعد
        int[] stack = new int[h - l + 1];

        // تهيئة قمة المكدس
        int top = -1;

        // إدراج القيم الابتدائية لموقعي البداية والنهاية في المكدس
        stack[++top] = l;
        stack[++top] = h;

        // الاستمرار في إزالة العناصر من المكدس ما دامت هنالك عناصر في المكدس 
	while (top >= 0) { 
		// إزالة موقعي البداية والنهاية
		h = stack[top--]; 
		l = stack[top--]; 

		// وضع العنصر المحوري في موقعه الصحيح في المصفوفة المرتبة
		int p = partition(arr, l, h); 

		// إن كان هناك عناصر في الجانب الأيسر من العنصر المحوري
        // فسنضيف الجانب الأيسر إلى المكدس
		if (p - 1 > l) { 
			stack[++top] = l; 
			stack[++top] = p - 1; 
		} 

		// إن كان هناك عناصر في الجانب الأيمن من العنصر المحوري
        // فسنضيف الجانب الأيمن إلى المكدس
		if (p + 1 < h) { 
			stack[++top] = p + 1; 
			stack[++top] = h; 
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = { 4, 3, 5, 2, 1, 3, 2, 3 };
        int n = 8;

        quickSortIterative(arr, 0, n - 1);

        for (int i = 0; i < n; i++)
            System.out.println(arr[i] + " ");
    }
}

التعقيد الزمني

يعتمد الوقت الذي تستغرقه هذه الخوارزمية على عدد المدخلات وطريقة التقسيم، وهناك ثلاث حالات هي:

الحالة الأسوأ: تحدث الحالة الأسوأ عندما تختار عملية التقسيم دائمًا العنصر الأكبر أو الأصغر كعنصر محوري. ولو نظرنا إلى طريقة التقسيم سابقة الذكر حيث يُعتمد العنصر الأخير دائمًا كعنصر محوري، فإنّ الحالة الأسوأ تطرأ عندما تكون المصفوفة مرتّبة ترتيبًا تصاعديًا أو تنازليًا. يبلغ التعقيد الزمني في هذه الحالة المقدار O(n^2)‎.

الحالة الأمثل: تحدث الحالة الأمثل عندما تختار عملية التقسيم دائمًا العنصر الأوسط في المصفوفة كعنصر محوري.

الحالة الوسطية: لحساب التعقيد الزمني في الحالة الوسطية يجب النظر في جميع احتمالات اختيار العنصر المحوري، وحساب التعقيد الزمني لكل حالة. يبلغ التعقيد الزمني لهذه الحالة المقدار O(nlogn)‎.

صحيح أنّ التعقيد الزمني لخوارزمية الترتيب السريع في الحالة الأسوأ يبلغ المقدار O(n^2)‎ وهو أعلى من التعقيد الزمني لخوارزميات أخرى مثل الترتيب بالدمج والترتيب بالكومة، غير أنّ خوارزمية الترتيب السريع هي الأسرع عمليًا؛ وذلك لأن من الممكن تنفيذ الحلقة التكرارية الداخلية بطريقة فعالة في معظم المعماريات وفي معظم البيانات الحقيقية. يمكن تنفيذ خوارزمية الترتيب السريع بطرق مختلفة وذلك بتغيير العنصر المحوري، وبذلك يمكن تجنب حدوث الحالة الأسوأ بنسبة كبيرة. ولكن تعدّ خوارزمية الترتيب بالدمج الخيار الأفضل عند التعامل مع مقدار ضخم من البيانات المخزّنة في مصدر خارجي.

انظر أيضًا

خوارزمية الترتيب السريع العشوائية: تنتخب هذه الخوارزمية العنصر المحوري عشوائيًا.

مصادر

صفحة Quick Sort في توثيق الخوارزميات في موقع GeeksforGeeks.
صفحة ‎3-Way QuickSort‎ في توثيق الخوارزميات في موقع GeeksforGeeks.
صفحة Iterative Quick Sort في توثيق الخوارزميات في موقع GeeksforGeeks.

@@ سطر 10: / سطر 10: @@
 == خوارزمية التقسيم ==
+هناك طريقتان شائعتان لتقسيم المصفوفة المراد ترتيبها باستخدام خوارزمية الترتيب السريع.
+# طريقة لوموتو Lomuto's Method
+# طريقة هواري Hoare's Method
 === طريقة لوموتو ===
@@ سطر 17: / سطر 20: @@
 * C++‎:
-<source lang="c++">/* C++ implementation QuickSort using Lomuto's partition
+<source lang="c++">#include<bits/stdc++.h>
-Scheme.*/
-#include<bits/stdc++.h>
 using namespace std;
@@ سطر 217: / سطر 218: @@
 تعمل طريقة هواري في تقسيم المصفوفة على تهيئة موقعين في طرفي المصفوفة، ثم يتحرك الموقعان باتجاه بعضهما البعض إلى أن يحصل انقلاب (أي تصبح القيمة الصغرى في الجانب الأيسر والكبرى في الجانب الأيمن). عند حصول الانقلاب تبدّل الخوارزمية بين موقعي القيمتين وتعاد العملية مرة أخرى.
-=== تنفيذ الخوارزمية ===
 تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:
@@ سطر 648: / سطر 647: @@
 	}
 } </source>
-=== خوارزمية الترتيب السريع ثلاثية الطرق ===
+== خوارزمية الترتيب السريع ثلاثية الطرق ==
 تعمل خوارزمية الترتيب السريع عن طريق اختيار عنصر كمحور ثم تقسيم المصفوفة حول هذا المحور وإعادة هذه العملية مع المصفوفات الناتجة من عملية التقسيم.