خوارزميات الترتيب

في المعلوميات أو الرياضيات, خوارزمية الترتيب هي خوارزمية تمكن من تنظيم مجموعة عناصر حسب ترتيب محدد. العناصر المراد ترتيبها توجد في مجموعة مزودة بعلاقة ترتيب.

[تحرير] التصنيفات

تصنيف خوارزميات الترتيب مهم جدا, لأنه يمكن من اختيار نوع الخوارزمية الأكثر مناسبة للمشكل المعالج, مع الأخد بعين الإعتبار السلبيات الموجودة في الخوارزمية.

[تحرير] تعقيد الخوارزمية

• تعقيد الخوارزمية الزمني في الحالات الأكثر تعقيدا يمكن من تحديد الحد الأقصى لعدد العمليات التي يجب استعمالها لترتيب عناصر مجموعة مكونة من n عنصر. نستعمل لترميز هذا التعقيد لاندو: O.
• تعقيد الخوارزمية الزمني في الحالة المتوسطة تمكن من مقارنة خوارزميات الترتيب و إعطاء فكرة عن الوقت اللازم لتنفيذ الخوارزمية.
• تعقيد الخوارزمية المكاني قي الحالات الأكثر تعقيدا أو الحالات المتوسطة تمثل كمية الذاكرة المستعملة في خوارزمية الترتيب. و هي أيضا مرتبطة بعدد عناصر المجموعة.

في معظم الحالات , و بالنسبة للبعض .

الترتيب الذي يضم في المتوسط يعتبر جيدا.

[تحرير] مميزات المكان

نقول أن خوارزمية مكانية اذا لم تستعمل سوى عدد محدد من المتغيرات و تُغير مباشرة المجموعة المراد ترتيبها. هذا يتطلب استعمال بنية للمعطيات مثلا جدول.

[تحرير] مميز الثبات

تكون الخوارزمية ثابتة اذا كان يحافظ على الترتيب النسبي للكميات المتساوية بالنسبة لعلاقة الترتيب.

مثال, بالنسبة للعناصر الآتية:

(4, 1) (3, 1) (3, 7) (5, 6)

الذي نرتبها حسب الاحداثية الأولى (المفتاح) نجد حالتين, عندما يتم احترام الترتيب النسبي و عندما لا يحترم:

(3, 1) (3, 7) (4, 1) (5, 6) (ترتيب نسبي محترم)

(3, 7) (3, 1) (4, 1) (5, 6) (ترتيب نسبي متغير)

[تحرير] أمثلة و تقنيات الترتيب

• ترتيب الفقاعات: خوارزمية رباعية,
• ترتيب الاختيار: خوارزمية رباعية,
• ترتيب بالإدراج: خوارزمية رباعية,
• ترتيب سريع: في الحالات المتوسطة, لكن رباعي في الحالات الصعبة.