شرح خوارزمية الفرز السريع (Quicksort)

تُعد خوارزمية الفرز السريع (Quicksort) واحدة من أهم خوارزميات الفرز وأكثرها دراسة في علوم الحاسوب. إنها خوارزمية فرّق تسد (divide-and-conquer) تقوم بفرز مصفوفة عن طريق اختيار عنصر محوري (pivot)، ووضع القيم الأصغر قبل العنصر المحوري، ووضع القيم الأكبر بعده، ثم فرز الأجزاء المتبقية بشكل استدعائي.

تتمتع Quicksort بشعبية كبيرة لسرعتها في الممارسة العملية عادةً. على الرغم من أن أسوأ حالات التعقيد الزمني لها هي O(n²)، إلا أن أداءها في الحالة المتوسطة هو O(n log n)، مما يجعلها أكثر كفاءة بكثير من الخوارزميات البسيطة مثل Bubble Sort و Selection Sort و Insertion Sort لمجموعات البيانات الكبيرة.

مقدمة

تساعد خوارزميات الفرز المطورين على تنظيم البيانات بترتيب ذي معنى. تستخدم التطبيقات الفرز لترتيب الأسعار، والأسماء، والنتائج، والطوابع الزمنية، ونتائج البحث، وسجلات قواعد البيانات، ومخرجات التحليلات، وأنواع عديدة أخرى من المعلومات.

تُعد خوارزميات الفرز البسيطة مفيدة للتعلم، لكنها تصبح بطيئة عندما يزداد حجم الإدخال. عادةً ما تكون خوارزميات مثل Bubble Sort و Selection Sort و Insertion Sort ذات تعقيد زمني O(n²)، مما يعني أن وقت تشغيلها يزداد بسرعة للمصفوفات الكبيرة.

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

ما هي Quicksort؟

Quicksort هي خوارزمية فرز قائمة على المقارنة (comparison-based sorting algorithm) تعمل عن طريق اختيار عنصر محوري وإعادة ترتيب المصفوفة بحيث تنتقل القيم الأصغر من المحور إلى جانب واحد، والقيم الأكبر من المحور إلى الجانب الآخر.

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

يمكن تلخيص الفكرة الرئيسية كالتالي:

• اختر عنصرًا محوريًا.

• حرّك العناصر الأصغر إلى الجانب الأيسر من العنصر المحوري.

• حرّك العناصر الأكبر إلى الجانب الأيمن من العنصر المحوري.

• افرِز الجزء الأيسر بشكل استدعائي.

• افرِز الجزء الأيمن بشكل استدعائي.

• اجمع النتيجة بشكل طبيعي لأن العنصر المحوري يكون بالفعل في الموضع الصحيح.

تُسمى Quicksort "سريعة" لأنها عادةً ما تكون سريعة جدًا مقارنة بالعديد من خوارزميات الفرز الأساسية.

الفكرة الرئيسية وراء Quicksort

المفهوم الأكثر أهمية في Quicksort هو التقسيم (partitioning). يعني التقسيم إعادة تنظيم المصفوفة حول عنصر محوري مُختار.

على سبيل المثال، لننظر إلى هذه المصفوفة:

[8, 3, 1, 7, 0, 10, 2]

إذا اخترنا 7 كعنصر محوري، فالهدف هو وضع جميع القيم الأصغر من 7 قبله وجميع القيم الأكبر من 7 بعده.

Smaller than pivot: [3, 1, 0, 2]
Pivot:              [7]
Greater than pivot: [8, 10]

بعد التقسيم، يكون العنصر المحوري في موضعه العام الصحيح. القيم على اليسار ليست بالضرورة مفرزة بعد، والقيم على اليمين ليست بالضرورة مفرزة بعد. تحل Quicksort ذلك عن طريق تطبيق العملية نفسها بشكل استدعائي على كل جانب.

مبدأ فرّق تسد في Quicksort

تتبع Quicksort تقنية فرّق تسد (divide-and-conquer). تقوم هذه التقنية بتقسيم مشكلة كبيرة إلى مشكلات أصغر، وتحل المشكلات الأصغر، ثم تجمع النتائج.

في Quicksort، تعمل العملية كالتالي:

