خوارزمية فرز

في المعلوماتية أو الرياضيات، خوارزمية الفرز^[1] (الإنجليزية: Sort Algorithm) هي خوارزمية تمكن من تنظيم مجموعة عناصر حسب ترتيب محدد. العناصر المراد ترتيبها توجد في مجموعة مزودة بعلاقة ترتيب.

التصنيفات

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

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

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

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

الفرز ذو التعقيد $n l o g (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)$ في الحالات المتوسطة، لكن رباعي في الحالات الصعبة.

مراجع

↑ معجم مصطلحات المعلوماتية (بالعربية والإنجليزية)، دمشق: الجمعية العلمية السورية للمعلوماتية، 2000، ص. 499، OCLC:47938198، QID:Q108408025
↑ Nilsson، Stefan (2000). "The Fastest Sorting Algorithm?". Dr Dobbs. مؤرشف من الأصل في 2019-06-08.
↑ Tim Peters's original description of timsort نسخة محفوظة 22 يناير 2018 على موقع واي باك مشين
↑ Lohr، Steve (17 ديسمبر 2001). "Frances E. Holberton, 84, Early Computer Programmer". NYTimes. مؤرشف من الأصل في 2018-01-18. اطلع عليه بتاريخ 2014-12-16.

هذه بذرة مقالة عن الرياضيات أو موضوع متعلق بها بحاجة للتوسيع. فضلًا شارك في تحريرها.

[1] معجم مصطلحات المعلوماتية (بالعربية والإنجليزية)، دمشق: الجمعية العلمية السورية للمعلوماتية، 2000، ص. 499، OCLC:47938198، QID:Q108408025

[2] Nilsson، Stefan (2000). "The Fastest Sorting Algorithm?". Dr Dobbs. مؤرشف من الأصل في 2019-06-08.

[3] Tim Peters's original description of timsort نسخة محفوظة 22 يناير 2018 على موقع واي باك مشين

[4] Lohr، Steve (17 ديسمبر 2001). "Frances E. Holberton, 84, Early Computer Programmer". NYTimes. مؤرشف من الأصل في 2018-01-18. اطلع عليه بتاريخ 2014-12-16.

[1]

[2]

[3]

[4]

ع ن ت خوارزميات الفرز
الجانب النظري	نظرية التعقيد الحسابي تمثيل O الكبرى ترتيب كلي قائمة (نوع بيانات مجرد) خوازمية موضعية خوارزمية فرز فرز بالمقارنة فرز تكيفي ^{[الإنجليزية]} شبكة فرز ^{[الإنجليزية]} فرز الأعداد الصحيحة ^{[الإنجليزية]} X + Y sorting فرز كمومي ^{[الإنجليزية]}
الفرز بالتبديل	فرز فقاعي Cocktail shaker sort فرز فردي وزوجي ^{[الإنجليزية]} فرز مشطي Gnome sort فرز سريع Stooge sort فرز غبي
الفرز بالإدراج	فرز بالإدراج خوارزمية شل للترتيب ^{[لغات أخرى]}‏ Splaysort فرز شجري ^{[الإنجليزية]} Library sort Patience sorting
الفرز بالمرج	فرز بالمرج Cascade merge sort Oscillating merge sort Polyphase merge sort
الفرز بالتوزيع	American flag sort Bead sort فرز بالدلاء Burstsort الفرز العدي Interpolation sort Pigeonhole sort Proxmap sort فرز بالأساس Flashsort
الفرز التفرعي	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
فرز هجين ^{[الإنجليزية]}	Block merge sort ^{[لغات أخرى]}‏ Kirkpatrick-Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
أخرى	فرز طوبولوجي Pre-topological order Pancake sorting Spaghetti sort
بوابة خوارزميات