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

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

التصنيفات

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

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

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

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

الترتيب الذي يضم $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) (ترتيب نسبي متغير)

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

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

ملف:Nuvola apps edu mathematics-ar.svg

بوابة رياضيات تصفح مقالات ويكيبيديا المهتمة بالرياضيات.

ca:Algorisme d'ordenació cs:Řadicí algoritmus da:Sorteringsalgoritme de:Sortierverfahren Sorting algorithm]] es:Algoritmo de ordenamiento et:Sortimisalgoritm fa:الگوریتم مرتب‌سازی fi:Lajittelualgoritmi fr:Algorithme de tri he:מיון (מדעי המחשב) hu:Rendezés (programozás) hy:Տեսակավորման ալգորիթմ is:Röðunarreiknirit it:Algoritmo di ordinamento ja:ソート kk:Мәліметтерді сұрыптау ko:정렬 알고리즘 ku:Algorîtmayê rêzkerdişî lb:Zortéieralgorithmus lt:Rikiavimo algoritmas lv:Datu šķirošanas algoritmi mhr:Ойыркалымаш nl:Sorteeralgoritme no:Sorteringsalgoritme pl:Sortowanie pt:Algoritmo de ordenação ru:Алгоритм сортировки sk:Triediaci algoritmus sl:Algoritmi za urejanje podatkov sv:Sorteringsalgoritm ta:வரிசையாக்கப் படிமுறை th:ขั้นตอนวิธีการเรียงลำดับ tr:Sıralama algoritması uk:Алгоритм сортування vi:Thuật toán sắp xếp zh:排序算法