خوارزمية الترتيب بتعمل إيه؟
الفكرة الأساسية
تعيد ترتيب العناصر وفق قاعدة مقارنة محددة. قبل الاختيار، حدد مفتاح الفرز والاتجاه والتعامل مع القيم المتساوية. ترتيب أرقام تصاعديًا أبسط من ترتيب سجلات لها عدة مفاتيح.
مثلًا، قد ترتب مهام حسب موعدها وتريد الاحتفاظ بترتيب الوصول بين المهام ذات الموعد نفسه. هذا شرط إضافي له معنى.
تتبع فرز الإدراج
ابدأ بالقيم 8 و3 و5. اعتبر أول عنصر جزءًا مرتبًا. أدخل 3 قبله فتصبح 3 و8 و5، ثم أدخل 5 بين 3 و8 فتصبح 3 و5 و8.
| المرحلة | الجزء المرتب | المتبقي |
|---|---|---|
| البداية | 8 | 3، 5 |
| إدخال 3 | 3، 8 | 5 |
| إدخال 5 | 3، 5، 8 | لا شيء |
الخاصية التي تتابعها هي أن الجزء المعالج مرتب. كل إدخال يمد هذه الخاصية إلى عنصر إضافي.
معنى ثبات الترتيب
الفرز الثابت يحافظ على الترتيب النسبي للعناصر المتساوية في المقارنة. لو للمهمتين أ وب نفس الموعد وكانت أ أولًا، يظل هذا الترتيب بعد فرز ثابت حسب الموعد.
الثبات لا يعني «يعمل دائمًا». قد يكون فرز غير ثابت صحيحًا تمامًا عندما لا يهم ترتيب العناصر المتساوية.
قارن الخصائص المعتادة
| الطريقة | الزمن في أسوأ حالة عادة | ملاحظة |
|---|---|---|
| الإدراج | O(n squared) | قد يناسب الأحجام الصغيرة أو شبه المرتبة |
| الدمج القياسي | O(n log n) | التنفيذ المعتاد للمصفوفات يحتاج مساحة إضافية |
| الكومة | O(n log n) | التنفيذ المعتاد داخل المكان غير ثابت |
| صور أساسية من الفرز السريع | O(n squared) | اختيار المحور مؤثر والأداء المتوقع قد يكون أفضل |
تفاصيل التنفيذ مهمة. لا تنسب كل خصائص نسخة دراسية إلى أي دالة مكتبة تحمل اسمًا قريبًا.
راجع قاعدة المقارنة
عند تساوي المفتاح الأول، هل تحافظ على ترتيب الإدخال أم تستخدم مفتاحًا ثانيًا؟ يجب أن تكون المقارنة متسقة؛ القاعدة المتناقضة قد تفسد افتراضات طريقة الفرز.
وفي النصوص، الترتيب البسيط حسب تمثيل الحروف مختلف عن الترتيب اللغوي المناسب. حدد المطلوب قبل الحكم على الناتج.
اختبارات أساسية
جرّب بيانات مرتبة أصلًا وعكسية ومكررة، وعنصرًا واحدًا ومجموعة فارغة. وفي السجلات، راقب ترتيب المفاتيح المتساوية عند اشتراط الثبات.
افحص أن الناتج مرتب وأنه احتفظ بكل العناصر وعدد مرات تكرارها. قائمة مرتبة فقدت عنصرًا مكررًا ليست إجابة صحيحة.
تأتي الخوارزميات بعد هياكل البيانات في جمال تك. قارن الطريقة بشروطها وطبيعة استخدامها، لا بعدد أسطر كودها فقط.
مراجع وتفاصيل الكورسات
المراجع التالية تساعد على متابعة التعلم. الأمثلة والتمارين في هذا المقال تعليمية، وتفاصيل الكورسات تُراجع من الكتالوج.