Binary search และ merge sort ทำงานอย่างไรสำหรับ GCSE?

หากคุณกำลังทบทวน algorithms สำหรับ GCSE Computer Science ชื่อสี่ชื่อจะปรากฏขึ้นมาซ้ำแล้วซ้ำเล่า: linear search, binary search, bubble sort, และ merge sort คณะสอบบอบมักชอบขอให้คุณ trace ขั้นตอนเหล่านี้ด้วยมือ จำสไตล์การทำงาน หรือเติมบรรทัด 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 ตัวเลข และขอให้คุณ trace ว่าดัชนีใดได้รับการตรวจสอบ — ฝึกซ้อมด้วยมือด้วยปากกาและกระดาษ ไม่ใช่แค่ในหัวของคุณ

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²) — สำหรับทุกองค์ประกอบ คุณอาจต้องสแกนรายการเกือบทั้งหมดอีกครั้ง ไม่ค่อยมีการใช้ในซอฟต์แวร์จริง เพราะมันช้าในข้อมูลขนาดใหญ่ แต่ผู้สอบชอบมันเพราะการ trace ด้วยมือจะสามารถจัดการได้ และแสดงให้เห็นแนวคิดของการผ่านซ้ำและการสลับได้ชัดเจน รู้วิธีนับจำนวนการเปรียบเทียบและการสลับในตารางติดตามเนื้อหา นี่คือรายการแผนเกรดทั่วไป

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)

ขั้นตอนการผสานเปรียบเทียบรายการด้านหน้าของแต่ละครึ่งและเลือกรายการที่เล็กกว่า ทำซ้ำจนกว่าครึ่งทั้งสองจะใช้หมด สิ่งนี้ให้ O(n log n) ซึ่งเอาชนะ bubble sort ได้อย่างมั่นใจในสิ่งใดก็ตามนอกจากรายการเล็กน้อย คำถาม GCSE บางครั้งขอให้คุณวาดไดอะแกรมการแบ่งและผสาน — รูปร่างต้นไม้แสดงรายการแบ่งลงมาแล้วรวมกันใหม่ ฝึกซ้อมการวาดนี้สำหรับรายการ 8 ตัวเลขเพื่อให้คุณเร็วขึ้นภายใต้สภาวะสอบ

สิ่งที่ผู้สอบทดสอบจริงๆ

แผนเกรดส่วนใหญ่ต้องการให้คุณสามารถ:

• Trace algorithm ทีละขั้นตอนและเขียนสถานะของรายการหลังจากแต่ละรอบหรือการเปรียบเทียบ
• ระบุความซับซ้อนของเวลาในเงื่อนไข Big O หรืออย่างน้อยอธิบายด้วยคำพูด (