• التقسيم (Divide): اختر عنصرًا محوريًا وقسّم المصفوفة إلى عناصر أصغر وأكبر.

• الغزو (Conquer): افرِز الأجزاء اليسرى واليمنى بشكل استدعائي.

• الدمج (Combine): النتيجة تكون مفرزة لأن الجزء الأيسر، والعنصر المحوري، والجزء الأيمن مرتبة بالفعل بشكل صحيح.

هذا الهيكل هو ما يسمح لـ Quicksort بتحقيق أداء O(n log n) في الحالة المتوسطة.

كيف تعمل Quicksort خطوة بخطوة

يمكن فهم Quicksort من خلال هذه الخطوات:

1. اختر عنصرًا محوريًا من المصفوفة.

2. قسّم المصفوفة بحيث تذهب العناصر الأصغر قبل العنصر المحوري وتذهب العناصر الأكبر بعده.

3. طبق Quicksort بشكل استدعائي على الجزء الأيسر.

4. طبق Quicksort بشكل استدعائي على الجزء الأيمن.

5. توقف عندما يحتوي الجزء على صفر أو عنصر واحد لأنه يكون مفرزًا بالفعل.

الحالة الأساسية (base case) مهمة في الاستدعاء الذاتي. بدون حالة أساسية، ستستمر الدالة في استدعاء نفسها إلى الأبد.

مثال تشغيل يدوي

دعنا نفرز يدويًا المصفوفة التالية باستخدام Quicksort:

[8, 3, 1, 7, 0, 10, 2]

لهذا التشغيل اليدوي، سنستخدم العنصر الأخير كعنصر محوري.

التقسيم الأول

المصفوفة هي:

[8, 3, 1, 7, 0, 10, 2]

العنصر المحوري هو العنصر الأخير:

Pivot = 2

الآن نقارن كل عنصر بالعنصر المحوري ونحرك القيم الأصغر من أو تساوي 2 نحو الجانب الأيسر.

باستخدام فكرة تقسيم لوموتو (Lomuto partition idea)، تصبح المصفوفة:

[1, 0, 2, 7, 8, 10, 3]

العنصر المحوري 2 الآن في موضعه الصحيح. يحتوي الجانب الأيسر على قيم أصغر من 2، ويحتوي الجانب الأيمن على قيم أكبر من 2.

Left part:  [1, 0]
Pivot:      [2]
Right part: [7, 8, 10, 3]

فرز الجزء الأيسر

الجزء الأيسر هو:

[1, 0]

العنصر المحوري هو:

Pivot = 0

لا يوجد عنصر أصغر من 0. القيمة 1 أكبر من 0. بعد التقسيم:

[0, 1]

الجزء الأيسر الآن مفرز.

فرز الجزء الأيمن

الجزء الأيمن هو:

[7, 8, 10, 3]

العنصر المحوري هو:

Pivot = 3

لا يوجد عنصر أصغر من 3. القيم 7 و 8 و 10 أكبر من 3. بعد التقسيم:

[3, 8, 10, 7]

الآن 3 في موضعه الصحيح داخل هذا التقسيم.

الجزء الأيمن المتبقي هو:

[8, 10, 7]

العنصر المحوري هو:

Pivot = 7

لا يوجد عنصر أصغر من 7. القيم 8 و 10 أكبر من 7. بعد التقسيم:

[7, 10, 8]

الجزء الأيمن المتبقي هو:

[10, 8]

العنصر المحوري هو:

Pivot = 8

لا يوجد عنصر أصغر من 8. القيمة 10 أكبر من 8. بعد التقسيم:

[8, 10]

المصفوفة النهائية المفرزة

بعد انتهاء جميع الاستدعاءات المتكررة، تكون المصفوفة النهائية المفرزة هي:

[0, 1, 2, 3, 7, 8, 10]

يُظهر هذا التشغيل اليدوي السلوك الرئيسي لـ Quicksort. لا تقوم الخوارزمية ببناء المصفوفة المفرزة عنصرًا تلو الآخر مثل Insertion Sort. بدلاً من ذلك، تقوم بتقسيم المصفوفة بشكل متكرر حول العناصر المحورية حتى تصبح جميع القيم بالترتيب الصحيح.

