إنتروسورت

يُعدّ فرز Introsort، أو الفرز الاستبطاني، خوارزمية فرز هجينة تجمع بين الأداء المتوسط ​​السريع والأداء الأمثل (تقاربًا) في أسوأ الحالات. تبدأ هذه الخوارزمية بفرز Quicksort ، ثم تنتقل إلى فرز Heapsort عندما يتجاوز عمق الاستدعاء مستوىً مُحددًا بناءً على ( لوغاريتم ) عدد العناصر المراد فرزها، وأخيرًا تنتقل إلى فرز الإدراج عندما يقل عدد العناصر عن حدٍّ معين. يجمع هذا الأسلوب بين مزايا الخوارزميات الثلاث، مع أداء عملي يُضاهي Quicksort على مجموعات البيانات النموذجية، ووقت تشغيل في أسوأ الحالات O ( n log n ) بفضل فرز Heapsort. وبما أن الخوارزميات الثلاث المستخدمة هي خوارزميات فرز مقارنة ، فإن Introsort تُصنّف أيضًا ضمن خوارزميات فرز المقارنة.

ابتكر ديفيد موسر خوارزمية Introsort في بحثه المنشور عام 1997 ، حيث قدم أيضًا خوارزمية introselect ، وهي خوارزمية اختيار هجينة تعتمد على خوارزمية quickselect (وهي نسخة معدلة من quicksort)، وتعتمد في حال عدم تحقق الشرط على وسيط الوسائط ، مما يوفر تعقيدًا خطيًا في أسوأ الحالات، وهو الأمثل. وقد طُرحت كلتا الخوارزميتين بهدف توفير خوارزميات عامة لمكتبة C++ القياسية ، تتميز بأداء متوسط ​​سريع وأداء مثالي في أسوأ الحالات، مما يسمح بتقليل متطلبات الأداء. ^{[ 1 ]} تُعدّ خوارزمية Introsort خوارزميةً تُنفّذ في مكانها ، وهي غير مستقرة .

إذا توفر تطبيق لخوارزمية فرز الكومة ووظائف تقسيم من النوع الذي نوقش في مقالة الفرز السريع ، فيمكن وصف الفرز الداخلي بإيجاز كما يلي:

إجراء الفرز (A: مصفوفة): أقصى عمق ← ⌊log 2 (طول(A))⌋ × 2 introsort(A, maxdepth) الإجراء introsort(A, maxdepth): n ← طول(A) إذا كان n < 16: فرز الإدراج (A) وإلا إذا كانت قيمة maxdepth تساوي 0: heapsort(A) آخر : p ← partition(A) // بافتراض أن هذه الدالة تقوم بتحديد المحور، فإن p هو الموضع النهائي للمحور introsort(A[1:p-1], maxdepth - 1) introsort(A[p+1:n], maxdepth - 1)

العامل 2 في العمق الأقصى اختياري، ويمكن ضبطه لتحقيق الأداء الأمثل. يرمز A [ i : j ] إلى شريحة المصفوفة التي تضم العناصر من i إلى j، بما في ذلك A [ i ] و A [ j ] . ويُفترض أن تبدأ الفهارس من 1 (العنصر الأول في المصفوفة A هو A[1] ).

في خوارزمية الفرز السريع، تُعدّ عملية اختيار العنصر المحوري (العنصر الذي تُقسّم القائمة حوله) من العمليات الأساسية. أبسط خوارزمية لاختيار العنصر المحوري هي اختيار العنصر الأول أو الأخير من القائمة، مما يُؤدي إلى أداء ضعيف في حالة المدخلات المُرتّبة أو شبه المُرتّبة. يستخدم مُعدّل نيكلاوس ويرث العنصر الأوسط لتجنّب هذه الحالات، مما يُؤدي إلى تباطؤ كبير في الأداء (O( n² )) في حالة التسلسلات المُصطنعة. تعتمد خوارزمية اختيار العنصر المحوري باستخدام وسيط العناصر الثلاثة على وسيط العناصر الأول والأوسط والأخير من القائمة؛ ومع ذلك، على الرغم من أن هذه ^{الخوارزمية} تُحقق أداءً جيدًا مع العديد من المدخلات الواقعية، إلا أنه لا يزال من الممكن ابتكار قائمة "وسيط العناصر الثلاثة" تُؤدي إلى تباطؤ كبير في أداء خوارزمية الفرز السريع المُعتمدة على هذه التقنية.

