WEEK 3 • خوارزميات الترتيب

QuickSort

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

إيه هو QuickSort؟

⚡ الفكرة الأساسية

📖 تشبيه توزيع الورق

تخيل عندك ورق كوتشينة وعايز ترتبه:

  1. اختار ورقة واحدة تكون "Pivot" (المحور)
  2. وزع باقي الورق: اللي أصغر على الشمال، واللي أكبر على اليمين
  3. الـ Pivot دلوقتي في مكانه الصح!
  4. كرر نفس الخطوات للشمال واليمين

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

🎯
1. اختار Pivot

عادة آخر عنصر أو عشوائي

↔️
2. Partition

رتب حوالين الـ Pivot

🔁
3. Recurse

كرر للشمال واليمين

⚡ التعقيد

Average Case

O(n log n)

لما الـ Pivot بيقسم بالتساوي

Worst Case

O(n²)

لما الـ array مترتبة و Pivot سيء

Partition بالتفصيل

الخطوة الأهم في QuickSort

مثال: ترتيب [8, 3, 7, 1, 5, 9, 2]
Pivot = 2 (آخر عنصر)

Initial
8
3
7
1
5
9
2

الـ Pivot = 2 (آخر عنصر)

Partitioning...
1
3
7
8
5
9
2

1 أصغر من 2، نحركه للشمال

After Partition
←أصغر
1
2
3
7
8
5
9
أكبر→

🎯 الـ Pivot (2) في مكانه الصح الآن!

💡 الفكرة:

بعد الـ Partition:
• الـ Pivot في مكانه النهائي
• كل اللي على شماله أصغر منه
• كل اللي على يمينه أكبر منه

INTERACTIVE

QuickSort Demo

Pivot
Comparing
Swapping
Sorted

Click "Sort" to start.

Implementation

quickSort.js 
function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return;
  
  const pivotIdx = partition(arr, lo, hi);
  quickSort(arr, lo, pivotIdx - 1);
  quickSort(arr, pivotIdx + 1, hi);
}

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo - 1;
  
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  return i + 1;
}

شرح الكود 📖

سطر 2: Base Case - لو عنصر واحد أو أقل، خلاص
سطر 4: عمل partition وجيب index الـ pivot
سطر 5-6: كرر للجزء الشمال واليمين
partition(): الـ pivot = آخر عنصر، نحرك الأصغر للشمال
سطر 19: في الآخر نحط الـ pivot في مكانه

QuickSort vs MergeSort

QuickSort MergeSort
Average Time O(n log n) O(n log n)
Worst Time O(n²) O(n log n)
Space O(log n) O(n)
In-place? ✓ Yes ✗ No
Stable? ✗ No ✓ Yes