خوارزمية الفرز السريع

يعتبر الفرز السريع من أشهر خوارزميات الفرز، لأنه يتم تنفيذه بعدة لغات برمجة داخل المكتبة القياسية. لماذا يتم استخدام هذه الخوارزمية؟؟
نظرًا لسرعتها، تعد خوارزمية الفرز السريع واحدة من أسرع خوارزميات الفرز التي تتمتع بتعقيد زمني قدره O(n * log n) حيث n هو حجم المصفوفة وlog هو اللوغاريتم الأساسي 2.

كيف يعمل؟

المفهوم الرئيسي الضروري لفهم خوارزمية الفرز السريع هو استراتيجية فرق تسد.
إن استراتيجية فرق تسد هي مصطلح عسكري مشهور، وكان يعني أنه لغزو أمة كبيرة، يجب عليك أولاً أن تجعل الأمة مقسمة، غالبًا بسبب صراع داخلي أو حرب أهلية، ثم تذهب وتدمر الأمة بأكملها بينما هم كذلك. مشغول.
حسنًا، ولكن كيف يُترجم هذا المفهوم إلى علوم الكمبيوتر؟ تعني فرق تسد، في الخوارزميات، أنه يحل مشكلة عن طريق حل مشاكل أصغر، وهذا يشبه إلى حد ما مفهوم الاستقراء الرياضي، حيث نؤسس f(1)، ثم نؤسس f(n) وبعد ذلك، لقد أظهرنا أن f(n - 1) يعمل، ومن خلال القيام بذلك، يمكننا إثبات المفهوم.
تعمل مسائل فرق تسد بنفس الطريقة، أولاً نقوم بحل أبسط مشكلة، والتي غالبًا ما تسمى الحالة الأساسية، ثم نقوم بصياغة الحالة العودية، وفي النهاية، نجعل المشكلة مقسمة إلى أبسط المشكلات، لأن تلك التي نعرف كيفية حلها.

الخوارزمية

سأعرض تنفيذًا في لغة C، ثم سأشرح سطرًا تلو الآخر كيف يعمل هذا، نظرًا لأنها فكرة معقدة إلى حد ما.

#include 
#include 
#include 

void _quick_sort(uint32_t *arr, size_t low, size_t high);
void quick_sort(uint32_t *arr, size_t size);

int32_t main(void)
{
    uint32_t list[] = {1, 4, 5, 10, 2, 9, 17, 100, 4, 2, 1000};

    // 11 is the number of elements list has
    // this is really usefull, because whenever we pass an array to a function, it decays as a pointer
    // due to this, if the function is in another translation layer it won't be able to know, so it can do the 
    // sizeof(list) / sizeof(list[1]) trick
    quick_sort(list, 11);

    for (size_t i = 0; i  i are greater than the pivot
        // so we just need to swap the pivot with the element at index i
        if (arr[j] = high)
    {
        return;
    }

    // The pivot index is the index of the pivot element after partitioning,
    // so it means that the list is weakly sorted around the pivot,
    // (i.e. all elements to the left of the pivot are less than the pivot)
    // and all elements to the right are greater then
    size_t pivot_index = partition(arr, low, high);

    // Here we have a cool implementation detail
    // since pivot_index is a size_t, it is unsigned
    // and if we subtract 1 from an unsigned 0,
    // we get undefined behavior
    // This would happen, if the last element should be the first
    // in this case, no sorting is necessary, since there is nothing
    // before it
    if (pivot_index > 0)
    {
        // Sorting the left hand window
        // they have the bounds, [low, pivot_index - 1]
        // the -1 is so it is inclusive
        // because we now know the pivot is in the right spot
        _quick_sort(arr, low, pivot_index - 1);
    }

    // Same thing with before, now, we are sorting the right side of the window
    _quick_sort(arr, pivot_index   1, high);
}

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

هناك فارق بسيط مهم في اختيار محور في خوارزمية الفرز السريع، إذا اخترنا محاور سيئة، فسوف ينتهي بنا الأمر بتعقيد رهيب، لأنه في كل مرة نقوم بتقسيم المصفوفة إلى صفيفين، ينتهي بنا الأمر بمحور صغير المصفوفات، في هذه الحالة، سيكون لدينا n استدعاءات متكررة وسيتعين علينا السير n من العناصر، وبالتالي فإن الفرز السريع له أسوأ سيناريو لـ O(n*n)، وهو أمر فظيع، لذا علينا توخي الحذر عندما عند اختيار محور، أحد الأساليب الجيدة هو اختيار رقم عشوائي، ومن خلال القيام بذلك، نحن على يقين من أننا سنحصل على الحالة الوسطى، وهي O(n * log n)، log n لأنه في الحالة المتوسطة، سوف نقوم بالتقسيم المصفوفة إلى مصفوفتين تحتويان على نصف عناصر المصفوفة الأولية، وبما أنه يتعين علينا المرور عبر جميع العناصر، فهناك عامل n.