شجرة الاستدعاء الذاتي لـ Quicksort

يمكن تصور Quicksort كشجرة استدعاء ذاتي. يقسم كل عنصر محوري المصفوفة إلى أجزاء أصغر.

[8, 3, 1, 7, 0, 10, 2]
             pivot 2
        /                  \
    [1, 0]              [7, 8, 10, 3]
   pivot 0                  pivot 3
      \                         \
      [1]                    [8, 10, 7]
                                pivot 7
                                   \
                                 [10, 8]
                                  pivot 8
                                     \
                                     [10]

عندما تكون الأقسام متوازنة، تكون شجرة الاستدعاء الذاتي ضحلة وفعالة. عندما تكون الأقسام غير متوازنة بشكل كبير، تصبح شجرة الاستدعاء الذاتي عميقة وتصبح Quicksort أبطأ.

شبه الكود (Pseudocode)

يمكن وصف خوارزمية Quicksort بسيطة كالتالي:

quickSort(array, low, high):
    if low < high:
        pivotIndex = partition(array, low, high)

        quickSort(array, low, pivotIndex - 1)
        quickSort(array, pivotIndex + 1, high)

تقوم دالة التقسيم بوضع العنصر المحوري في موضعه الصحيح وإرجاع مؤشر ذلك العنصر المحوري.

partition(array, low, high):
    pivot = array[high]
    i = low - 1

    for j from low to high - 1:
        if array[j] <= pivot:
            i = i + 1
            swap array[i] with array[j]

    swap array[i + 1] with array[high]
    return i + 1

يستخدم هذا الإصدار مخطط لوموتو للتقسيم (Lomuto partition scheme)، حيث يتم اختيار العنصر الأخير كعنصر محوري.

مثال Quicksort بلغة PHP

إليك تطبيق PHP نظيف لـ Quicksort باستخدام مخطط لوموتو للتقسيم:

<?php

function quickSort(array &$numbers, int $low, int $high): void
{
    if ($low < $high) {
        $pivotIndex = partition($numbers, $low, $high);

        quickSort($numbers, $low, $pivotIndex - 1);
        quickSort($numbers, $pivotIndex + 1, $high);
    }
}

function partition(array &$numbers, int $low, int $high): int
{
    $pivot = $numbers[$high];
    $i = $low - 1;

    for ($j = $low; $j < $high; $j++) {
        if ($numbers[$j] <= $pivot) {
            $i++;

            [$numbers[$i], $numbers[$j]] = [$numbers[$j], $numbers[$i]];
        }
    }

    [$numbers[$i + 1], $numbers[$high]] = [$numbers[$high], $numbers[$i + 1]];

    return $i + 1;
}

$numbers = [8, 3, 1, 7, 0, 10, 2];

quickSort($numbers, 0, count($numbers) - 1);

print_r($numbers);

سيكون الناتج:

Array
(
    [0] => 0
    [1] => 1
    [2] => 2
    [3] => 3
    [4] => 7
    [5] => 8
    [6] => 10
)

ينفذ هذا التطبيق الفرز في الموقع (in place). يتم تمرير المصفوفة بالمرجع، وبالتالي تقوم الدالة بتعديل المصفوفة الأصلية بدلاً من إنشاء مصفوفة جديدة تمامًا.

مثال Quicksort بلغة JavaScript

إليك نفس الخوارزمية مطبقة بلغة JavaScript:

function quickSort(numbers, low = 0, high = numbers.length - 1) {
    if (low < high) {
        const pivotIndex = partition(numbers, low, high);

        quickSort(numbers, low, pivotIndex - 1);
        quickSort(numbers, pivotIndex + 1, high);
    }

    return numbers;
}

function partition(numbers, low, high) {
    const pivot = numbers[high];
    let i = low - 1;

    for (let j = low; j < high; j++) {
        if (numbers[j] <= pivot) {
            i++;

            [numbers[i], numbers[j]] = [numbers[j], numbers[i]];
        }
    }

    [numbers[i + 1], numbers[high]] = [numbers[high], numbers[i + 1]];

    return i + 1;
}

