ترتيب بالإدراج
من ويكيبيديا، الموسوعة encyclopedia
الترتيب بالإدراج (بالإنجليزية: Insertion Sort) هي خوارزمية ترتيب بسيطة مبدأها مشابه لما يستعملهُ أغلب الناس عند ترتيب أوراقهم أو ملفاتهم.[1][2][3] وتعمل الخوارزمية بالمرور على البيانات وإدراج كل مدخل في مكانه أولا بأول، ولا تعدّ هذه الطريقة الأفضل بالنسبة للقوائم الكبيرة حيث من يُفضل استخدام خوارزميات متطورة أكثر مثل الترتيب السريع أو الترتيب الدمجي، ولكن للترتيب بالإدراج عدة نقاط إيجابية:
- خوارزمية بسيطة: قام عالم الحاسوب جون بنتلي بتطبيق الخوارزمية في ثلاثة سطور بلغة سي ونسخة محسنة في 5 سطور.[3]
- أكثر كفاءة للمصفوفات الصغيرة جداً كغيرها من الخوارزمات الرباعية.
- كفاءة أعلى عند التطبيق من أغلب خوارزمات الترتيب التربيعية البسيطة مثل الترتيب بالاختيار أو الترتيب بالفقاعات.
- متأقلمة الأداء: إذ تتحسن كفاءتها كلما كانت المصفوفة مرتبة أكثر، وينخفض التعقيد الزمني للترتيب إلى O(nk) في مصفوفة لا يبعد أي مدخل أكثر من k خانة عن مكانها المرتب.
- الثبات: لا يغير الترتيب النسبي للمدخلات ذات مفاتيح متساوية.
- في المكان: يحتاج فقط إلى O(1) ذاكرة اضافية.
- فورية: أي أنها تستطيع ترتيب المعلومات أثناء تلقيها بدل الانتظار حتى تلقي المصفوفة الكاملة.
معلومات سريعة الصنف, بنية البيانات ...
ترتيب بالإدراج
الصنف | |
---|---|
بنية البيانات | |
مشتق من |
أسوء حالة |
О(n2) مقارنات وتبديلات |
---|---|
الحالة المُثلى |
O(n) مقارنات و O(1) تبديلات |
الأداء الوسطي |
О(n2) مقارنات وتبديلات |
أسوأ حالة تعقيد مكاني |
إغلاق
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/2/25/Insertion_sort_animation.gif/220px-Insertion_sort_animation.gif)
وبرمجياً، تتطلب الخوارزمية عدد مقارنات من الرتبة ، ومعدل تبديلات من الرتبة
، وتعقيد زمني برتبة
.