QuickSelect: شرح خوارزمية التحديد السريع مع أمثلة التعليمات البرمجية

ما هو QuickSelect؟

QuickSelect عبارة عن خوارزمية تحديد للعثور على أصغر عنصر K-th في قائمة لم يتم فرزها.

شرح الخوارزمية

بعد العثور على المحور (الموضع الذي يقسم القائمة إلى جزأين: كل عنصر على اليسار أقل من المحور وكل عنصر على اليمين أكثر من المحور) ، تتكرر الخوارزمية فقط للجزء الذي يحتوي على الحرف k أصغر عنصر.

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

التحديد Psudocode

Input : List, left is first position of list, right is last position of list and k is k-th smallest element. Output : A new list is partitioned. quickSelect(list, left, right, k) if left = right return list[left] // Select a pivotIndex between left and right pivotIndex := partition(list, left, right, pivotIndex) if k = pivotIndex return list[k] else if k < pivotIndex right := pivotIndex - 1 else left := pivotIndex + 1 

تقسيم

القسم هو العثور على المحور كما هو مذكور أعلاه. (كل عنصر على اليسار أقل من المحور وكل عنصر على اليمين أكثر من المحور) هناك خوارزميتان لإيجاد محور القسم.

• قسم لوموتو
• قسم هور

قسم لوموتو

يختار هذا القسم المحور الذي يكون عادةً العنصر الأخير في المصفوفة. تحتفظ الخوارزمية بالفهرس i أثناء قيامها بمسح المصفوفة باستخدام فهرس آخر j بحيث تكون العناصر من lo إلى i (شاملة) أقل من المحور أو مساوية له ، والعناصر i + 1 إلى j-1 (شاملة) أكبر من محور.

يتدهور هذا المخطط O(n^2)عندما تكون المصفوفة جاهزة بالفعل.

algorithm Lomuto(A, lo, hi) is pivot := A[hi] i := lo for j := lo to hi - 1 do if A[j] < pivot then if i != j then swap A[i] with A[j] i := i + 1 swap A[i] with A[hi] return i 

قسم هور

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

ثم يتم تبديل العناصر المقلوبة. عندما تلتقي المؤشرات ، تتوقف الخوارزمية وتعيد الفهرس النهائي. هناك العديد من المتغيرات لهذه الخوارزمية.

algorithm Hoare(A, lo, hi) is pivot := A[lo] i := lo - 1 j := hi + 1 loop forever do i := i + 1 while A[i]  pivot if i >= j then return j swap A[i] with A[j]