Kiểm tra từng cái một
Tìm kiếm Tuyến tính: Kiểm tra từng cái một
Hãy tưởng tượng bạn có 10 thẻ úp, được đánh số từ 1 đến 10, xáo trộn ngẫu nhiên.
Bạn muốn tìm thẻ có số 7.
Bạn lật thẻ từng cái một, từ trái sang phải, cho đến khi tìm được.
| Tình huống | Lần lật cần thiết |
|---|---|
| Trường hợp tốt nhất | 1 lần lật (may mắn lần đầu tiên!) |
| Trường hợp xấu nhất | 10 lần lật (nó là thẻ cuối cùng) |
| Trung bình | khoảng 5 lần lật |
Bây giờ hãy tưởng tượng 100 thẻ. Trung bình: khoảng 50 lần lật.
1.000 thẻ? Trung bình: khoảng 500 lần lật.
Bạn thấy mẫu không? Gấp đôi thẻ, gấp đôi công việc. Công việc tăng lên theo một đường thẳng.
Các nhà khoa học máy tính gọi đây là tìm kiếm tuyến tính — tuyến tính có nghĩa là công việc tăng lên như một đường thẳng: ổn định & dự đoán được.
Tìm kiếm tuyến tính hoạt động trên bất kỳ danh sách nào, sắp xếp hay không. Điều đó làm cho nó đơn giản. Nhưng nó có thể chậm lại.
Bao nhiêu Tên?
Bạn có danh sách lớp của 20 tên được viết theo thứ tự ngẫu nhiên.
Bạn cần tìm tên Zoe.
Bạn kiểm tra tên từng cái một, từ trên cùng của danh sách xuống.
Cắt Danh sách ra Nửa
Tìm kiếm Nhị phân: Nhảy đến Giữa
Tìm kiếm nhị phân có một quy tắc: danh sách phải được sắp xếp trước.
Nếu danh sách 20 tên của bạn theo thứ tự từ A đến Z, bạn có thể sử dụng tìm kiếm nhị phân.
Cách hoạt động: mở ra tên ở giữa (tên #10). Hỏi: Zoe có trước hay sau tên này?
Z gần cuối bảng chữ cái, vì vậy Zoe đến sau giữa. Vứt bỏ nửa đầu. Bây giờ bạn chỉ có tên 11-20 còn lại.
Kiểm tra giữa 10 tên đó (tên #15). Z đến sau M, vì vậy Zoe đến sau tên #15. Vứt bỏ tên 11-14. Bây giờ bạn có tên 16-20.
Tiếp tục cắt ra nửa. Mỗi lần kiểm tra loại bỏ một nửa tên còn lại.
| Kích thước danh sách | Kiểm tra tối đa bằng tìm kiếm nhị phân |
|---|---|
| 20 tên | tối đa 5 lần kiểm tra |
| 1.000 tên | tối đa 10 lần kiểm tra |
| 1.000.000 tên | tối đa 20 lần kiểm tra |
So sánh với tìm kiếm tuyến tính trên 1.000.000 tên: trung bình 500.000 lần kiểm tra.
Tìm kiếm nhị phân cắt danh sách ra nửa mỗi lần. Cắt ra nửa liên tục đạt được 1 rất nhanh — đó là lý do tại sao nó vẫn hoạt động nhanh.
Tìm 'fig' trong Danh sách Sắp xếp
Đây là danh sách sắp xếp 8 từ:
1. apple 2. banana 3. cherry 4. date 5. elderberry 6. fig 7. grape 8. honeydew
Bạn muốn tìm fig bằng tìm kiếm nhị phân.
Nhớ rằng: kiểm tra giữa, hỏi xem mục tiêu của bạn có trước hay sau, rồi cắt danh sách ra nửa.
Hoán đổi Hàng xóm thành Thứ tự
Sắp xếp Nổi bọt: So sánh Hàng xóm & Hoán đổi
Sắp xếp nổi bọt sắp xếp danh sách theo thứ tự bằng cách so sánh hai mục hàng xóm cùng một lúc.
Nếu hai hàng xóm không theo thứ tự — hoán đổi chúng.
Tiếp tục thực hiện các lần chuyển qua danh sách cho đến khi không cần hoán đổi gì cả.
Ví dụ: sắp xếp [5, 3, 8, 1]
Lần chuyển qua 1:
- So sánh 5 & 3. 5 > 3, vì vậy hoán đổi → [3, 5, 8, 1]
- So sánh 5 & 8. 5 < 8, không hoán đổi → [3, 5, 8, 1]
- So sánh 8 & 1. 8 > 1, vì vậy hoán đổi → [3, 5, 1, 8]
Lần chuyển qua 2:
- So sánh 3 & 5. OK → [3, 5, 1, 8]
- So sánh 5 & 1. 5 > 1, hoán đổi → [3, 1, 5, 8]
- So sánh 5 & 8. OK → [3, 1, 5, 8]
Lần chuyển qua 3:
- So sánh 3 & 1. 3 > 1, hoán đổi → [1, 3, 5, 8]
- So sánh 3 & 5. OK. So sánh 5 & 8. OK.
Xong! [1, 3, 5, 8] ✓
Chú ý: số lớn nhất nổi lên cuối danh sách ở mỗi lần chuyển qua. Đó là cách sắp xếp nổi bọt có tên gọi của nó.
Sắp xếp nổi bọt hoạt động. Nó không phải là cách nhanh nhất cho danh sách lớn, nhưng nó dễ hiểu — hoàn hảo để học.
Sắp xếp [4, 2, 7, 1] bằng Sắp xếp Nổi bọt
Sắp xếp danh sách này bằng sắp xếp nổi bọt: [4, 2, 7, 1]
Hiển thị danh sách sau mỗi lần chuyển qua. Đếm bao nhiêu lần chuyển qua để hoàn thành.