خوارزمية فرز
بدايةً، في المعلوماتية أو الرياضيات، خوارزمية الفرز هي خوارزمية تمكن من تنظيم مجموعة عناصر حسب ترتيب محدد. العناصر المراد ترتيبها توجد في مجموعة مزودة بعلاقة ترتيب. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
التصنيفات
من جهة ثانية، تصنيف خوارزميات الفرز مهم جدا، لأنه يمكن من اختيار نوع الخوارزمية الأكثر تناسبا للمشكل المعالج، مع الأخذ بعين الاعتبار السلبيات الموجودة في الخوارزمية.
تعقيد الخوارزمية
الفرز ذو التعقيد في المتوسط يعد جيدًا.
في أغلب الحالات ، وبالنسبة للبعض .
من جهة ثانية، تعقيد الخوارزمية الزمني في الحالات الأكثر تعقيدا يمكن من تحديد الحد الأقصى لعدد العمليات التي يجب استعمالها لترتيب عناصر مجموعة مكونة من n عنصر. نستعمل لترميز هذا التعقيد لاندو: O.
كذلك، تعقيد الخوارزمية المكاني قي الحالات الأكثر تعقيدا أو الحالات المتوسطة تمثل كمية الذاكرة المستعملة في خوارزمية الفرز. وهي كذلك مرتبطة بعدد عناصر المجموعة.
إضافةً إلى ذلك، تعقيد الخوارزمية الزمني في الحالة المتوسطة تمكن من مقارنة خوارزميات الفرز وإعطاء فكرة عن الوقت اللازم لتنفيذ الخوارزمية.
مميزات المكان
في هذا الإطار، نقول أن خوارزمية مكانية إذا لم تستعمل سوى عدد محدد من المتغيرات وتُغير مباشرة المجموعة المراد ترتيبها. هذا يتطلب استعمال بنية للمعطيات مثلا جدول.
مميز الثبات
- (3, 1) (3, 7) (4, 1) (5, 6) (ترتيب نسبي محترم)
- (3, 7) (3, 1) (4, 1) (5, 6) (ترتيب نسبي متغير)
- أمثلة وتقنيات الفرز
- ترتيب الفقاعات: خوارزمية رباعية,
- ترتيب الاختيار: خوارزمية رباعية,
ومن جهة أخرى، الذي نرتبها حسب الاحداثية الأولى (المفتاح) نجد حالتين، عندما يتم احترام الفرز النسبي وعندما لا يحترم:
وفي هذا السياق، تكون الخوارزمية ثابتة إذا كان يحافظ على الفرز النسبي للكميات المتساوية بالنسبة لعلاقة الفرز.
مثال، بالنسبة للعناصر الآتية:
(4, 1) (3, 1) (3, 7) (5, 6)
ترتيب بالإدراج: خوارزمية رباعية,
من جهة ثانية، ترتيب سريع: في الحالات المتوسطة، لكن رباعي في الحالات الصعبة.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