Sorting algorithms
مُقدَّم| English | المعنى |
|---|---|
| bubble sort/ˈbʌbl sɔːt/ | ترتيب الفقاعة |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | فرز الإدراج |
| in place/ɪn pleɪs/ | في الموقع |
| stable/ˈsteɪbl/ | مستقر |
الفرز الذي بطيء عمداً
- كل مكتبة جادة تقوم بالفرز باستخدام خوارزمية لا يُطلب منك كتابتها في الامتحان. كلا من فرز الفقاعات وفرز الإدراج هما $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، وتزاحم العناصر الأكبر لليمين لفتح فراغ، ثم تُوضع المفتاح. - هكذا يرتب معظم الناس مجموعة من بطاقات اللعب، وهو التشبيه المتوقع في الامتحان.

الجزء الأيسر مرتب، والجزء الأيمن غير مساس به، والحدود يتحرك لليمين
خوارزميات الترتيب
compare adjacent, swap if needed
Step through a bubble sort: each pass floats the largest value to the end.
Bubble sort works by:
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Each pass swaps adjacent pairs, "bubbling" the largest element to the end.
The average/worst-case time complexity of bubble sort is:
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Two nested loops over n elements give O(n²); the best case (already sorted) is O(n) with the early exit.
مثال محلول: تتبع دورة واحدة
- تتبع الدورة الأولى لفرز الفقاعات على 5, 3, 8, 1.
- قارن 5 و3: غير مرتبين، تبدل، فتصبح 3, 5, 8, 1. قارن 5 و8: مرتبان، لا تبديل. قارن 8 و1: تبدل، فتصبح 3, 5, 1, 8.
- بعد دورة واحدة أصبحت أكبر قيمة، وهي 8، في موقعها النهائي، ويمكن تخطي مقارنة واحدة إضافية في كل دورة من الآن فصاعدًا.
- الآن تتبع الخطوة الثالثة لفرز الإدراج على 3, 5, 8, 1. المفتاح هو 1. أزاحم 8 و5 و3 كلًا منهما خانة واحدة لليمين، ثم ضع 1 في البداية: 1, 3, 5, 8. اعرض المصفوفة بعد كل خطوة؛ فهنا توجد الدرجات.
Insertion sort builds the sorted result by:
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
It grows a sorted prefix on the left, shifting larger elements right to drop each key into place.
How does insertion sort place each new element?
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Holding the key aside and shifting is what distinguishes it from bubble sort's repeated adjacent swaps.
الأداء
| فقاعات | إدراج | |
|---|---|---|
| الحالة الأفضل | $O(n)$، دورة واحدة بدون تبدلات | $O(n)$، مرتبة مسبقًا، بدون تزاحم |
| المتوسطة والأسوأ | $O(n^2)$ | $O(n^2)$ |
| ذاكرة إضافية | $O(1)$، محلي | $O(1)$، محلي |
| مستقر | نعم | نعم، مستقر |
- محلي يعني أنه يحتاج فقط لكمية ثابتة من الذاكرة الإضافية، ويرتب داخل المصفوفة نفسها. مستقر يعني أن قيمتين متساويتين تحتفظان بترتيبهما النسبي الأصلي، وهو مهم عندما تكون القائمة مرتبة مسبقًا بمجال آخر.
- كلاهما يصل إلى $O(n)$ على بيانات مرتبة مسبقًا، ولكن فقط إذا كان فرز الفقاعات يحتوي على علم
swapped. بدون هذا العلم، فإنه ينفذ جميع الدورات دائمًا.
After the first pass of a bubble sort on 5, 3, 8, 1, what is the array? Write the four numbers separated by commas.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
5 and 3 swap, 5 and 8 do not, 8 and 1 swap. The largest value has reached the end, so the next pass can be one comparison shorter.
مثال محلول: أي فرز، ولماذا
- قائمة من 200,000 سجل يجب فرزها من الصفر. لا لأحدهما: كلاهما $O(n^2)$، لذا تحتاج إلى دمج أو سريع فرز في $O(n \log n)$. قل ذلك بدلاً من اختيار الأقل سوءًا.
- قائمة مرتبة من 10,000 تستقبل 5 سجلات جديدة في النهاية ويجب فرزها مجددًا. فرز الإدراج: البيانات شبه مرتبة، لذا يزياحم كل مفتاح جديد مسافة قصيرة ويتقارب نحو $O(n)$.
- مثال تعليمي يجب تتبعه يدويًا على ورق. فرز الفقاعات: هو الأسهل في المتابعة، وهو استخدامه الحقيقي المتبقي.
- برر بناءً على حالة البيانات والحجم، وليس تفضيلًا عامًا.
Match each sorting idea to what it means.
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Bubble swaps neighbours, insertion grows a sorted prefix; both are O(n²) worst-case; stability is about equal-key order.
Insertion sort runs close to O(n) on small or nearly-sorted arrays, because few elements need to be shifted.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
On nearly-sorted data each new item is already almost in place — which is why insertion sort beats fancier sorts on small inputs.
Which are true of both bubble sort and insertion sort? Select جميعها that apply.
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
On a large unsorted list an O(n log n) sort wins decisively. Saying so is the right answer, not choosing the least bad of the two.
لماذا دورة واحدة ليست القصة الكاملة
- كلا الفرزين ينفذان دورات متكررة، ويميز بينهما الامتحان بما تحققه دورة واحدة ومتى يتوقفان.
- دورة فرز الفقاعات تقارن أزواجًا مجاورة وتبدلها، لذا تحمل الدورة الواحدة أكبر عنصر متبقي إلى موقعه النهائي. الفرز الكامل يستغرق $n - 1$ دورات.
- دورة فرز الإدراج تأخذ العنصر التالي وتحركه للخلف إلى الجزء المرتب بالفعل، لذا بعد $k$ دورات تكون أول $k$ عناصر مرتبة بينها البعض لكنها ليست في موقعها النهائي بعد.
- يمكن تحسين فرز الفقاعات بـعلم: إذا لم تتم أي تبدلات في دورة، فإن القائمة مرتبة مسبقًا وتتوقف الخوارزمية. على بيانات شبه مرتبة يحوله هذا إلى دورة واحدة.
- بدون العلم، كلاهما $n^2$ في أسوأ حالة، ولهذا Either خيار سيئ للملف الكبير ولماذا يسأل الامتحان عن الصغيرة.
A sorted list of 10,000 records gains 5 new records at the end. Which sort suits re-sorting it?
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Nearly sorted data is exactly insertion sort's best case, approaching O(n). Real libraries switch to it for this reason.
Match each sort to what one pass achieves.
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
That difference is what a trace question is really testing. A bubble-sort flag also lets it stop early on nearly-sorted data, which insertion sort handles well anyway.
علامات ضائعة
- فرز الفقاعات يقارن أزواجًا مجاورة. الإجابة التي تقارن عنصرًا مع جميعOthers تصف خوارزمية مختلفة.
- يقل كل مرور في الحلقة الداخلية، لأن نهاية المصفوفة أصبحت نهائية. اذكر السبب.
- الترتيب بالإدراج يقوم بـ نقل العناصر لليمين لفتح فراغ؛ ولا يقوم بالتبديل بشكل متكرر. هذا التمييز هو جوهر الخوارزمية.
- كلاهما $O(n^2)$ في المتوسط وفي أسوأ الحالات، و$O(n)$ في أفضل حالة. قدم الحالة مع الترتيب.
لقد فهمت الأمر
- ترتيب الفقاعات: مرورات متكررة تقارن أزواجًا متجاورة وتقوم بالتبديل، حيث تصعد أكبر عنصر إلى النهاية، وتتقلص الحلقة الداخلية في كل مرور، مع وجود علم
swappedللخروج المبكر - ترتيب الإدراج: توسيع جزء مرتب في البداية، مع إبقاء كل مفتاح جانبًا، ونقل العناصر الأكبر يمينًا وإسقاط المفتاح في الفراغ
- كلاهما $O(n^2)$ متوسط وأسوأ، $O(n)$ أفضل، محليًا ومستقر
- ترتيب الإدراج يتفوق حقًا على القوائم الصغيرة أو شبه المرتبة تقريبًا؛ أما بالنسبة لقائمة غير مرتبة كبيرة، فلا واحد منهما هو الإجابة الصحيحة