GCSE के लिए binary search और merge sort कैसे काम करते हैं?

अगर आप GCSE Computer Science के लिए algorithms को revise कर रहे हैं, तो चार नाम बार-बार सामने आते हैं: linear search, binary search, bubble sort, और merge sort। Exam boards आपसे इन्हें hand से trace करने, runtime निकालने, या pseudocode की missing lines भरने के लिए सवाल पूछना पसंद करते हैं। यहाँ वह सब कुछ है जो exam के लिए और उससे आगे के लिए मायने रखता है।

Linear search: आधार

Linear search एक list के हर item को check करता है, एक समय में एक, जब तक वह target को find न कर ले या अंत तक न पहुँच जाए। बस इतना ही।

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

Worst case में, आप हर single element को check करते हैं, तो यह O(n) है। Best case में, target पहला है, तो O(1) है। Examiners दोनों को state करने के लिए पूछना पसंद करते हैं। Linear search unsorted data पर काम करता है, जो binary search पर इसका एक real advantage है।

Binary search: जो लोगों को confuse करता है

Binary search केवल एक sorted list पर काम करता है। आप target को middle item से compare करते हैं। अगर target छोटा है, तो आप top half को discard करते हैं; अगर बड़ा है, तो bottom half को discard करते हैं। तब तक repeat करें जब तक आप इसे find न कर लें या items खत्म न हो जाएँ।

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) है, जो बड़े datasets पर इसे dramatically तेज़ बनाता है। एक million items की sorted list को search करें और linear search को a million comparisons तक की जरूरत हो सकती है; binary search को करीब 20 की जरूरत है। Examiners आमतौर पर आपको, कहें, 16 numbers की एक list देते हैं और आपसे पूछते हैं कि कौन से indices check किए गए — इसे hand से pen और paper के साथ practice करें, न कि सिर्फ अपने head में।

Bubble sort: सरल लेकिन धीमा

Bubble sort बार-बार list को walk करता है, adjacent items को swap करता है अगर वे wrong order में हैं। हर full pass सबसे बड़े unsorted item को उसकी सही position पर end में push करता है।

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])

Worst case O(n²) है — हर element के लिए, आप almost पूरी list को फिर से scan कर सकते हैं। यह real software में rarely use होता है क्योंकि यह large data पर slow है, लेकिन examiners इसे पसंद करते हैं क्योंकि इसे trace करना hand से manageable है और यह repeated passes और swaps का idea clearly दिखाता है। एक trace table में comparisons और swaps की संख्या count करना जानते हैं; यह एक common mark scheme item है।

Merge sort: divide और conquer

Merge sort list को बार-बार आधा split करता है जब तक हर sublist का one item न हो, फिर उन sublists को sorted order में वापस 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 step हर half के front items को compare करता है और छोटे को pick करता है, तब तक repeat करता है जब तक दोनों halves use न हो जाएँ। यह O(n log n) देता है, जो bubble sort को छोटी lists को छोड़कर comfortably beat करता है। GCSE questions कभी-कभी आपसे split-and-merge diagram draw करने के लिए कहते हैं — एक tree shape दिखाता है जो list को divide down करता है और फिर recombine करता है। 8 numbers की एक list के लिए यह draw करने का practice करें ताकि आप exam conditions में इसमें तेज़ हों।

Examiners असल में क्या test करते हैं

अधिकांश mark schemes आपसे यह चाहते हैं:

• एक algorithm को step by step trace करें और हर pass या comparison के बाद list की state को लिखें।
• Big O terms में time complexity state करें, या कम से कम इसे words में describe करें (