const numbers = [8, 3, 1, 7, 0, 10, 2];

console.log(quickSort(numbers));

سيكون الناتج:

[0, 1, 2, 3, 7, 8, 10]

يتبع إصدار JavaScript نفس هيكل إصدار PHP. يختار العنصر الأخير كعنصر محوري، ويقسّم المصفوفة، ويفرز كلا الجانبين بشكل استدعائي.

مثال Quicksort الوظيفي (Functional Quicksort)

يمكن أيضًا كتابة Quicksort بأسلوب وظيفي (functional style) أكثر. هذا الإصدار أسهل في القراءة، لكنه يستخدم مصفوفات إضافية وبالتالي يحتاج إلى المزيد من الذاكرة.

function quickSortFunctional(numbers) {
    if (numbers.length <= 1) {
        return numbers;
    }

    const pivot = numbers[numbers.length - 1];
    const left = [];
    const right = [];

    for (let i = 0; i < numbers.length - 1; i++) {
        if (numbers[i] <= pivot) {
            left.push(numbers[i]);
        } else {
            right.push(numbers[i]);
        }
    }

    return [
        ...quickSortFunctional(left),
        pivot,
        ...quickSortFunctional(right)
    ];
}

console.log(quickSortFunctional([8, 3, 1, 7, 0, 10, 2]));

هذا التطبيق مفيد للتعلم لأنه يوضح بوضوح فكرة الجزء الأيسر، والعنصر المحوري، والجزء الأيمن. ومع ذلك، فإن الإصدار الذي يعمل في الموقع (in-place) عادة ما يكون أكثر كفاءة في استخدام الذاكرة.

اختيار العنصر المحوري في Quicksort

العنصر المحوري جزء حاسم في Quicksort. تؤثر جودة العنصر المحوري على مدى توازن الأقسام.

تشمل استراتيجيات اختيار العنصر المحوري الشائعة ما يلي:

• العنصر الأول: بسيط، ولكنه محفوف بالمخاطر إذا كانت المصفوفة مفرزة بالفعل.

• العنصر الأخير: بسيط وشائع في الأمثلة، ولكنه قد يكون محفوفًا بالمخاطر أيضًا.

• عنصر عشوائي: يقلل من فرصة وجود أقسام سيئة باستمرار.

• العنصر الأوسط: غالبًا ما يكون أفضل من اختيار العنصر الأول أو الأخير دائمًا.

• وسيط الثلاثة (Median-of-three): يختار القيمة الوسيطة من بين العناصر الأول والأوسط والأخير.

العنصر المحوري الجيد يقسم المصفوفة إلى جزأين متوازنين بشكل معقول. العنصر المحوري السيئ ينشئ قسمًا صغيرًا جدًا وقسمًا كبيرًا جدًا، مما يجعل الخوارزمية أبطأ.

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

يصف التعقيد الزمني (Time complexity) كيف ينمو وقت تشغيل الخوارزمية مع زيادة حجم الإدخال. بالنسبة لـ Quicksort، يعتمد التعقيد الزمني على مدى توازن الأقسام بعد كل اختيار للعنصر المحوري.

لدى Quicksort ثلاث حالات مهمة للتعقيد الزمني:

• أفضل حالة: O(n log n)

• الحالة المتوسطة: O(n log n)

• أسوأ حالة: O(n²)

تتم خطوة التقسيم بمسح المصفوفة مرة واحدة، وهو ما يكلف O(n). يحدد الهيكل الاستدعائي عدد مستويات التقسيم المطلوبة.

أفضل حالة للتعقيد الزمني: O(n log n)

تحدث أفضل حالة عندما يقسم العنصر المحوري المصفوفة إلى جزأين متساويين تقريبًا في كل مرة.

على سبيل المثال، إذا قسم العنصر المحوري المصفوفة هكذا:

n elements
n/2 elements + n/2 elements
n/4 elements + n/4 elements + n/4 elements + n/4 elements

يصبح عدد مستويات الاستدعاء الذاتي حوالي log n. في كل مستوى، يكلف تقسيم جميع العناصر معًا O(n).

لذلك، أفضل حالة للتعقيد الزمني هي:

O(n log n)

