Binary search மற்றும் merge sort GCSE-க்கு எவ்வாறு செயல்படுகிறது?

GCSE Computer Science-ஐ திருத்தினால், நான்கு பெயர்கள் மீண்டும் மீண்டும் வருகின்றன: linear search, binary search, bubble sort, மற்றும் merge sort. தேர்வு வாரியங்கள் இவற்றை கையால் தடம் பிடிக்க, 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

இது O(log n), இதனால் இது பெரிய தரவுசெটுகளில் நாটকীயமாக வேகமாக உள்ளது. வரிசைப்படுத்தப்பட்ட பட்டியலை ஒரு மில்லியன் உருப்படிகளுக்குத் தேடுங்கள் மற்றும் linear search ஒரு மில்லியன் ஒப்பீடுகள் வரை தேவைப்படலாம்; binary search சுமார் 20 தேவைப்படுகிறது. தேர்வாளர்கள் பொதுவாக உங்களுக்கு 16 எண்களின் ஒரு பட்டியலைக் கொடுக்கிறார்கள் மற்றும் எந்த குறியீடுகள் சரிபார்க்கப்படுகின்றன என்பது கண்டறிய கேட்கிறார்கள் — பேனா மற்றும் காகிதத்துடன் கையால் இந்தப் பயிற்சியைச் செய்யுங்கள், உங்கள் தலையில் மட்டுமல்ல.

Bubble sort: எளிய ஆனால் மெதுவான

Bubble sort பட்டியலைப் பலமுறை நடந்து, அவை தவறான வரிசையில் இருந்தால் அருகிலுள்ள உருப்படিகளைப் பரிமாறுகிறது. ஒவ்வொரு முழு கடபாசையும் பெரிய வரிசைப்படுத்தப்படாத உருப்படியை முடிவில் அதன் சரியான நிலানத்திற்கு தள்ளுகிறது.

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²) — ஒவ்வொரு உருப்படிக்கும், நீங்கள் முழு பட்டியல் மீண்டும் ஏறக்குறைய ஸ্கேன் செய்ய வேண்டும். இது பெரிய தரவுகளில் மெதுவாக இருப்பதால் பொதுவாக உண்மையான மென்பொருளில் பயன்படுத்தப்படுவதில்லை, ஆனால் தேர்வாளர்கள் இதை விரும்புகிறார்கள் কারணமாக கையால் கண்டறிவது சாத்தியமாகும் மற்றும் இது மீண்டுவரும் கடப்பாசை மற்றும் பரிமாற்றங்களின் ধারணையை தெளிவாகக் காட்டுகிறது. ஒரு தடம் அட்டவணையில் ஒப்பீடுகளின் எண்ணிக்கை மற்றும் பரிமாற்றங்களின் எண்ணிக்கை எவ்வாறு எண்ணுவது என்பது தெரிந்து கொள்ளுங்கள்; அது ஒரு பொதுவான மதிப்பெண் திட்டம் உருப்படி.

Merge sort: பகுத்து வெல்லுங்கள்

Merge sort பட்டியலை ஒவ்வொரு சப்-பட்டியலும் ஒரு உருப்படியைக் கொண்டிருக்கும் வரை பாதியாக ভাগ செய்யுங்கள், பின்னர் அந்த சப்-பட்டியல்களை வரிசைப்படுத்தப்பட்ட வரிசையில் மீண்டும் இணைக்கிறது.

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-ஐ வசப்படுத்துகிறது. GCSE கேள்விகள் சில சமயங்களில் split-and-merge வரையறை வரைய கேட்கிறது — பட்டியல் கீழ்நோக்கி பிரிக்கப்பட்டு பின்னர் மீண்டும் இணைக்கப்படும் ஒரு மரம் வடிவம். 8 எண்களின் பட்டியলுக்கு இதை வரைவதைப் பயிற்சி செய்யுங்கள் எனவே தேர்வு நிலைகளின் கீழ் இது வேகமாக.

தேர்வாளர்கள் உண்மையில் சோதிக்கும் விஷயம்

பেரும்பாலான மதிப்பெண் திட்டம் உங்களை இந்த வகையில் இருக்க விரும்புகிறது:

• ஒரு அல்கோரிதம் ஒரு கட்டமாக ஒரு கட்டம் மற்றும் ஒவ்வொரு கடப்பாசை அல்லது ஒப்பீட்டுக்குப் பிறகு பட்டியலின் நிலையை எழுதுங்கள்.
• Big O விதிமுறைகளில் நேர சிக்கலதையைக் கூறுங்கள், அல்லது குறைந்தபட்சம் அதை சொல்லுங்கள் (