fbpx
الفضائيون

خوارزمية الفرز السريع (Quick Sort)

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

تحدّثنا في مقالات سابقة عن عدّة أنواع لخوارزميات الفرز، الآن سنكمل في سلسلتنا ونبدأ بالحديث عن خوارزمية الفرز السريع (Quick Sort).

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

هي خوارزمية تستند إلى مفهوم فرّق- تَسُد وتعتمد على فكرة اختيار عنصر ليكون المحور الذي يقسم المصفوفة؛ بحيث تكون العناصر التي تصغره في القيمة تقع إلى يساره والتي تكبره في القيمة تقع على يمينه. ثم إنّها تعمل على خفض درجة التعقيد وإزالة المصفوفات الوسيطة (المؤقتة) التي لاحظت استخدامها في خوارزمية الفرز بالدمج.

ماهي آلية عمل الخوارزمية؟

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

enter image description here

سترد العناصر التالية، في التطبيق البرمجي أدناه، وهي:

  • A[]: هي المصفوفة المطلوب ترتيب عناصرها.
  • start: الجزء اليساري من المصفوفة.
  • end: الجزء اليميني من المصفوفة.
  • i: الحد الذي يفصل بين العناصر الأصغر من العنصر المحوري، والعناصر الأكبر.
  • j: الحد بين الجزء المُقسَّم (partitioned part) من المصفوفة والجزء غير المُقسَّم (unpartitioned part).
  • piv: العنصر المحوري.

التابع (الدالّة) السابق هو تابع التقسيم، أما التابع التالي فهو التابع العودي الخاص بعملية الفرز:

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

مثال:

الآن، لتوضيح الفكرة بشكل أفضل سنأخذ مثال، لتكن لدينا المصفوفة التالية:

A= [9 , 7 , 8 , 3 , 2 , 1]

قبل أن تكمل، تأمل مخطط الخوارزمية التالي قليلًا.

enter image description here

 لماذا تم اختيار الرقم 7 في المخطط أعلاه؟

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

بالنسبة للعناصر الأصغر من الرقم 7، سيختار التابع  randpartition() الرقم 2 كعنصر محوري، وذلك في الاستدعاء الخامس له، ومن ثمّ يبدّل بينه وبين العنصر الأول ويستدعي التابع partition(). بعد الاستدعاءَين السابع والثامن، لن يكون هنالك حاجة لاستدعاءات أخرى؛ بسبب تبقّي عنصر واحد فقط بعد كل استدعاء. وبشكل مماثل يمكن تتبع الاستدعاءات بالنسبة للقسم الثاني الذي يحوي العناصر الأكبر من 7.

الكود البرمجي الخاص بالتابع randpartition():

ما الفائدة من الاختيار العشوائي للعنصر المحوري؟

للتقليل من زمن تنفيذ الخوارزمية أي درجة تعقيدها.

درجة تعقيد الخوارزمية (Time Complexity):

تعقيد من رتبة

O(N2)

في الحالة الأسوأ، لكن بوجود العشوائية تصبح درجة التعقيد متراوحة بين

O(N2) و O(N.LogN)

وغالبًا

O(N.LogN).

المُساهمون:
  • ترجمة: نور عبدو

إضافة تعليق

الفضائيون

الفضائيون عبارة عن مجتمع مكون من أفراد يتعلمون معًا ويُشاركون هذه المعرفة مع العالم. نحن نقدم مرجعًا علميًا ينمو باستمرار يشمل مواد تعليمية ومقالات علمية عالية الدقة والجودة، بفضل الجهد الكبير الذي يبذله متطوعونا في الإعداد والمراجعة والتدقيق لتقديم محتوى جادّ ومؤثر، يُمكنك ولوجه مجانًا بشكل كامل.