جستجوی دودویی و مرتب‌سازی ادغام برای GCSE چگونه کار می‌کنند؟

اگر برای درس Computer Science در GCSE در حال مرور الگوریتم‌ها هستید، چهار نام بارها و بارها مطرح می‌شود: جستجوی خطی، جستجوی دودویی، مرتب‌سازی حبابی و مرتب‌سازی ادغام. هیئت‌های امتحانی عاشق پرسیدن این‌ها برای ردیابی دستی، شناخت زمان اجرا یا تکمیل خطوط گم‌شده در شبه‌کد هستند. اینجا آن چیزی است که برای امتحان و فراتر از آن واقعاً مهم است.

جستجوی خطی: پایه‌ی اولیه

جستجوی خطی هر آیتم در لیست را یک‌به‌یک بررسی می‌کند، تا زمانی که هدف را پیدا کند یا به انتهای لیست برسد. همین.

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) است، و این همان دلیلی است که بر روی مجموعه‌داده‌های بزرگ به طور چشمگیری سریع‌تر است. جستجوی یک لیست مرتب‌شده‌ی یک میلیون آیتمی را با جستجوی خطی انجام دهید و ممکن است تا یک میلیون مقایسه لازم باشد؛ جستجوی دودویی تنها حدود ۲۰ مقایسه نیاز دارد. امتحان‌دهندگان معمولاً یک لیست، مثلاً ۱۶ عدد، به شما می‌دهند و می‌خواهند که ردیابی کنید کدام شاخص‌ها بررسی می‌شوند — این را با قلم و کاغذ به‌صورت دستی تمرین کنید، نه فقط در ذهن‌تان.

مرتب‌سازی حبابی: ساده اما کند

مرتب‌سازی حبابی مکرراً از لیست عبور می‌کند و آیتم‌های مجاور را در صورت نادرست‌بودن ترتیب، تعویض می‌کند. هر بار عبور کامل بزرگ‌ترین آیتم مرتب‌نشده‌ی باقی‌مانده را به موضع صحیح آن در انتهای لیست می‌برد.

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 گاهی از شما می‌خواهند نمودار تقسیم‌و‌ادغام را رسم کنید — شکل درخت‌ی که نشان می‌دهد لیست چگونه پایین‌تر تقسیم می‌شود و سپس دوباره ترکیب می‌شود. برای یک لیست ۸ عددی این را تمرین کنید تا در شرایط امتحان سریع باشید.

آن‌چه امتحان‌دهندگان واقعاً آزمایش می‌کنند

اکثر طرح‌های نمره‌دهی می‌خواهند شما بتوانید:

• یک الگوریتم را گام به گام ردیابی کنید و وضعیت لیست را پس از هر عبور یا مقایسه یادداشت کنید.
• پیچیدگی زمان را به‌صورت Big O بیان کنید، یا حداقل آن را به‌صورت کلامی توضیح دهید (