إنتروسليكت

في علوم الحاسوب ، تُعدّ خوارزمية introselect (اختصارًا لـ "الاختيار الاستبطاني") خوارزمية اختيار هجينة تجمع بين خوارزميتي quickselect و median of medians ، وتتميز بأداء متوسط ​​سريع وأداء مثالي في أسوأ الحالات. ترتبط خوارزمية introselect بخوارزمية فرز introsort ، فهما تطويران مماثلان لخوارزميتي quickselect و quicksort الأساسيتين ، حيث تبدآن بالخوارزمية السريعة ذات الأداء المتوسط ​​الجيد والتكلفة المنخفضة، ثم تعودان إلى خوارزمية مثالية في أسوأ الحالات (ذات تكلفة أعلى) إذا لم تتقدم الخوارزمية السريعة بالسرعة الكافية. قدّم ديفيد موسر هاتين الخوارزميتين في ( Musser 1997 ) ، بهدف توفير خوارزميات عامة لمكتبة C++ القياسية تتميز بأداء متوسط ​​سريع وأداء مثالي في أسوأ الحالات، مما يسمح بتقليل متطلبات الأداء. ^{[ 1 ]}

مع ذلك، في معظم تطبيقات مكتبة C++ القياسية، تُستخدم خوارزمية "introselect" مختلفة، تجمع بين خوارزميتي quickselect و heapselect ، ويبلغ زمن تشغيلها في أسوأ الحالات O ( n log n ). ^{[ 2 ]} لا يشترط معيار C++ المبدئي، اعتبارًا من عام 2022، أي متطلبات على أداء أسوأ الحالات، مما يسمح بهذا الخيار. ^{[ 3 ]}

يحقق فرز Introsort أداءً عمليًا يُضاهي فرز Quicksort مع الحفاظ على أداء O ( n log n ) في أسوأ الحالات، وذلك من خلال دمج خوارزميتي Quicksort و Heapsort . يبدأ Introsort بخوارزمية Quicksort، لذا يحقق أداءً مشابهًا لها إذا نجحت، ثم يعود إلى خوارزمية Heapsort (التي تتمتع بأداء مثالي في أسوأ الحالات) إذا لم يتقدم Quicksort بالسرعة الكافية. وبالمثل، يجمع introselect بين Quickselect وMedian of Medians لتحقيق اختيار خطي في أسوأ الحالات بأداء مشابه لـ Quickselect.

تعتمد خوارزمية Introselect على البدء بخوارزمية Quickselect، ثم الانتقال إلى خوارزمية اختيار خطية في أسوأ الحالات (خوارزمية Blum-Floyd-Pratt-Rivest-Tarjan لمتوسط ​​الوسائط ) فقط في حال تكرارها مرات عديدة دون إحراز تقدم كافٍ. تُعدّ استراتيجية التبديل هي المحتوى التقني الرئيسي للخوارزمية. ولا يكفي مجرد تقييد التكرار بعمق ثابت، لأن ذلك سيؤدي إلى تبديل الخوارزمية في جميع القوائم الكبيرة بما يكفي. يناقش موسر نهجين بسيطين:

• احتفظ بسجل لأحجام الأقسام الفرعية التي تمت معالجتها حتى الآن. إذا تم إجراء k استدعاءات متكررة دون تقليل حجم القائمة إلى النصف، فعندئذٍ، بالنسبة لقيمة k موجبة صغيرة ، انتقل إلى خوارزمية الحالة الأسوأ الخطية.
• اجمع أحجام جميع الأقسام التي تم إنشاؤها حتى الآن. إذا تجاوز هذا المجموع حجم القائمة مضروبًا في ثابت موجب صغير k ، فانتقل إلى خوارزمية الحالة الأسوأ الخطية. يسهل تتبع هذا المجموع في متغير عددي واحد.

كلا النهجين يحدان من عمق التكرار إلى k ⌈log n ⌉ = O (log n ) ووقت التشغيل الإجمالي إلى O ( n ) .

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

• خوارزمية فلويد-ريفست