📦 أكثر مسألة شيوعًا في المعلوميات
لديك لائحة من الأعداد غير مرتبة. تريد ترتيبها من الأصغر إلى الأكبر. سهل، أليس كذلك؟ يدويًا، بعشر بطاقات، نعم. لكن الحاسوب يجب أن يتبع وصفة دقيقة — خوارزمية — والوصفة التي يختارها تغير كل شيء تمامًا عندما لا تحتوي اللائحة على عشرة أعداد، بل على مليون.
الترتيب هو بلا شك العملية الأكثر تنفيذًا في العالم: تصنيف نتائج البحث، ترتيب الرسائل الإلكترونية حسب التاريخ، عرض تصنيف، تجهيز المعطيات قبل البحث فيها… أن تفهم كيف نرتب، يعني أن تفهم القلب النابض للخوارزميات.
🎬 خوارزميات الترتيب أثناء العمل
شغّل ترتيبًا وشاهد الأعمدة ترتب نفسها خطوة بخطوة. الأصفر = قيد المقارنة، الأخضر = مرتب بالفعل.
المقارنات
0
التبديلات
0
اختر خوارزمية لتشغيل الترتيب.
🫧 أنواع الترتيب الثلاثة «البسيطة»
قبل الخوارزميات الذكية، هناك الخوارزميات البديهية: تلك التي نخترعها تلقائيًا. سهلة الفهم، سهلة البرمجة… وبطيئة. إليك الثلاثة الكلاسيكية الكبرى.
الترتيب بالفقاعات (bubble sort). نمر على اللائحة، وكلما كان عنصران متجاوران في الترتيب الخاطئ، نقوم بتبديلهما. القيم الكبيرة «تطفو» مثل الفقاعات نحو النهاية. نعيد العملية إلى أن لا يبقى أي تبديل ضروري. بسيط، لكنه يبدّل كثيرًا جدًا.
الترتيب بالاختيار (selection sort). نبحث عن أصغر عنصر في اللائحة بأكملها ونضعه في الموضع الأول. ثم أصغر عنصر من الباقي، في الموضع الثاني. وهكذا دواليك. يقوم بمقارنات كثيرة لكن بتبديلات قليلة جدًا (تبديل واحد في كل دورة).
الترتيب بالإدراج (insertion sort). هذه بالضبط الطريقة التي نرتب بها البطاقات في أيدينا: نأخذ كل بطاقة جديدة وندرجها في مكانها الصحيح بين البطاقات المرتبة بالفعل. فعال جدًا على اللوائح شبه المرتبة — وهو في الواقع غالبًا الترتيب المستخدم عمليًا على الجداول الصغيرة.
⏱️ الفكرة الكبرى: التعقيد
ما يميز هذه الخوارزميات ليس ما إذا كانت ترتب — فكلها ترتب بشكل صحيح — بل عدد العمليات التي تحتاجها. نقيس ذلك بواسطة التعقيد، المرمّز بحرف O الكبير: يصف كيف يَكبُر عدد العمليات عندما يزداد حجم اللائحة، n.
أنواع الترتيب البسيطة الثلاثة لدينا كلها بتعقيد O(n²): لمضاعفة حجم اللائحة، تستغرق حوالي أربعة أضعاف الوقت. لماذا؟ لأن كل واحدة منها تقارن، تقريبًا، كل عنصر بجميع العناصر الأخرى: n عناصر × n عناصر = n². بالنسبة لـ n = 40 عمودًا في العرض المرئي، فهذا حوالي 1600 عملية. لا بأس. بالنسبة لمليون عنصر…
n = 1 000 000. خوارزمية بتعقيد O(n²) تتطلب حوالي 1 000 000 000 000 (ألف مليار) عملية. حتى بمليار عملية في الثانية، يستغرق ذلك أكثر من 15 دقيقة. بالنسبة لـ 100 مليون عنصر: أشهر من الحساب.
🚀 أنواع الترتيب «الذكية»: O(n log n)
لحسن الحظ، نعرف كيف نفعل ما هو أفضل بكثير. أفضل خوارزميات الترتيب العامة بتعقيد O(n log n) — نمو شبه خطي. نجمتان:
الترتيب بالدمج (merge sort). استراتيجية «فرّق تَسُد»: نقسم اللائحة إلى نصفين، نرتب كل نصف (بشكل تراجعي)، ثم ندمج النصفين المرتبين في واحد. دائمًا O(n log n)، حتى في أسوأ الحالات. اخترعه جون فون نويمان عام 1945.
الترتيب السريع (quicksort). اخترعه توني هور عام 1959، وهو الترتيب الأكثر استخدامًا في العالم. نختار عنصرًا محوريًا، نضع كل ما هو أصغر على اليسار وكل ما هو أكبر على اليمين، ثم نعيد العملية على كل جانب. في المتوسط O(n log n)، بسرعة حقيقية مذهلة.
كم تساوي «log n»؟ بالنسبة لـ n = 1 000 000، تساوي log₂(n) بالكاد 20. إذن n log n ≈ 20 مليون عملية… مقابل ألف مليار بالنسبة لـ O(n²). أي أقل بـ 50 000 مرة.
🌍 لماذا يهم ذلك على نطاق واسع
عندما تصنف Google مليارات الصفحات، عندما يرتب بنك ملايين المعاملات، عندما يرتب هاتفك الصور: اختيار الخوارزمية ليس تفصيلًا نظريًا. إنه الفرق بين تطبيق فوري وتطبيق غير قابل للاستعمال.
🧠 ما يجب تذكره
يبدو الترتيب بديهيًا لأننا نقوم به على نطاق صغير. لكن وراء هذه الحركة العادية يختبئ أحد أعمق دروس المعلوميات: برنامجان يعطيان نفس النتيجة بالضبط يمكن أن يفصل بينهما عامل مقداره مليار.
الفقاعات، الاختيار، الإدراج للفهم؛ الدمج والترتيب السريع للحياة الواقعية. وفوق كل شيء: مفهوم التعقيد، البوصلة التي تقول، قبل حتى كتابة سطر واحد من الشيفرة، ما إذا كانت الخوارزمية ستتحمل الحمولة أم ستنهار.