أفاد موسر أن زمن تشغيل خوارزمية الفرز الداخلي (introsort) على تسلسل قاتل متوسط ​​من 100,000 عنصر كان 1/200 من زمن تشغيل خوارزمية الفرز السريع المتوسط ​​من 3. كما درس موسر تأثير فرز سيدجويك الصغير المؤجل على ذاكرة التخزين المؤقت ، حيث يتم فرز النطاقات الصغيرة في النهاية في تمريرة واحدة من فرز الإدراج . وذكر أن ذلك قد يضاعف عدد حالات عدم العثور على البيانات في ذاكرة التخزين المؤقت، لكن أداءها مع قوائم الانتظار ذات النهايتين كان أفضل بكثير، ويجب الاحتفاظ بها في مكتبات القوالب، ويعود ذلك جزئيًا إلى أن الفائدة المرجوة من إجراء الفرز فورًا في الحالات الأخرى لم تكن كبيرة.

يتم استخدام Introsort أو أحد المتغيرات في عدد من وظائف الفرز في المكتبة القياسية ، بما في ذلك بعض تطبيقات الفرز في لغة C++ .

يستخدم تطبيق stl_algo.h الخاص بمكتبة القوالب القياسية SGI C++ لشهر يونيو 2000 لفرز غير مستقر نهج Musser introsort مع عمق التكرار للتبديل إلى فرز الكومة الذي يتم تمريره كمعامل، واختيار محور الوسيط 3، وتمرير فرز الإدخال النهائي Knuth للأقسام الأصغر من 16.

مكتبة GNU Standard C++ مشابهة: تستخدم introsort بعمق أقصى يبلغ 2×log ₂ n ، متبوعًا بفرز الإدراج على الأقسام الأصغر من 16. ^{[ 2 ]}

تستخدم مكتبة libc++ في LLVM أيضًا خوارزمية الفرز الداخلي (introsort) بعمق أقصى يبلغ 2×log₂n _، إلا أن حد حجم الفرز بالإدراج يختلف باختلاف أنواع البيانات (30 إذا كانت عمليات التبديل بسيطة، و6 في غير ذلك). كما تُعالج المصفوفات التي يصل حجمها إلى 5 عناصر بشكل منفصل. ^{[ 3 ]} يقدم كوتينين (2022) نظرة عامة على بعض التغييرات التي أجرتها LLVM، مع التركيز على إصلاح مشكلة التربيعية في عام 2022. ^{[ 4 ]}

تستخدم مكتبة فئات إطار عمل Microsoft .NET ، بدءًا من الإصدار 4.5 (2012)، خوارزمية الفرز الداخلي بدلاً من خوارزمية الفرز السريع البسيطة. ^{[ 5 ]}

تستخدم لغة Go تعديلًا لخوارزمية فرز الإدخال: فبالنسبة للشرائح التي تحتوي على 12 عنصرًا أو أقل، تستخدم فرز الإدراج ، أما بالنسبة للشرائح الأكبر حجمًا، فتستخدم فرزًا سريعًا يتغلب على الأنماط، بالإضافة إلى وسيطة الوسائط الثلاثة الأكثر تطورًا لاختيار المحور. ^{[ 6 ]} قبل الإصدار 1.19، كانت تستخدم فرز شل للشرائح الصغيرة.

تستخدم لغة جافا ، بدءًا من الإصدار 14 (2020)، خوارزمية فرز هجينة تستخدم فرز الدمج للمصفوفات ذات البنية العالية (المصفوفات التي تتكون من عدد قليل من المصفوفات الفرعية المرتبة) وفرز الإدخال في غير ذلك لفرز مصفوفات الأعداد الصحيحة، والأعداد الطويلة، والأعداد العشرية، والأعداد المضاعفة. ^{[ 7 ]}