ما هو خوارزمية الفرز السريع (Quick Sort)؟
يعتبر Quick Sort من بين أكثر الخوارزميات كفاءة في فرز البيانات، وهو يعتمد على مبدأ “التقسيم والغزو” (Divide and Conquer). تعمل هذه الخوارزمية عن طريق اختيار عنصر يسمى “المحور” (Pivot) ومن ثم تقسيم العناصر إلى مجموعتين: الأولى تضم العناصر الأقل من المحور، والثانية تضم العناصر الأكبر من المحور. بعد ذلك، يتم تطبيق نفس العملية على كل مجموعة بشكل متكرر حتى يتم فرز جميع العناصر.
تتميز Quick Sort بكفاءتها العالية في الأداء، حيث يمكنها فرز القوائم بوقت يتناسب بشكل لوغاريتمي مع عدد العناصر، مما يجعلها مناسبة للتعامل مع مجموعات بيانات كبيرة. كما أنها لا تتطلب مساحة إضافية كبيرة، حيث يتم الفرز في مكانه (in-place).
تطبيق Quick Sort في بايثون
تطبيق Quick Sort في بايثون بسيط ومباشر، حيث يمكن تعريف دالة تقوم بعملية الفرز باستخدام هذه الخوارزمية. فيما يلي مثال يوضح كيفية تطبيق Quick Sort في بايثون:
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
less_than_pivot = [x for x in arr[1:] if x <= pivot]
greater_than_pivot = [x for x in arr[1:] if x > pivot]
return quick_sort(less_than_pivot) + [pivot] + quick_sort(greater_than_pivot)
# مثال على استخدام Quick Sort
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("المصفوفة بعد الفرز:", sorted_arr)
في هذا المثال، قمنا بتعريف دالة `quick_sort` التي تأخذ قائمة كمدخل. إذا كان طول القائمة أقل من أو يساوي واحد، فإنها تعيد القائمة كما هي لأنها بالفعل مرتبة. خلاف ذلك، يتم اختيار العنصر الأول كمحور، ويتم تقسيم العناصر الأخرى إلى قائمتين بناءً على ما إذا كانت أقل أو أكبر من المحور. يتم استدعاء الدالة بشكل متكرر على القائمتين، ثم يتم دمج النتائج للحصول على القائمة المرتبة النهائية.
مزايا وعيوب Quick Sort
تتميز Quick Sort بعدة مزايا، منها سرعتها العالية في معظم الحالات، وعدم حاجتها لمساحة تخزين إضافية كبيرة، مما يجعلها مثالية للعديد من التطبيقات. ومع ذلك، هناك بعض العيوب مثل الأداء السيء في أسوأ الحالات عندما تكون البيانات مرتبة بالفعل أو عندما يتم اختيار المحور بشكل سيء، مما يؤدي إلى وقت تنفيذ يتناسب تربيعيًا مع عدد العناصر.
للتغلب على مشكلات الأداء في أسوأ الحالات، يمكن تحسين اختيار المحور باستخدام تقنيات مثل اختيار المحور عشوائيًا أو استخدام “الوسيط الثلاثي” (Median of Three) لزيادة احتمالية الأداء الجيد. بشكل عام، تظل Quick Sort واحدة من أكثر خوارزميات الفرز شهرة واستخدامًا في البرمجة والتطبيقات الحياتية.