الكويك سورت (Quick Sort)

مفاهيم أساسية

• فكرة الكويك سورت:
  • تقسيم المصفوفة إلى مصفوفتين غير متساويتين.
  • الجزء الأول يحتوي على العناصر التي ستكون أقل أو تساوي العناصر في الجزء الثاني بعد الترتيب.
  • الجزء الثاني يحتوي على العناصر التي ستكون أكبر من العناصر في الجزء الأول بعد الترتيب.
  • يتم تقسيم المصفوفة باستخدام عنصر محوري (Pivot).

خطوات الخوارزمية

1. مرحلة التقسيم (Divide):

   • تقسيم المصفوفة إلى جزئين باستخدام عنصر محوري.
   • جميع العناصر في الجزء الأول أقل أو تساوي العنصر المحوري، والعناصر في الجزء الثاني أكبر.

2. مرحلة الحل الجزئي (Conquer):

   • يتم تطبيق خوارزمية الكويك سورت بشكل عودي على كل جزء من الأجزاء المقسمة.

3. مرحلة التجميع (Combine):

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

السودوكود (Pseudo Code)

• نحدد متغيرين (I و J)
• J تبدأ من خارج المصفوفة و I تبدأ من أول عنصر
• نمر على المصفوفة من اليسار لليمين ومن اليمين لليسار ونقوم بالتبديلات لتحقيق الترتيب
• عند انتهاء التبديلات، نقسم المصفوفة إلى جزئين عند الموضع الذي وصلنا إليه

التطبيق العودي (Recursive Implementation)

• نتحقق من حالة التوقف (Base Case) عند مصفوفة تحتوي على عنصر واحد فقط.
• نقوم بتطبيق الخوارزمية على المصوفة من P إلى R:
  • إذا P = R، فإن المصفوفة تحتوي على عنصر واحد فقط
  • إذا P < R، نقوم بالتقسيم وإعادة تطبيق خوارزمية الكويك سورت على الأجزاء الناتجة

اختيار العنصر المحوري (Pivot)

• يمكن أن يكون أول أو آخر أو أي عنصر في المصفوفة
• نقوم بالمرور على العناصر وتقسيمها حول العنصر المحوري
• جميع العناصر الأصغر أو تساوي المحوري تكون في الجزء الأيسر، والعناصر الأكبر أو تساوي المحوري تكون في الجزء الأيمن

خطوات التقسيم

• نبدأ باختيار قيمة العنصر المحوري الموجود في المصفوفة
• نحرك المتغير I من اليسار إلى اليمين حتى نجد عنصرًا أكبر من المحوري
• نحرك المتغير J من اليمين إلى اليسار حتى نجد عنصرًا أصغر من المحوري
• نقوم بتبديل العناصر بين I و J
• نكرر العملية حتى يتوقف I و J

التحليل الزمني

• أفضل حالة: O(n log n) عندما يكون التقسيم متساويًا.
• متوسط الحالة: O(n log n) بشكل عام.
• أسوأ حالة: O(n^2) عندما يكون القسم غير متوازن كليًا.

استعراض بياني

• نقسم المصفوفة بصريًا ونرى كيف يتم تقسيم إلى مراحل أصغر حتى نحصل على مصفوفات تحتوي على عناصر قليلة يمكن فرزها مباشرة.

خاتمة

• الكويك سورت هو مثال على خوارزمية التجزئة ثم الحل.
• يتطلب اختيارًا جيدًا لعنصر المحوري لضمان أداء جيد.