خوارزميات الترتيب

الفرز الذي بطيء عمداً

• كل مكتبة جادة تقوم بالفرز باستخدام خوارزمية لا يُطلب منك كتابتها في الامتحان. كلا من فرز الفقاعات وفرز الإدراج هما $O(n^2)$، وكلاهما يتفوق عليهما أي فرز جيد على قائمة كبيرة.
• هي في المنهج anyway، ولأسباب جيدة: فهي قصيرة بما يكفي للتتبع يدوياً، والتتبع هو ما تعلمك كيف يقوم الفرز فعلياً بفعله على المصفوفة.
• هناك أيضاً حالة حقيقية لاستخدام فرز الإدراج. على قائمة صغيرة أو شبه مرتبة بالفعل، هو حقاً الأسرع، وتنتقل المكتبات الحقيقية إليه لهذه الحالات تحديداً.
• هذه الدرس فرز الفقاعات وفرز الإدراج: الخوارزميات، سلوكها، وأين يربح كل واحد منهما.

فرز الفقاعات

FOR pass ← 1 TO n - 1
    swapped ← FALSE
    FOR i ← 1 TO n - pass
        IF A[i] > A[i + 1] THEN
            swap A[i], A[i + 1]
            swapped ← TRUE
        ENDIF
    NEXT i
    IF NOT swapped THEN      // already sorted
        EXIT FOR
    ENDIF
NEXT pass

• كل دورة تقارن الأزواج المجاورة وتبدل أي منها غير مرتبة، بحيث "تصعد" أكبر قيمة متبقية إلى النهاية.
• بعد الدورة $k$ تكون آخر $k$ عناصر نهائية، ولهذا تتوقف الحلقة الداخلية عند $n - \text{pass}$.
• علم swapped يسمح بالتوقف المبكر: إذا لم تتم أي تبديل خلال دورة كاملة، فإن القائمة مرتبة.

فرز الإدراج

FOR i ← 2 TO n
    key ← A[i]
    j ← i - 1
    WHILE j >= 1 AND A[j] > key DO
        A[j + 1] ← A[j]                 // shift right
        j ← j - 1
    ENDWHILE
    A[j + 1] ← key                      // drop it in
NEXT i

• يبني قسمًا مرتبًا في البداية، وينمو بعنصر واحد في كل مرة. يتم إبعاد كل عنصر جديد كـkey، وتزاحم العناصر الأكبر لليمين لفتح فراغ، ثم تُوضع المفتاح.
• هكذا يرتب معظم الناس مجموعة من بطاقات اللعب، وهو التشبيه المتوقع في الامتحان.

الجزء الأيسر مرتب، والجزء الأيمن غير مساس به، والحدود يتحرك لليمين

مثال محلول: تتبع دورة واحدة

الأداء

• محلي يعني أنه يحتاج فقط لكمية ثابتة من الذاكرة الإضافية، ويرتب داخل المصفوفة نفسها. مستقر يعني أن قيمتين متساويتين تحتفظان بترتيبهما النسبي الأصلي، وهو مهم عندما تكون القائمة مرتبة مسبقًا بمجال آخر.
• كلاهما يصل إلى $O(n)$ على بيانات مرتبة مسبقًا، ولكن فقط إذا كان فرز الفقاعات يحتوي على علم swapped. بدون هذا العلم، فإنه ينفذ جميع الدورات دائمًا.

مثال محلول: أي فرز، ولماذا

لماذا دورة واحدة ليست القصة الكاملة

• كلا الفرزين ينفذان دورات متكررة، ويميز بينهما الامتحان بما تحققه دورة واحدة ومتى يتوقفان.
• دورة فرز الفقاعات تقارن أزواجًا مجاورة وتبدلها، لذا تحمل الدورة الواحدة أكبر عنصر متبقي إلى موقعه النهائي. الفرز الكامل يستغرق $n - 1$ دورات.
• دورة فرز الإدراج تأخذ العنصر التالي وتحركه للخلف إلى الجزء المرتب بالفعل، لذا بعد $k$ دورات تكون أول $k$ عناصر مرتبة بينها البعض لكنها ليست في موقعها النهائي بعد.
• يمكن تحسين فرز الفقاعات بـعلم: إذا لم تتم أي تبدلات في دورة، فإن القائمة مرتبة مسبقًا وتتوقف الخوارزمية. على بيانات شبه مرتبة يحوله هذا إلى دورة واحدة.
• بدون العلم، كلاهما $n^2$ في أسوأ حالة، ولهذا Either خيار سيئ للملف الكبير ولماذا يسأل الامتحان عن الصغيرة.

علامات ضائعة

لقد فهمت الأمر