Jak działają wyszukiwanie binarne i sortowanie przez scalanie dla GCSE?

Jeśli przygotowujesz się do algorytmów na egzaminie GCSE Computer Science, cztery nazwy pojawiają się wciąż na nowo: wyszukiwanie liniowe, wyszukiwanie binarne, sortowanie bąbelkowe i sortowanie przez scalanie. Komisje egzaminacyjne uwielbiają prosić cię, aby śledzić je ręcznie, określić złożoność czasową lub uzupełnić brakujące linie pseudokodu. Oto co rzeczywiście ważne na egzaminie i poza nim.

Wyszukiwanie liniowe: podstawa

Wyszukiwanie liniowe sprawdza każdy element na liście, jeden po drugim, aż znajdzie cel lub osiągnie koniec. Tyle.

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

W najgorszym przypadku sprawdzasz każdy element, więc to O(n). W najlepszym przypadku cel jest na początku, więc O(1). Egzaminatorzy lubią prosić cię o podanie obu. Wyszukiwanie liniowe działa na danych nieposortowanych, co jest jego jedną prawdziwą zaletą nad wyszukiwaniem binarnym.

Wyszukiwanie binarne: to co wszystkich myli

Wyszukiwanie binarne działa tylko na posortowanej liście. Porównujesz cel ze środkowym elementem. Jeśli cel jest mniejszy, odrzucasz górną połowę; jeśli większy, odrzucasz dolną połowę. Powtarzaj aż znajdziesz go lub skończy ci się elementy.

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

To jest O(log n), dlatego jest dramatycznie szybsze na dużych zbiorach danych. Przeszukaj posortowaną listę miliona elementów, a wyszukiwanie liniowe może wymagać do miliona porównań; wyszukiwanie binarne wymaga około 20. Egzaminatorzy często dają ci listę, powiedzmy, 16 liczb i proszą, aby śledzić, które indeksy są sprawdzane — pracuj nad tym ręcznie ołówkiem i papierem, nie tylko w głowie.

Sortowanie bąbelkowe: proste ale wolne

Sortowanie bąbelkowe wielokrotnie przechodzi przez listę, zamieniając sąsiadujące elementy, jeśli są w złej kolejności. Każde pełne przejście przesuwa największy nieposortowany element na jego właściwe miejsce na końcu.

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

Najgorszy przypadek to O(n²) — dla każdego elementu możesz skanować prawie całą listę jeszcze raz. Rzadko się go używa w prawdziwym oprogramowaniu, bo jest wolny na dużych danych, ale egzaminatorzy go lubią, bo śledzenie go ręcznie jest wykonalne i wyraźnie pokazuje ideę wielokrotnych przejść i zamian. Wiedz, jak liczyć liczbę porównań i zamian w tabeli śledzenia; to typowy punkt w schemacie oceny.

Sortowanie przez scalanie: dziel i zwyciężaj

Sortowanie przez scalanie dzieli listę na pół wielokrotnie, aż każda podlista ma jeden element, a następnie scala te podlisty z powrotem w posortowanej kolejności.

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)

Krok scalania porównuje pierwsze elementy każdej połowy i wybiera mniejszy, powtarzając aż obydwie połowy są użyte. Daje to O(n log n), co beat sortowanie bąbelkowe spokojnie na wszystkim poza maleńkimi listami. Pytania GCSE czasami proszą cię, aby narysować diagram podziału i scalania — kształt drzewa pokazujący listę dzielącą się w dół, a następnie łączącą się ponownie. Pracuj nad narysowaniem tego dla listy 8 liczb, aby był szybki pod presją egzaminu.

Co egzaminatorzy rzeczywiście testują

Wiekszość schematów oceny chce, abyś mógł:

• Śledzić algorytm krok po kroku i zapisywać stan listy po każdym przejściu lub porównaniu.
• Podać złożoność czasową w terminach Big O, lub przynajmniej opisać ją słowami (