هذا هو السلوك المثالي لـ Quicksort.

الحالة المتوسطة للتعقيد الزمني: O(n log n)

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

في التطبيقات الحقيقية، هذا هو السلوك الشائع لـ Quicksort، خاصة عندما يتم اختيار العنصر المحوري بعناية أو بشكل عشوائي.

التعقيد الزمني للحالة المتوسطة هو:

O(n log n)

هذا هو السبب في اعتبار Quicksort فعالة جدًا في الممارسة.

أسوأ حالة للتعقيد الزمني: O(n²)

تحدث أسوأ حالة عندما ينشئ العنصر المحوري بشكل متكرر أقسامًا غير متوازنة للغاية.

على سبيل المثال، إذا كانت المصفوفة مفرزة بالفعل وكانت الخوارزمية تختار دائمًا العنصر الأخير كعنصر محوري:

[1, 2, 3, 4, 5]

يكون العنصر المحوري دائمًا هو العنصر الأكبر. هذا يعني أن أحد الأقسام يحتوي على جميع العناصر تقريبًا والقسم الآخر فارغ.

يصبح التحليل الاستدعائي كالتالي:

n
n - 1
n - 2
n - 3
...
1

يصبح العمل الكلي تقريبًا:

n + (n - 1) + (n - 2) + ... + 1

هذا ينمو بمقدار n²، لذا فإن أسوأ حالة للتعقيد الزمني هي:

O(n²)

لهذا السبب فإن اختيار العنصر المحوري مهم جدًا في Quicksort.

التعقيد المكاني لـ Quicksort

يصف التعقيد المكاني (Space complexity) مقدار الذاكرة الإضافية التي تستخدمها الخوارزمية. لا تحتاج Quicksort التي تعمل في الموقع (in-place Quicksort) إلى مصفوفة إضافية للفرز، لكنها تستخدم الذاكرة لاستدعاءات الدوال المتكررة.

متوسط التعقيد المكاني هو:

O(log n)

يحدث هذا عندما تكون الأقسام متوازنة وعمق الاستدعاء الذاتي حوالي log n.

أسوأ حالة للتعقيد المكاني هي:

O(n)

يحدث هذا عندما تكون الأقسام غير متوازنة بشكل كبير ويصبح عمق الاستدعاء الذاتي n.

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

هل Quicksort مستقرة؟

عادةً ما تكون Quicksort غير مستقرة في تطبيقاتها الشائعة التي تعمل في الموقع.

خوارزمية الفرز المستقرة (stable sorting algorithm) تحافظ على الترتيب النسبي للعناصر المتساوية. على سبيل المثال، إذا كان منتجان لهما نفس السعر، فإن الفرز المستقر يحافظ عليهما بنفس الترتيب الذي ظهرا به قبل الفرز.

قد تقوم Quicksort بتبديل عناصر متساوية أثناء التقسيم، مما قد يغير ترتيبها الأصلي. لهذا السبب، تُعتبر Quicksort القياسية التي تعمل في الموقع غير مستقرة.

من الممكن إنشاء إصدار مستقر من Quicksort، لكنه عادة ما يتطلب ذاكرة إضافية أو نهج تقسيم معدل.

هل Quicksort تعمل في الموقع؟

يمكن تطبيق Quicksort كخوارزمية فرز تعمل في الموقع (in-place sorting algorithm). يعيد التطبيق الشائع القائم على التقسيم ترتيب العناصر داخل المصفوفة الأصلية باستخدام عمليات التبديل.

ومع ذلك، ليست كل تطبيقات Quicksort تعمل في الموقع. الإصدار الوظيفي الذي ينشئ مصفوفات يسار ويمين منفصلة أسهل في القراءة، لكنه يستخدم ذاكرة إضافية.

لذا الإجابة الصحيحة هي:

• Quicksort في الموقع: نعم، عند تطبيقها مع التقسيم وعمليات التبديل.

• Quicksort الوظيفية: لا، لأنها تنشئ مصفوفات إضافية.

Quicksort مقابل Merge Sort

كل من Quicksort و Merge Sort هما خوارزميات فرز فعالة تعتمد على مبدأ فرّق تسد. وكلاهما عادةً ما يؤديان بشكل أفضل بكثير من خوارزميات O(n²) البسيطة على مجموعات البيانات الكبيرة.

