ما هي خوارزميات الفرز والترتيب ( Sorting Algorithms ) وما هي ابرز انواعها ؟

هنالكَ انواع عديدة من خوارزميات الفرز و الترتيب. بشكل عام, تختلف أليه عمل خوارزميات الفرز من واحده لآخره على حسب نوع الغرض والتقنية المستخدمة.  في هذهِ المقالة سنتحدث عن الـ كيفية التي تعمل بها خوارزميات الترتيب. وبشكل عام فأن المهمه الاساسية للـ Sorting Algorithms  هي ترتيب العناصر بشكل معين, كترتيب العناصر بالشكل التصاعدي او التنازلي.

أشهر خوارزميات الفرز (Sorting Algorithms)

• Selection Sort :- تعمل هذهِ الخوارزمية على فكرة إيجاد العنصر الأصغر أو الاكبر من بين مجموعة العناصر الغير مرتبة الموجودة في المصفوفة ومن ثم وضعه في الموقع المناسب ضمن المصفوفة. هذهِ الخوارزمية قائمة على اساس المقارنه ( Comparison ).

• Bubble Sort :- تعمل هذهِ الخوارزمية على فكرة المقارنة المتكررة بين الازواج المتجاورة من العناصر, وتبديل مواقع هذهِ العناصر أن كانوا في ترتيبِ خاطئ.

• Insertion Sort :-  تعمل هذهِ الخوارزمية على فكرة ( الادخال ) في ترتيب عناصرها. فرضاً لنعتبر أن لدينا مصفوفتان : الاصلية المراد ترتيبها و المرتبه مسبقاً, حيث أن المصفوفة المرتبه تكون فارغة في البداية, نقوم بترتيب العناصر في المصفوفة الاصلية كما في المصفوفة المرتبة عن طريق اضافة كل عنصر من عناصر المصفوفة الاصلية في موقعه الصحيح في المصفوفة المرتبة.  اكثر الامثلة انتشاراً لتوضيح أليه عمل هذهِ الخوارزمية هي كيفية ترتيب اوراق اللعب

• Quick Sort :- أن خوارزمية الـQuick Sort تعمل بمبدأ الـ (Divide and Conquer). تتلخص فكرة هذا المبدأ في  تقسيم المشكلة المراد حلها إلى عدة مشاكل أصغر في الحجم (نقصد بالكبر و الصغر هنا عدد العناصر التي يتم معالجتها) ومماثلة للمشكلة الكبيرة من حيث المبدأ (عادة ما تكون المشكلات الصغيرة مستقلة عن بعضها ), وبعد حل كل مشكلة صغيرة على حدة. تأتي مرحلة تجميع الأجزاء المحلولة بحيث تكون معا حل للمشكلة الكاملة. وهكذا فإن المراحل الأساسية التي تمر بها كل خوارزمية هي :-
  – مرحلة التفريق أو التقسيم (The Divide Step) وفي هذا المرحلة يتم تحديد حجم المشاكل الصغيرة والتي إليها تنقسم المشكلة الكبيرة.
  – مرحلة السيادة (The Conquer Step) وهنا يتم حل المشاكل الصغيرة, كل على حدة.
  – مرحلة التجميع (The Combine Step ) وهنا يتم تجميع حلول المشاكل الصغيرة والتي تكون معا حل المشكلة الأصلية.

بعد توضيح مبدأ عمل الـ (Divide and Conquer) , لنوضح كيفية عمل خوارزمية الـ Quick Sort

اولاً : Pivot Selection : أختيار عنصر من المصفوفة ويدعى هذا العنصر المختار بأسم الـ Pivot . عادة, يكون هذا العنصر في النهاية اليسرى او اليمنى من المصفوفة.

ثانياً : Partitioning : بعد الخطوة الاولى, تبدأ الخطوة الثانية المتمثلة بترتيب عناصر المصفوفة بحيث أن كل العناصر التي تكون أصغر من الـ Pivot المختار يتم ترتيبها قبله والاكبر توضع بعده. ويتم تكرار الخطوتين في كل مصفوفة جديدة كما موضح في المثال المذكور.

• Merge Sort :- تعمل هذهِ الخوارزمية على فكرة تقسيم القائمة او المصفوفة الرئيسية الى قوائم فرعية تحوي كل منها عنصر وحيد, ومن ثم دمج هذهِ القوائم الفرعية بشكل ترتيبي من الاكبر الى الاصغر او العكس لتنتج مصفوفة مرتبه. كالمثال ادناه

• Heap Sort :- تعمل هذهِ الخوارزمية على أساس مرحلتين ,في البداية يتم صنع او خلق Heap للقوائم او المصفوفات الغير مفرزة ثم يتم انشاء القوائم المفرزة من خلال حذف العناصر الاكبر او الاصغر من الذاكرة بشكل متكرر, وادراجها للمصفوفة الجديدة.

• Tree Sort :- تعتمد هذهِ الخوارزمية في عملها على فكرة “شجرة البحث الثنائية” في هيكلة البيانات. حيث في البداية يتم انشاء “شجرة بحث ثنائية” من خلال العناصر المدخلة في المصفوفة او القائمة. بعد ذلك يتم تطبيق عملية ” In-order traversal ” على الشجرة المكونة للترتيب العناصر بشكل جيد