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

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

في معظم الحالات ${\displaystyle T(n)=O(n^{2})\,}$، وبالنسبة للبعض ${\displaystyle T(n)=O(nlog(n))\,}$.

الترتيب الذي يضم ${\displaystyle nlog(n)\,}$في المتوسط يعتبر جيدا.

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

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

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

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

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

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

• ترتيب الفقاعات: خوارزمية رباعية, ${\displaystyle T(n)=O(n^{2})\,}$
• ترتيب الاختيار: خوارزمية رباعية, ${\displaystyle T(n)=O(n^{2})\,}$
• ترتيب بالإدراج: خوارزمية رباعية, ${\displaystyle T(n)=O(n^{2})\,}$
• ترتيب سريع: ${\displaystyle O(n\log n)\,}$ في الحالات المتوسطة، لكن رباعي في الحالات الصعبة.