Binary search và merge sort hoạt động như thế nào đối với GCSE?

Nếu bạn đang ôn tập các thuật toán cho GCSE Computer Science, bốn cái tên xuất hiện lặp đi lặp lại: linear search, binary search, bubble sort và merge sort. Ban thi yêu thích hỏi bạn trace những thuật toán này bằng tay, xác định thời gian chạy hoặc điền vào các dòng pseudocode còn thiếu. Dưới đây là những gì thực sự quan trọng cho kỳ thi và hơn thế nữa.

Linear search: đường cơ sở

Linear search kiểm tra từng mục trong một danh sách, một lần một, cho đến khi tìm thấy mục tiêu hoặc đến cuối danh sách. Thế là đủ.

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

Trường hợp tồi tệ nhất, bạn kiểm tra từng phần tử, nên độ phức tạp là O(n). Trường hợp tốt nhất, mục tiêu ở vị trí đầu tiên, nên O(1). Những người chấm thi thích hỏi bạn phát biểu cả hai. Linear search hoạt động trên dữ liệu chưa sắp xếp, đây là ưu điểm thực sự duy nhất của nó so với binary search.

Binary search: cái làm người ta nhầm lẫn

Binary search chỉ hoạt động trên danh sách đã sắp xếp. Bạn so sánh mục tiêu với mục ở giữa. Nếu mục tiêu nhỏ hơn, bạn loại bỏ nửa trên; nếu lớn hơn, loại bỏ nửa dưới. Lặp lại cho đến khi tìm thấy hoặc hết mục.

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

Đây là O(log n), đó là lý do tại sao nó nhanh hơn đáng kể trên tập dữ liệu lớn. Tìm kiếm danh sách đã sắp xếp có một triệu mục và linear search có thể cần đến một triệu lần so sánh; binary search chỉ cần khoảng 20 lần. Những người chấm thi thường cho bạn danh sách, chẳng hạn như 16 số, và hỏi bạn trace xem những chỉ số nào được kiểm tra — hãy thực hành điều này bằng tay với bút và giấy, không chỉ trong đầu.

Bubble sort: đơn giản nhưng chậm

Bubble sort lặp đi lặp lại qua danh sách, hoán đổi các mục liền kề nếu chúng ở sai thứ tự. Mỗi lần đi qua đầy đủ đẩy mục lớn nhất chưa được sắp xếp đến vị trí đúng ở cuối.

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

Trường hợp tồi tệ nhất là O(n²) — đối với mỗi phần tử, bạn có thể quét lại gần như toàn bộ danh sách. Nó hiếm khi được sử dụng trong phần mềm thực vì nó chậm trên dữ liệu lớn, nhưng những người chấm thi thích nó vì trace nó bằng tay có thể quản lý được và nó rõ ràng cho thấy ý tưởng về các lần đi qua và hoán đổi lặp đi lặp lại. Biết cách đếm số lần so sánh và hoán đổi trong bảng trace; đây là mục thường gặp trong tiêu chí chấm điểm.

Merge sort: chia để trị

Merge sort chia danh sách làm đôi lặp đi lặp lại cho đến khi mỗi danh sách con có một mục, rồi hợp nhất các danh sách con đó lại với nhau theo thứ tự đã sắp xếp.

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)

Bước merge so sánh các mục ở phía trước của mỗi nửa và chọn mục nhỏ hơn, lặp lại cho đến khi cả hai nửa được sử dụng hết. Điều này cho O(n log n), vượt trội hơn bubble sort dễ dàng trên bất kỳ cái gì ngoài danh sách nhỏ. Các câu hỏi GCSE đôi khi yêu cầu bạn vẽ sơ đồ chia và hợp nhất — một hình dạng cây cho thấy danh sách chia xuống rồi kết hợp lại. Hãy thực hành vẽ điều này cho danh sách 8 số để bạn nhanh chóng dưới điều kiện kỳ thi.

Những gì những người chấm thi thực sự kiểm tra

Hầu hết tiêu chí chấm điểm muốn bạn có thể:

• Trace một thuật toán từng bước và ghi lại trạng thái của danh sách sau mỗi lần đi qua hoặc so sánh.
• Phát biểu độ phức tạp thời gian ở các điều khoản Big O, hoặc ít nhất mô tả nó bằng lời nói (