GCSE için binary search ve merge sort nasıl çalışır?

GCSE Bilgisayar Bilimleri için algoritmaları gözden geçiriyorsanız, dört isim tekrar tekrar ortaya çıkıyor: linear search, binary search, bubble sort ve merge sort. Sınav kurulları sizi bu algoritmaları elle izlemeye, çalışma zamanını belirlemeye veya eksik sahte kod satırlarını tamamlamaya çok seviyorlar. İşte sınavda ve ötesinde gerçekten önemli olan şeyler.

Linear search: temel seviye

Linear search, hedef öğeyi bulana veya listenin sonuna ulaşana kadar bir listedeki her öğeyi sırayla kontrol eder. Bu kadar.

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

En kötü durumda, her öğeyi kontrol edersiniz, bu yüzden O(n)'dir. En iyi durumda, hedef birinci konumdadır, bu yüzden O(1)'dir. Sınav sorusu soran kişiler her ikisini de belirtmenizi severler. Linear search sıralanmamış verilerle çalışır, bu da binary search'e göre tek gerçek avantajıdır.

Binary search: insanları çaşırtan algoritma

Binary search sadece sıralanmış bir liste üzerinde çalışır. Hedefi ortadaki öğe ile karşılaştırırsınız. Hedef daha küçükse, üst yarıyı atarsınız; daha büyükse, alt yarıyı atarsınız. Bulana veya öğeler bitene kadar tekrarlayın.

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

Bu O(log n)'dir ve bu yüzden büyük veri setlerinde çarpıcı şekilde daha hızlıdır. Bir milyonluk sıralanmış liste arayın ve linear search bir milyona kadar karşılaştırma yapmanız gerekebilir; binary search 20 kadar gerektirir. Sınav sorusu soran kişiler yaygın olarak size bir liste verirler, diyelim 16 sayı, ve hangi indexlerin kontrol edildiğini izlemenizi isterler — bunu sadece kafanızda değil, kalemle kağıtla elle yapın.

Bubble sort: basit ama yavaş

Bubble sort, listeyi tekrar tekrar yürüyerek bitişik öğeleri yanlış sıradaysa değiştirir. Her tam geçiş, en büyük sıralanmamış öğeyi sonundaki doğru konumuna iter.

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

En kötü durum O(n²)'dir — her öğe için, listeyi hemen hemen tamamını tekrar taramanız gerekebilir. Büyük veriler üzerinde yavaş olduğu için gerçek yazılımda nadiren kullanılır, ama sınav sorusu soran kişiler bunu severler çünkü elle izlemek yönetilebilirdir ve tekrarlanan geçişler ve değişikliklerin fikrini net gösterir. Bir izleme tablosundaki karşılaştırma ve değişikliklerin sayısını nasıl sayacağınızı bilin; bu yaygın bir puanlama şeması öğesidir.

Merge sort: böl ve yönet

Merge sort, listeyi her alt liste bir öğeye ulaşana kadar tekrar tekrar ikiye böler, sonra bu alt listeleri sıralanmış sırada geri birleştirir.

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 adımı her yarının ön öğelerini karşılaştırır ve daha küçük olanı seçer, her iki yarı da bitene kadar tekrarlayır. Bu O(n log n) verir, bu da bubble sort'u küçük listeler haricinde rahatça yener. GCSE soruları bazen bölünme ve birleştirme diyagramı çizmenizi ister — listenin aşağıya bölündüğü ve sonra birleştirildiği ağaç şekli. Sınav koşulları altında hızlı olmak için 8 sayıdan oluşan bir liste üzerinde bunu çizin.

Sınav sorusu soran kişiler gerçekte neyi test eder

Çoğu puanlama şeması sizin şunları yapabilmenizi ister:

• Bir algoritmayi adım adım izlemek ve her geçişten veya karşılaştırmadan sonra listenin durumunu yazmak.
• Zaman karmaşıklığını Big O terimleriyle belirtmek, veya en azından bunu kelimelerle tanımlamak (