Algorithms/quick sort

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

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

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

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

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

تعرض الشيفرة العامة التالية كيفية تنفيذ هذه الطريقة:

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

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

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

partition (arr[], low, high)
{
    // pivot (Element to be placed at right position)
    pivot = arr[high];  
 
    i = (low - 1)  // Index of smaller element

    for (j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap arr[i] and arr[j]
        }
    }
    swap arr[i + 1] and arr[high])
    return (i + 1)
}

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

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

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

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

• 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[]‎ إلى أجزاء ثلاثة هي:

1. a[l..i]‎: ويتضمن جميع العناصر التي تكون أصغر من المحور.
2. a[i+1..j-1]‎: ويتضمن جميع مواقع ظهور المحور في المصفوفة.
3. 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.