ماذا يعني sort في الخوارزميات وهياكل البيانات؟ شرح مبسّط مع مقارنة الخوارزميات
كلمة sort في مجال الخوارزميات وهياكل البيانات تعني ببساطة إعادة ترتيب مجموعة من العناصر وفق معيار محدد: تصاعديًا من الأصغر إلى الأكبر، أو تنازليًا، أو أبجديًا، أو حسب أي مفتاح تختاره (تاريخ، سعر، أولوية). لكن أهمية الترتيب لا تكمن في المخرجات الجميلة فحسب، بل في أنه يجعل بقية العمليات — وعلى رأسها البحث — أسرع بمراحل. هذا هو الجوهر الذي يجب أن تفهمه قبل أي شيء آخر.
لماذا نرتّب البيانات أصلًا؟
تخيّل قائمة هاتف غير مرتبة تحتوي على مليون اسم. للعثور على اسم واحد قد تضطر لقراءة القائمة كاملة، أي مليون خطوة في أسوأ الحالات. لكن إذا كانت القائمة مرتبة أبجديًا، يمكنك استخدام البحث الثنائي (Binary Search) الذي يقسّم القائمة نصفين في كل خطوة، فتصل إلى الاسم في نحو 20 خطوة فقط لمليون عنصر.
هذا الفرق — من مليون خطوة إلى عشرين — هو السبب الحقيقي وراء أهمية الترتيب. كثير من الخوارزميات المتقدمة (إزالة التكرار، إيجاد الوسيط، دمج مجموعتين، اكتشاف التقارب بين العناصر) تفترض مسبقًا أن البيانات مرتبة، لأن الترتيب يحوّل مسائل صعبة إلى مسائل سهلة.
كيف نقيس جودة خوارزمية الترتيب؟
قبل أن نقارن الخوارزميات، تحتاج ثلاثة مقاييس أساسية:
- تعقيد الوقت (Time Complexity): كم عملية تحتاجها الخوارزمية مع نمو عدد العناصر
n؟ يُكتب بصيغة Big O مثل O(n²) أو O(n log n). الأصغر أفضل. - الاستقرار (Stability): الخوارزمية «المستقرة» تحافظ على الترتيب النسبي للعناصر المتساوية. مهم جدًا عند الترتيب حسب أكثر من مفتاح (مثلًا ترتيب حسب الاسم ثم حسب المدينة).
- استهلاك الذاكرة (Space): هل تحتاج الخوارزمية مساحة إضافية بحجم البيانات، أم تعمل «في المكان» (in-place) بذاكرة ثابتة؟
أشهر خوارزميات الترتيب
Bubble Sort (الفقاعة): تقارن كل عنصرين متجاورين وتبدّلهما إذا كانا في ترتيب خاطئ، وتكرر ذلك. أبسط خوارزمية للفهم، لكنها من أبطأ الخيارات عمليًا. تصلح للتعليم لا للإنتاج.
Selection Sort (الاختيار): تبحث في كل جولة عن أصغر عنصر متبقٍّ وتضعه في مكانه. عدد التبديلات قليل، لكن عدد المقارنات كبير دائمًا.
Insertion Sort (الإدراج): تبني القائمة المرتبة عنصرًا عنصرًا، مثل ترتيب أوراق اللعب في يدك. بطيئة مع البيانات الكبيرة، لكنها سريعة جدًا مع القوائم الصغيرة أو شبه المرتبة، ولهذا تُستخدم داخل خوارزميات أكبر.
Merge Sort (الدمج): تقسّم البيانات نصفين، ترتّب كل نصف، ثم تدمجهما. أداؤها ثابت وممتاز O(n log n) في كل الحالات، ومستقرة، لكنها تحتاج ذاكرة إضافية بحجم البيانات.
Quick Sort (السريعة): تختار عنصرًا «محوريًا» وتقسّم البيانات حوله ثم تكرّر. سريعة جدًا في الممارسة العملية وتعمل في المكان، لكنها قد تتدهور إلى O(n²) مع اختيار محور سيئ، وهي غير مستقرة.
Heap Sort (الكومة): تستخدم بنية «الكومة» لسحب أكبر عنصر تِباعًا. مضمونة O(n log n) وتعمل بذاكرة ثابتة، لكنها غير مستقرة وأبطأ قليلًا من Quick Sort عمليًا.
جدول مقارنة سريع
| الخوارزمية | متوسط الوقت | أسوأ حالة | الذاكرة | مستقرة؟ |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) | نعم |
| Selection Sort | O(n²) | O(n²) | O(1) | لا |
| Insertion Sort | O(n²) | O(n²) | O(1) | نعم |
| Merge Sort | O(n log n) | O(n log n) | O(n) | نعم |
| Quick Sort | O(n log n) | O(n²) | O(log n) | لا |
| Heap Sort | O(n log n) | O(n log n) | O(1) | لا |
ملاحظة: Insertion وBubble تصلان إلى O(n) في أفضل حالة عندما تكون البيانات مرتبة مسبقًا تقريبًا.
كيف تختار الخوارزمية المناسبة؟
- بيانات كبيرة وتريد أداءً ثابتًا مضمونًا: Merge Sort أو Heap Sort.
- بيانات كبيرة والسرعة العملية أهم من الضمان النظري: Quick Sort.
- قوائم صغيرة أو شبه مرتبة: Insertion Sort.
- تحتاج الحفاظ على ترتيب العناصر المتساوية: اختر خوارزمية مستقرة (Merge أو Insertion).
نصيحة عملية: لا تعِد اختراع العجلة
الخطأ الأكثر شيوعًا بين المبتدئين هو كتابة خوارزمية ترتيب يدوية داخل مشروع حقيقي. في الواقع، كل لغة برمجة حديثة تأتي بدالة ترتيب مُحسَّنة وهجينة جاهزة:
- بايثون تستخدم
sorted()أو.sort()وتعتمد داخليًا على Timsort (مزيج من Merge وInsertion، مستقرة وسريعة جدًا مع البيانات الواقعية). - جافا تستخدم Timsort للكائنات وإصدارًا من Quick Sort للأعداد الأولية.
- C++ توفّر
std::sortالمبنية على Introsort (Quick Sort مع تحوّل تلقائي إلى Heap Sort لتجنّب الحالة الأسوأ).
هذه الدوال أسرع وأكثر اختبارًا من أي كود تكتبه بنفسك. تعلَّم الخوارزميات لتفهم لماذا تعمل ولتنجح في المقابلات التقنية، لكن استخدم الدالة الجاهزة في الإنتاج.
الأسئلة الشائعة
ما أسرع خوارزمية ترتيب؟ لا توجد «أسرع» مطلقة. من حيث التعقيد النظري، الحد الأدنى للترتيب القائم على المقارنة هو O(n log n)، وتحققه Merge وHeap وQuick (في المتوسط). في الممارسة العملية، Quick Sort والدوال الهجينة مثل Timsort تتفوق غالبًا على بيانات الواقع.
هل يمكن الترتيب أسرع من O(n log n)؟ نعم، لكن ليس عبر المقارنة. خوارزميات مثل Counting Sort وRadix Sort تصل إلى O(n) لأنها لا تقارن العناصر ببعضها، بل تعتمد على خصائص المفاتيح (مثل كونها أعدادًا صحيحة ضمن مدى محدود).
ما الفرق بين الخوارزمية المستقرة وغير المستقرة؟ المستقرة تُبقي العناصر المتساوية بترتيبها الأصلي. هذا حاسم عند الترتيب المتعدد المستويات؛ فلو رتّبت جدولًا حسب التاريخ ثم حسب الاسم بخوارزمية مستقرة، يبقى ترتيب التاريخ محفوظًا داخل كل اسم.
هل أحتاج حفظ هذه الخوارزميات عن ظهر قلب؟ لا تحفظ الكود، بل افهم الفكرة والمقايضات: متى تكون كل خوارزمية أفضل، وما تعقيدها، ولماذا تُستخدم الدوال الجاهزة. هذا الفهم هو ما يميّزك في العمل والمقابلات معًا.