GCSE کے لیے بائنری سرچ اور مرج سارٹ کیسے کام کرتے ہیں؟

اگر آپ GCSE Computer Science کے لیے algorithms پر نظرثانی کر رہے ہیں، تو چار نام بار بار سامنے آتے ہیں: linear search، binary search، bubble sort، اور merge sort۔ امتحانی بورڈز آپ سے ان کو ہاتھ سے trace کرنے، runtime کا پتا لگانے، یا pseudocode کی لکیریں مکمل کرنے کے لیے پوچھنے سے پیار کرتے ہیں۔ یہاں ہے جو امتحان اور اس سے آگے بڑی اہمیت رکھتا ہے۔

Linear search: بنیادی حد

Linear search ایک فہرست میں ہر چیز کو، ایک وقت میں ایک، اس وقت تک چیک کرتا ہے جب تک یہ ہدف نہ مل جائے یا آخر تک نہ پہنچ جائے۔ یہی سب کچھ ہے۔

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

بدترین صورت میں، آپ ہر عنصر کو چیک کرتے ہیں، تو یہ O(n) ہے۔ بہترین صورت میں، ہدف پہلا ہے، تو O(1) ہے۔ معلمین آپ سے دونوں بیان کرنے کو پوچھنا پسند کرتے ہیں۔ Linear search بغیر ترتیب شدہ ڈیٹا پر کام کرتا ہے، جو binary search پر اس کا ایک حقیقی فائدہ ہے۔

Binary search: وہ جو لوگوں کو الجھا دیتا ہے

Binary search صرف ترتیب شدہ فہرست پر کام کرتا ہے۔ آپ ہدف کا موازنہ درمیانی چیز سے کرتے ہیں۔ اگر ہدف چھوٹا ہے، تو آپ اوپری نصف کو نکال دیتے ہیں؛ اگر بڑا ہے، تو نچلے نصف کو نکال دیتے ہیں۔ یہاں تک دہرائیں کہ آپ اسے ڈھونڈیں یا عناصر ختم ہو جائیں۔

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

yہ O(log n) ہے، یہی وجہ ہے کہ یہ بڑے datasets پر ڈرامائی طور پر تیز ہے۔ دس لاکھ اشیاء کی ترتیب شدہ فہرست میں سے کھوجیں اور linear search کو ایک لاکھ موازنوں کی ضرورت ہو سکتی ہے؛ binary search کو تقریباً 20 کی ضرورت ہے۔ معلمین عام طور پر آپ کو کہتے ہیں، کہیں، 16 نمبروں کی فہرست دیتے ہیں اور آپ سے پوچھتے ہیں کہ کون سے اشاریے چیک ہوتے ہیں — اسے ہاتھ سے قلم اور کاغذ سے مشق کریں، نہ کہ صرف اپنے دماغ میں۔

Bubble sort: سادہ لیکن سست

Bubble sort بار بار فہرست میں جاتا ہے، اگلے اگلے اشیاء کو swap کرتا ہے اگر وہ غلط ترتیب میں ہیں۔ ہر مکمل pass سب سے بڑی غیر مرتب شدہ چیز کو آخر میں اس کی صحیح جگہ تک دھکیلتا ہے۔

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²) ہے — ہر عنصر کے لیے، آپ تقریباً پوری فہرست کو دوبارہ scan کر سکتے ہیں۔ یہ حقیقی سافٹویئر میں شاذ و ندیر استعمال ہوتا ہے کیونکہ یہ بڑے ڈیٹا پر سست ہے، لیکن معلمین اسے پسند کرتے ہیں کیونکہ اسے ہاتھ سے trace کرنا حق تھا اور یہ واضح طور پر دہرائے جانے والے passes اور swaps کے خیال کو ظاہر کرتا ہے۔ ایک trace ٹیبل میں موازنوں اور swaps کی تعداد شمار کرنا جانیں؛ یہ mark scheme کا ایک عام چیز ہے۔

Merge sort: تقسیم اور فتح

Merge sort فہرست کو بار بار نصف میں تقسیم کرتا ہے جب تک کہ ہر sublist میں ایک چیز نہ ہو، پھر ان sublists کو دوبارہ ترتیب شدہ ترتیب میں merge کرتا ہے۔

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)

Merge قدم ہر نصف کی سامنے کی اشیاء کا موازنہ کرتا ہے اور چھوٹی کو چنتا ہے، دہراتے ہوئے جب تک دونوں نصف استعمال نہ ہوں۔ یہ O(n log n) دیتا ہے، جو bubble sort کو آسانی سے شکست دیتا ہے سوائے tiny فہرستوں کے۔ GCSE سوالات کبھی کبھی آپ سے split-and-merge ڈایاگرام کھینچنے کو کہتے ہیں — درخت کی شکل دکھاتے ہوئے فہرست نیچے تقسیم ہو رہی ہے اور پھر دوبارہ جمع ہو رہی ہے۔ 8 نمبروں کی فہرست کے لیے اسے کھینچنے کی مشق کریں تاکہ آپ امتحان کی شرائط میں تیز ہوں۔

معلمین اصل میں کیا ٹیسٹ کرتے ہیں

زیادہ تر mark schemes چاہتے ہیں کہ آپ اس میں سے کر سکیں:

• ایک algorithm کو قدم در قدم trace کریں اور ہر pass یا موازنے کے بعد فہرست کی حالت لکھیں۔
• Big O شرائط میں وقت complexity بیان کریں، یا کم از کم اسے الفاظ میں بیان کریں (