Algorithms/Sorting Algorithms

خوارزميات الترتيب Sorting Algorithms هي خوارزميات تستخدم لإعادة ترتيب مصفوفة معطاة أو قائمة من العناصر بالاعتماد على عامل مقارنة معيّن. يُستخدم عامل المقارنة لتحديد ترتيب العناصر الجديد في بنية المعطيات المراد إعادة ترتيب عناصرها.

مصطلحات عملية الترتيب

الترتيب في نفس المكان

لا تستخدم خوارزمية الترتيب في نفس المكان in-place sorting مساحة إضافية ثابتة لإنتاج المخرجات (وذلك بتعديل المصفوفة المعطاة فقط)، وترتّب العناصر في هذه الطريقة بتعديل ترتيب العناصر في المصفوفة فقط، ومن الخوارزميات التي تعتمد هذه الطريقة خوارزميتا الترتيب بالإدراج Insertion Sort والترتيب بالتحديد Selection Sort وذلك لأنّها لا تستخدم أيّ مساحة إضافية لترتيب عناصر القائمة.

الترتيب الداخلي والترتيب الخارجي

عندما لا يكون بالإمكان وضع جميع البيانات التي تحتاج إلى ترتيب في الذاكرة، فإنّ عملية الترتيب تسمّى حينئذٍ بالترتيب الخارجي external sorting، وتستخدم هذه العملية مع الكميات الكبيرة جدًّا من البيانات.

تستخدم خوارزمية الترتيب بالدمج Merge Sort بأنواعها المختلفة في هذا النوع من عمليات الترتيب، ويمكن الاستفادة من مصادر تخزين خارجية مثل الأقراص الصلبة أو الأقراص المضغوطة لتخزين البيانات.

تكون عملية الترتيب داخلية Internal Sorting إن كان بالإمكان وضع البيانات التي تحتاج إلى ترتيب في الذاكرة.

الترتيب بالفقاعات

خوارزمية الترتيب بالفقاعات Bubble Sort هي أبسط خوارزميات الترتيب والتي تعمل على تبديل مواقع العناصر المتجاورة إن كان ترتيبها خاطئًا.

الترتيب بالتحديد

ترتّب خوارزمية الترتيب بالتحديد selection sort المصفوفة عن طريق العثور على أصغر عنصر (بافتراض أنّ الترتيب سيكون ترتيبًا تصاعديًا) في الجزء غير المرتّب من المصفوفة ووضعه في بدايتها.

الترتيب بالإدراج

الترتيب بالإدراج Insertion Sort من خوارزميات الترتيب البسيطة التي تعمل بنفس الطريقة التي ترتّب فيها أوراق اللعب يدويًا.

الترتيب بالدمج

تقسم خوارزمية الترتيب بالدمج Merge Sort المصفوفة المدخلة إلى نصفين، ثم تستدعي الخوارزمية نفسها على هذين النصفين ثم تدمج نصفي المصفوفة المرتبين بعضهما ببعض.

الترتيب السريع

تنتقي عنصرًا من عناصر المصفوفة وتجعله محورًا pivot ثمّ تقسّم المصفوفة المعطاة حول ذلك العنصر.

الترتيب بالكومة

تستند خوارزمية الترتيب بالكومة Heap Sort على الكومة الثنائية Binary Heap، وهي مشابهة لخوارزمية الترتيب بالتحديد Selection Sort إذ نختار في البداية العنصر الأكبر في المصفوفة ونضعه في نهاية المصفوفة، وتعاد العملية على بقية العناصر.

الترتيب بالعد

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

الترتيب بالجذر

تتلخص هذه الخوارزمية بإجراء ترتيب للعناصر رقمًا تلو الآخر بدءًا من الرقم الأقل أهمية إلى الرقم الأكثر أهمية.

خوارزمية شِل للترتيب

ترتب خوارزمية شِل المصفوفة بالنسبة لقيمة كبيرة من h ، ثم تستمر في تقليص قيمة h إلى حين الوصول إلى 1.