ومع ذلك، لديهما خصائص مختلفة.

• Quicksort لديها تعقيد زمني متوسط O(n log n).

• Merge Sort لديها تعقيد زمني مضمون O(n log n).

• Quicksort يمكن أن تفرز في الموقع بذاكرة إضافية منخفضة.

• Merge Sort عادة ما تحتاج إلى ذاكرة إضافية للدمج.

• Quicksort عادة ما تكون غير مستقرة.

• Merge Sort مستقرة عند تطبيقها بشكل صحيح.

غالبًا ما تكون Quicksort أسرع في الممارسة للمصفوفات لأنها تتمتع بأداء جيد لذاكرة التخزين المؤقت (cache performance) وعبء ذاكرة منخفض. تُفضل Merge Sort غالبًا عندما تكون الاستقرارية مطلوبة أو عند فرز القوائم المرتبطة (linked lists).

Quicksort مقابل Insertion Sort

Insertion Sort بسيطة وفعالة للمصفوفات الصغيرة أو المفرزة تقريبًا. Quicksort أكثر كفاءة لمجموعات البيانات العشوائية الكبيرة.

تستخدم العديد من تطبيقات الفرز الحقيقية نهجًا هجينًا (hybrid approach). تستخدم Quicksort أو خوارزمية مشابهة تعتمد على فرّق تسد للأقسام الكبيرة، ثم تتحول إلى Insertion Sort عندما تصبح الأقسام صغيرة.

يعمل هذا جيدًا لأن Insertion Sort لديها عبء منخفض على المصفوفات الصغيرة، بينما تتعامل Quicksort مع التقسيم على نطاق واسع بكفاءة.

متى يجب على المطورين استخدام Quicksort؟

يجب على المطورين التفكير في Quicksort عندما يحتاجون إلى خوارزمية فرز عامة فعالة ولا تكون الاستقرارية مطلوبة.

Quicksort مفيدة عندما:

• حجم مجموعة البيانات متوسط أو كبير.

• الأداء في الحالة المتوسطة مهم.

• استخدام الذاكرة الإضافية يجب أن يكون منخفضًا.

• البيانات مخزنة في مصفوفة.

• هناك حاجة إلى خوارزمية فرز سريعة تعمل في الموقع.

• يمكن للتطبيق استخدام استراتيجية جيدة لاختيار العنصر المحوري.

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

متى لا يجب استخدام Quicksort

قد لا تكون Quicksort هي الخيار الأفضل في كل موقف.

يجب على المطورين تجنب Quicksort الأساسية عندما:

• الفرز المستقر مطلوب.

• قد يكون الإدخال غالبًا مفرزًا بالفعل واختيار العنصر المحوري ضعيف.

• سلوك O(n²) في أسوأ الحالات غير مقبول.

• قد يصبح عمق الاستدعاء الذاتي مشكلة.

• بيئة البرمجة لديها ذاكرة مكدس (stack memory) محدودة.

في مثل هذه الحالات، قد تكون Merge Sort أو Heap Sort أو TimSort أو وظائف الفرز المضمنة خيارات أفضل.

أخطاء شائعة عند تطبيق Quicksort

Quicksort أكثر تعقيدًا من Bubble Sort و Selection Sort و Insertion Sort، لذا غالبًا ما يرتكب المبتدئون أخطاء في منطق التقسيم أو حدود الاستدعاء الذاتي.

تشمل الأخطاء الشائعة ما يلي:

• نسيان الحالة الأساسية للاستدعاء الذاتي.

• استخدام مؤشرات منخفضة وعالية خاطئة.

• إرجاع مؤشر محوري خاطئ من دالة التقسيم.

• إعادة تضمين العنصر المحوري في الاستدعاءات المتكررة.

• اختيار عنصر محوري سيئ دائمًا.

• خلط مخططات تقسيم مختلفة بشكل غير صحيح.

• استخدام مصفوفات إضافية دون فهم تكلفة الذاكرة.

أهم تفاصيل التطبيق هو التأكد من أن دالة التقسيم تضع العنصر المحوري بشكل صحيح وتعيد مؤشره النهائي.

