GCSE এর জন্য বাইনারি সার্চ এবং মার্জ সর্ট কীভাবে কাজ করে?

যদি আপনি 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), যা বড় ডেটাসেটে এটি নাটকীয়ভাবে দ্রুত করে তোলে। একটি মিলিয়ন আইটেমের একটি সাজানো তালিকা সার্চ করুন এবং লিনিয়ার সার্চে এক মিলিয়ন পর্যন্ত তুলনার প্রয়োজন হতে পারে; বাইনারি সার্চে প্রায় 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 পদে সময় জটিলতা বলুন, বা কমপক্ষে এটি শব্দে বর্ণনা করুন (