فرز تكيفي

تُصنّف خوارزمية الفرز ضمن فئة الفرز التكيفي إذا كانت تستفيد من الترتيب الموجود في مدخلاتها. فهي تستفيد من الترتيب المسبق في تسلسل المدخلات - أو من قدر محدود من عدم الانتظام وفقًا لتعريفات مختلفة لمقاييس عدم الانتظام - وتُنجز الفرز بسرعة أكبر. عادةً ما يتم تنفيذ الفرز التكيفي عن طريق تعديل خوارزميات الفرز الموجودة.

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

تُعدّ هذه ميزة جذابة لخوارزمية الفرز، لأنّ التسلسلات شبه المرتبة شائعة في التطبيقات العملية. وبالتالي، يمكن تحسين أداء خوارزميات الفرز الحالية من خلال مراعاة الترتيب الموجود في المدخلات.

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

يُعد فرز الإدراج مثالاً كلاسيكياً على خوارزمية الفرز التكيفي . ^{[ 1 ]} في خوارزمية الفرز هذه، يتم مسح المدخلات من اليسار إلى اليمين، ويتم العثور بشكل متكرر على موضع العنصر الحالي، وإدراجه في مصفوفة من العناصر التي تم فرزها مسبقًا.

فيما يلي الشفرة الزائفة لخوارزمية فرز الإدراج (المصفوفة X تبدأ من الصفر ):

إجراء فرز الإدراج (X): من أجل j = 1 إلى طول(X) - 1 نفّذ t ← X[j] i ← j طالما أن i > 0 و X[i - 1] > t نفّذ X[i] ← X[i - 1] i ← i - 1 نهاية X[i] ← t نهاية

يمكن وصف أداء هذه الخوارزمية من حيث عدد عمليات الانعكاس في المدخلات، ثم ⁠${\displaystyle T(n)}$سيكون مساوياً تقريباً لـ${\displaystyle I(A)+(n-1)}$، حيث​${\displaystyle I(A)}$يمثل عدد الانعكاسات. باستخدام هذا المقياس للفرز المسبق - كونه نسبيًا لعدد الانعكاسات - يستغرق فرز الإدراج وقتًا أقل للفرز كلما اقتربت مصفوفة البيانات من الفرز.

ومن الأمثلة الأخرى على خوارزميات الفرز التكيفي: فرز الكومة التكيفي ، وفرز الدمج التكيفي ، وفرز الصبر ، ^{[ 2 ]} وفرز شيل ، وفرز السلوست ، وفرز سبلاي ، وفرز تيم ، وفرز الشجرة الديكارتية . ^{[ 3 ]}

• خوارزميات الفرز

• هاجيروب، توربين؛ جيركي كاتجاينن (2004). نظرية الخوارزمية – سوات 2004 . برلين هايدلبرغ: سبرينغر-فيرلاغ. ص 221 – 222. ISBN  3-540-22339-8.
• ميهتا، دينش ب.؛ سرتاج ساهني (2005). هياكل البيانات وتطبيقاتها . الولايات المتحدة الأمريكية: تشابمان آند هول/سي آر سي. الصفحات  11-8 و11-9. ISBN 1-58488-435-5.
• بيترسون، أولا؛ أليستير موفات (1992). إطار عمل للفرز التكيفي . سلسلة محاضرات في علوم الحاسوب. المجلد  621. برلين: سبرينغر برلين / هايدلبرغ. الصفحات 422-433 . doi : 10.1007/3-540-55706-7_38 . ISBN  978-3-540-55706-7ISSN 1611-3349​​