مثال عملي: فرز أسعار المنتجات

تخيل نظام تجارة إلكترونية يحتاج إلى فرز أسعار المنتجات من الأدنى إلى الأعلى. يمكن استخدام Quicksort لفرز قائمة الأسعار بكفاءة.

<?php

$prices = [99.99, 29.99, 49.99, 19.99, 79.99];

quickSort($prices, 0, count($prices) - 1);

print_r($prices);

ستكون النتيجة:

Array
(
    [0] => 19.99
    [1] => 29.99
    [2] => 49.99
    [3] => 79.99
    [4] => 99.99
)

هذا المثال بسيط، لكنه يوضح كيف يمكن ربط Quicksort بالبيانات الحقيقية التي يتعامل معها المطورون في التطبيقات.

قائمة مرجعية عملية لفهم Quicksort

قبل الانتقال إلى مواضيع الفرز الأكثر تقدمًا، يجب أن يكون المطورون قادرين على الإجابة على هذه الأسئلة:

• ما هو دور العنصر المحوري؟

• ماذا يعني التقسيم؟

• لماذا تستخدم Quicksort الاستدعاء الذاتي؟

• ما هي الحالة الأساسية لـ Quicksort؟

• لماذا التعقيد الزمني المتوسط هو O(n log n)؟

• لماذا يمكن أن تصبح أسوأ حالة O(n²)؟

• كيف يؤثر اختيار العنصر المحوري على الأداء؟

• هل Quicksort مستقرة؟

• هل Quicksort تعمل في الموقع؟

إذا كانت هذه الأسئلة واضحة، فإن المطور يفهم المنطق الحقيقي لـ Quicksort بدلاً من مجرد حفظ الكود.

مزايا Quicksort

تتمتع Quicksort بالعديد من المزايا التي تجعلها واحدة من أشهر خوارزميات الفرز.

• إنها سريعة في الحالات المتوسطة.

• لديها تعقيد زمني متوسط O(n log n).

• يمكن تطبيقها في الموقع.

• عادة ما تستخدم ذاكرة إضافية أقل من Merge Sort.

• تعمل بشكل جيد للمصفوفات.

• تعلّم مفاهيم مهمة مثل الاستدعاء الذاتي، والتقسيم، ومبدأ فرّق تسد.

هذه المزايا تجعل Quicksort خوارزمية أساسية للطلاب والمطورين.

عيوب Quicksort

لدى Quicksort أيضًا قيود يجب على المطورين فهمها.

• أسوأ حالات التعقيد الزمني لها هي O(n²).

• عادة ما تكون غير مستقرة.

• اختيار العنصر المحوري السيئ يمكن أن يقلل الأداء.

• قد تستهلك الاستدعاءات المتكررة ذاكرة المكدس (stack memory).

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

بسبب هذه القيود، غالبًا ما تستخدم أنظمة الإنتاج خوارزميات فرز محسنة أو هجينة بدلاً من Quicksort البسيطة المستندة إلى الكتب.

الخاتمة

Quicksort هي خوارزمية فرز قوية تعتمد على مبدأ فرّق تسد، تقوم بفرز البيانات عن طريق اختيار عنصر محوري، وتقسيم المصفوفة حول هذا العنصر المحوري، وفرز الأجزاء الأصغر بشكل استدعائي.

تعقيدها الزمني في الحالة المتوسطة وأفضل حالة هو O(n log n)، مما يجعلها أسرع بكثير من Bubble Sort و Selection Sort و Insertion Sort لمجموعات البيانات العشوائية الكبيرة. ومع ذلك، فإن أسوأ حالات التعقيد الزمني لها هي O(n²)، خاصة عندما يؤدي اختيار العنصر المحوري إلى أقسام غير متوازنة للغاية.

يمكن تطبيق Quicksort في الموقع، مما يجعلها فعالة في استخدام الذاكرة مقارنة بخوارزميات الفرز التي تتطلب مصفوفات إضافية. ومع ذلك، عادة ما تكون غير مستقرة، وتتطلب طبيعتها الاستدعائية تطبيقًا دقيقًا.

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