كيف يعمل البحث الثنائي والترتيب بالدمج من أجل GCSE؟

إذا كنت تراجع الخوارزميات لـ GCSE في علوم الحاسوب، فإن أربعة أسماء تظهر مراراً وتكراراً: البحث الخطي والبحث الثنائي والترتيب الفقاعي والترتيب بالدمج. مجالس الامتحانات تحب أن تطلب منك تتبع هذه يدوياً أو إيجاد وقت التشغيل أو ملء الأسطر المفقودة من pseudocode. إليك ما يهمك فعلاً للامتحان وما بعده.

البحث الخطي: الخط الأساسي

البحث الخطي يفحص كل عنصر في القائمة، واحداً تلو الآخر، حتى يجد الهدف أو يصل إلى النهاية. هذا كل شيء.

for i = 0 to length(list) - 1
    if list[i] == target then
        return i
return -1

في أسوأ الحالات، تفحص كل عنصر، لذا O(n). أفضل حالة، الهدف في البداية، لذا O(1). فاحصو الامتحانات يحبون أن تذكر الاثنين. البحث الخطي يعمل على البيانات غير المرتبة، وهذا هو ميزته الحقيقية الوحيدة على البحث الثنائي.

البحث الثنائي: الذي يربك الناس

البحث الثنائي يعمل فقط على قائمة مرتبة. تقارن الهدف بالعنصر الأوسط. إذا كان الهدف أصغر، تتجاهل النصف الأعلى؛ إذا كان أكبر، تتجاهل النصف الأسفل. كرر حتى تجده أو ينفد لديك عناصر.

low = 0
high = length(list) - 1
while low <= high
    mid = (low + high) / 2
    if list[mid] == target then
        return mid
    else if list[mid] < target then
        low = mid + 1
    else
        high = mid - 1
return -1

هذا O(log n)، وهذا هو السبب في أنه أسرع بشكل كبير على مجموعات البيانات الكبيرة. ابحث في قائمة مرتبة من مليون عنصر وقد يحتاج البحث الخطي إلى مليون مقارنة؛ البحث الثنائي يحتاج إلى حوالي 20. فاحصو الامتحانات غالباً ما يعطونك قائمة من، مثلاً، 16 رقماً ويطلبون منك تتبع أي فهارس يتم فحصها — مارس هذا يدوياً بقلم وورقة، وليس فقط في رأسك.

الترتيب الفقاعي: بسيط لكن بطيء

الترتيب الفقاعي يسير بشكل متكرر عبر القائمة، مبادلاً العناصر المجاورة إذا كانت بالترتيب الخاطئ. كل مسار كامل يدفع أكبر عنصر غير مرتب إلى موضعه الصحيح في النهاية.

for i = 0 to length(list) - 1
    for j = 0 to length(list) - 2 - i
        if list[j] > list[j+1] then
            swap(list[j], list[j+1])

أسوأ حالة هي O(n²) — لكل عنصر، قد تفحص تقريباً القائمة بأكملها مرة أخرى. نادراً ما يُستخدم في البرامج الحقيقية لأنه بطيء على البيانات الكبيرة، لكن فاحصو الامتحانات يحبونه لأن تتبعه يدوياً يمكن التحكم به ويوضح بوضوح فكرة المسارات والمبادلات المتكررة. اعرف كيفية عد عدد المقارنات والمبادلات في جدول التتبع؛ هذا عنصر شائع في جدول العلامات.

الترتيب بالدمج: فرق واحكم

الترتيب بالدمج يقسم القائمة إلى نصفين بشكل متكرر حتى يكون لكل قائمة فرعية عنصر واحد، ثم يدمج تلك القوائم الفرعية مرة أخرى بالترتيب الصحيح.

function mergeSort(list)
    if length(list) <= 1 then
        return list
    mid = length(list) / 2
    left = mergeSort(list[0:mid])
    right = mergeSort(list[mid:])
    return merge(left, right)

خطوة الدمج تقارن العناصر الأمامية لكل نصف وتختار الأصغر، وتكرر حتى يتم استنزاف كلا النصفين. هذا يعطي O(n log n)، الذي يتفوق على الترتيب الفقاعي بشكل مريح على أي شيء باستثناء القوائم الصغيرة جداً. أسئلة GCSE أحياناً تطلب منك رسم مخطط الانقسام والدمج — شكل شجرة يوضح القائمة تنقسم لأسفل ثم تتعاد الجمع. مارس رسم هذا لقائمة من 8 أرقام لكي تكون سريعاً فيه في ظروف الامتحان.

ما يختبره فاحصو الامتحانات فعلاً

معظم جداول العلامات تريد منك أن تكون قادراً على:

• تتبع خوارزمية خطوة بخطوة وكتابة حالة القائمة بعد كل مسار أو مقارنة.
• ذكر التعقيد الزمني بـ Big O أو على الأقل وصفه بالكلمات (