المقدمة
يعتبر فرز المصفوفة من أولى المشكلات الجادة التي تمت دراستها في المقرر الكلاسيكي "الخوارزميات وهياكل البيانات" في تخصص علوم الكمبيوتر. في هذا الصدد ، غالبًا ما تتم مواجهة مهام فرز الكتابة والأسئلة ذات الصلة في المقابلات الخاصة بمنصب متدرب أو مطور مبتدئ.
صياغة المشكلة
تقليديا ، يجدر البدء في تقديم حلول للمشكلة ببيانها. عادةً ما تتضمن مهمة الفرز ترتيب مجموعة من الأعداد الصحيحة بترتيب تصاعدي. لكن في الواقع ، هذا تبسيط مفرط إلى حد ما. يمكن استخدام الخوارزميات الموضحة في هذا القسم لترتيب مصفوفة من أي كائنات يتم إنشاء علاقة ترتيب بينها (أي بالنسبة لأي عنصرين يمكننا القول: الأول أكبر من الثاني ، والثاني أكبر من الأول ، أو أنهما متساويان). يمكنك الفرز بترتيب تصاعدي وتنازلي. سنستخدم التبسيط القياسي.
فرز سريع
آخر مرة تحدثنا فيها عن نوع أكثر تعقيدًا - نوع الإدراج. اليوم سنتحدث عن خوارزمية أكثر تعقيدًا - فرز سريع (يُسمى أيضًا فرز Hoare).
وصف الخوارزمية
تعد خوارزمية الفرز السريع متكررة ، وبالتالي ، من أجل التبسيط ، سيتخذ الإجراء كمدخل حدود مقطع مصفوفة من l متضمنًا إلى r غير شامل. من الواضح أنه من أجل فرز المصفوفة بأكملها ، يجب تمرير 0 كمعامل l ، و n كـ r ، حيث تشير التقاليد n إلى طول المصفوفة.
تعتمد خوارزمية الفرز السريع على إجراء التقسيم. يختار القسم بعض عناصر المصفوفة ويعيد ترتيب عناصر قسم المصفوفة بحيث يتم تقسيم المصفوفة إلى جزأين: الجزء الأيسر يحتوي على عناصر أقل من هذا العنصر ، والجزء الأيمن يحتوي على عناصر أكبر من هذا العنصر أو مساوية له. يسمى هذا العنصر الفاصل المحور .
تنفيذ Partiion:
partition(l, r):
pivot = a[random(l ... r - 1)]
m = l
for i = l ... r - 1:
if a[i] < pivot:
swap(a[i], a[m])
m++
return m
يتم اختيار المحور في حالتنا بشكل عشوائي. هذه الخوارزمية تسمى عشوائية . في الواقع ، يمكن تحديد المحور بعدة طرق: إما أن تأخذ عنصرًا عشوائيًا ، أو تأخذ العنصر الأول / الأخير من القسم ، أو حدده بطريقة "ذكية". يعد اختيار المحور مهمًا جدًا للتعقيد النهائي لخوارزمية الفرز ، ولكن المزيد عن ذلك لاحقًا. تعقيد إجراء التقسيم هو O (n) ، حيث n = r - l طول القسم.
الآن نستخدم القسم لتنفيذ الفرز:
تنفيذ Partiion:
sort(l, r):
if r - l = 1:
return
m = partition(l, r)
sort(l, m)
sort(m, r)
حالة متطرفة - مصفوفة من عنصر واحد لها خاصية الترتيب. إذا كانت المصفوفة طويلة ، فإننا نستخدم القسم وندعو الإجراء بشكل متكرر على نصفي المصفوفة.
إذا قمت بتشغيل الفرز المكتوب باستخدام مثال المصفوفة 1 2 2 ، فستلاحظ أنه لن ينتهي أبدًا. لماذا حصل هذا؟
عند كتابة القسم ، قمنا بافتراض - يجب أن تكون جميع عناصر المصفوفة فريدة. خلاف ذلك ، فإن القيمة المرجعة لـ m ستكون l ولن تنتهي العودية أبدًا ، لأن الفرز (l ، m) سيستدعي الفرز (l ، l) والفرز (l ، m). لحل هذه المشكلة ، تحتاج إلى تقسيم المصفوفة ليس إلى جزأين (<pivot و> = pivot) ، ولكن إلى 3 أجزاء (<pivot ، = pivot ،> pivot) واستدعاء الفرز العودي للجزء الأول والثالث.
تحليل
أقترح تحليل هذه الخوارزمية.
يتم التعبير عن التعقيد الزمني للخوارزمية من خلال الصيغة: T (n) = n + T (a * n) + T ((1 - a) * n). وهكذا ، عندما نطلق على فرز مصفوفة من n عنصرًا ، يستغرق الأمر حوالي n من العمليات لتنفيذ القسم وتنفيذ نفسه مرتين باستخدام المعلمات a * n و (1 - a) * n ، لأن المحور يقسم العنصر إلى كسور.
في أفضل الأحوال ، a = 1/2 ، أي أن المحور يقسم المنطقة إلى جزأين متساويين في كل مرة. في هذه الحالة: T (n) = n + 2 * T (n / 2) = n + 2 * (n / 2 + 2 * T (n / 4)) = n + n + 4 * T (n / 4 ) = n + n + 4 * (n / 4 + 2 * T (n / 8)) = n + n + n + 8 * T (n / 8) =…. سيكون الإجمالي عبارة عن مصطلحات log (n) ، لأن المصطلحات تظهر حتى تقل الوسيطة إلى 1. نتيجة لذلك ، T (n) = O (n * log (n)).
في أسوأ الحالات ، a = 1 / n ، أي أن المحور يقطع عنصرًا واحدًا بالضبط. يحتوي الجزء الأول من المصفوفة على عنصر واحد ، والثاني يحتوي على n - 1. وهذا هو: T (n) = n + T (1) + T (n - 1) = n + O (1) + T (n - 1) = n + O (1) + (n - 1 + O (1) + T (n - 2)) = O (n ^ 2). يظهر المربع بسبب حقيقة أنه يظهر في الصيغة لمجموع التقدم الحسابي الذي يظهر في عملية خربشة الصيغة.
في المتوسط ، من الناحية المثالية ، ينبغي النظر في التوقعات الرياضية للخيارات المختلفة. يمكن إظهار أنه إذا قسم المحور المصفوفة بنسبة 1: 9 ، فإن التقارب الناتج سيظل O (n * log (n)).
يُطلق على الفرز اسم سريع ، لأن الثابت المخفي تحت علامة O تبين أنه صغير جدًا من الناحية العملية ، مما أدى إلى انتشار استخدام الخوارزمية في الممارسة العملية.
اقرأ أكثر
