Algorithms/random quick sort

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

وتختلف خوارزمية الترتيب السريع عن خوارزمية الترتيب بالدمج Merge Sort في أنّها ليست بحاجة إلى دمج المصفوفتين الفرعيتين المرتبتين، وبهذا ستحتاج خوارزمية الترتيب السريع إلى مساحة أقل في الذاكرة من خوارزمية الترتيب بالدمج، وهذا هو السبب الذي يجعل خوارزمية الترتيب السريع مفضلة على خوارزمية الترتيب بالدمج. ويؤدي اختيار عنصر محوري عشوائيًا إلى تحسين التعقيد الزمني لخوارزمية الترتيب السريع.

هناك طريقتان لتقسيم المصفوفة هما طريقة هواري Hoare partition وطريقة لوموتو Lomuto partition.

طريقة هواري

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

• C++‎:

#include <cstdlib> 
#include <iostream> 
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]); 
	} 
} 

/* تنشئ الدالة عنصرًا محوريًا عشوائيًا، ثم تبدل موقعه مع العنصر الأخير
 في المصفوفة ثم تستدعي دالة التقسيم.
 في طريقة هواري لتقسيم المصفوفة يجري اختيار العنصر الأدنى كأول عنصر محوري */
int partition_r(int arr[], int low, int high) 
{ 
	// توليد رقم عشوائي بين الحدين الأعلى والأدنى المعطيين
	srand(time(NULL)); 
	int random = low + rand() % (high - low); 

	// تبديل موقعي العنصرين المحوري والأدنى
	swap(arr[random], arr[low]); 

	return partition(arr, low, high); 
} 

/* هذه هي الدالة الرئيسية التي تنفّذ عملية الترتيب السريع
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; 
}

• بايثون:

import random 

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

# تولّد هذه الدالة عنصرًا محوريًا عشوائيًا، ثم تبدّل موقعه مع موقع
# العنصر الأول ثم تستدعي دالة التقسيم
def partitionrand(arr , start, stop): 

	# توليد رقم عشوائي بين موقعي البداية والنهاية المعطيين
	randpivot = random.randrange(start, stop) 

	# تبديل موقعي العنصرين الأول والمحوري في المصفوفة
	arr[start], arr[randpivot] = arr[randpivot], arr[start] 
	return partition(arr, start, stop) 

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

طريقة لوموتو

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

• C++‎:

#include <cstdlib> 
#include <iostream> 
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); 
} 
// تولّد هذه الدالة عنصرًا محوريًا عشوائيًا، ثم تبدّل موقعه مع موقع
// العنصر الأخير ثم تستدعي دالة التقسيم
int partition_r(int arr[], int low, int high) 
{ 
	// توليد رقم عشوائي بين الحدين الأعلى والأدنى المعطيين
	srand(time(NULL)); 
	int random = low + rand() % (high - low); 

	// تبديل موقعي العنصرين المحوري والأعلى 
	swap(arr[random], arr[high]); 

	return partition(arr, low, high); 
} 

/* هذه هي الدالة الرئيسية التي تنفّذ عملية الترتيب السريع
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 - 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; 
}

• بايثون:

import random 

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

# تولّد هذه الدالة عنصرًا محوريًا عشوائيًا، ثم تبدّل موقعه مع موقع
# العنصر الأول ثم تستدعي دالة التقسيم
def partitionrand(arr , start, stop): 

		# توليد رقم عشوائي بين موقعي البداية والنهاية المعطيين
	randpivot = random.randrange(start, stop) 

		# تبديل موقعي العنصرين الأول والمحوري في المصفوفة
	arr[start], arr[randpivot] = arr[randpivot], arr[start] 
	return partition(arr, start, stop) 

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

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

انظر أيضًا

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

مصادر

• صفحة QuickSort using Random Pivoting في توثيق الخوارزميات في موقع GeeksforGeeks.