Trả lời nhanh
Lợi ích của việc sắp xếp trong tìm kiếm là giúp tìm kiếm nhanh hơn và thuận tiện hơn. Khi dữ liệu đã có thứ tự, ta biết phải tìm ở đâu và có thể bỏ qua nhiều phần tử không cần xét. Còn phương án “giúp tìm kiếm chính xác hơn” chưa đúng, vì dữ liệu sắp xếp hay không thì kết quả tìm được vẫn như nhau.
Vì sao sắp xếp giúp tìm kiếm nhanh hơn?
Hãy hình dung bạn tìm một từ trong từ điển. Từ điển xếp theo thứ tự chữ cái nên bạn mở ngay gần chữ cần tìm, không phải đọc từ trang đầu. Nếu các từ bị xáo trộn, bạn buộc phải đọc lần lượt từng từ.
Máy tính cũng vậy:
- Dữ liệu chưa sắp xếp: chỉ có thể tìm tuần tự, tức là so sánh từng phần tử từ đầu đến cuối. Trường hợp xấu nhất phải xét hết cả danh sách.
- Dữ liệu đã sắp xếp: có thể dùng tìm kiếm nhị phân. Mỗi lần so sánh với phần tử ở giữa, ta loại được một nửa danh sách.
Ví dụ so sánh số bước tìm
Đây là ví dụ tự đặt để em hình dung. Giả sử có danh sách 1 000 số.
| Cách tìm | Điều kiện dữ liệu | Số lần so sánh nhiều nhất |
|---|---|---|
| Tìm tuần tự | Không cần sắp xếp | 1 000 |
| Tìm nhị phân | Phải sắp xếp trước | khoảng 10 (vì 210 = 1 024 > 1 000) |
Số bước giảm đi rất nhiều. Danh sách càng dài thì lợi ích càng rõ.
Loại trừ các cách hiểu sai
- “Giúp tìm kiếm chính xác hơn” – chưa đúng. Tìm kiếm tuần tự trên dữ liệu lộn xộn vẫn tìm đúng phần tử nếu nó có trong danh sách. Sắp xếp làm thay đổi tốc độ, không làm thay đổi tính đúng của kết quả.
- “Giúp tìm kiếm nhanh hơn” – đúng. Đây là lợi ích chính, nhờ có thể loại bỏ nhiều phần tử không cần xét.
- “Giúp tìm kiếm dễ hơn, thuận tiện hơn” – đúng. Người dùng dễ quan sát, dễ đoán vị trí cần tìm. Ví dụ danh bạ xếp theo tên, thư mục xếp theo ngày sửa đổi.
Nếu đề của em có phương án dạng “cả hai ý về tốc độ và sự thuận tiện”, hãy chọn phương án đó. Nếu không, chọn phương án nói về tìm kiếm nhanh hơn.
Mẹo nhớ
Sắp xếp giống việc xếp sách lên kệ theo môn: tìm sách nhanh chứ không phải sách đúng hơn. Gặp câu hỏi về lợi ích của sắp xếp, em hãy nghĩ đến từ khoá “nhanh” và “dễ”.
Lỗi sai thường gặp
- Nhầm “nhanh hơn” với “chính xác hơn”.
- Nghĩ rằng sắp xếp luôn có lợi. Thực ra nếu chỉ tìm một lần trong danh sách ngắn thì mất công sắp xếp có thể còn tốn hơn tìm tuần tự. Sắp xếp có lợi khi phải tìm nhiều lần.
- Quên rằng tìm kiếm nhị phân chỉ dùng được khi dữ liệu đã có thứ tự.
Luyện tập
- Vì sao cô thủ thư xếp sách theo mã số thì tìm sách nhanh hơn?
Đáp án: Nhờ thứ tự mã số, cô biết ngay khu vực cần tìm và bỏ qua phần lớn các cuốn sách còn lại. - Danh sách 15 số đã sắp xếp tăng dần. Tìm nhị phân cần tối đa bao nhiêu lần so sánh?
Đáp án: 4 lần, vì sau mỗi lần số phần tử còn lại giảm khoảng một nửa (15 → 7 → 3 → 1) và 24 = 16 > 15. - Đúng hay sai: “Sắp xếp xong thì máy tính sẽ tìm ra kết quả khác với khi chưa sắp xếp”.
Đáp án: Sai. Kết quả tìm được vẫn như nhau, chỉ khác về số bước thực hiện.
Câu hỏi thường gặp
Lợi ích của việc sắp xếp trong tìm kiếm là gì?
Là giúp tìm kiếm nhanh hơn và thuận tiện hơn, vì dữ liệu có thứ tự cho phép bỏ qua nhiều phần tử không cần xét.
Sắp xếp có làm kết quả tìm kiếm chính xác hơn không?
Không. Dù dữ liệu có sắp xếp hay không, nếu phần tử cần tìm có trong danh sách thì vẫn tìm thấy. Sắp xếp chỉ ảnh hưởng đến tốc độ.
Tìm kiếm nhị phân có cần sắp xếp dữ liệu trước không?
Có. Tìm kiếm nhị phân chỉ hoạt động đúng khi danh sách đã được sắp xếp theo thứ tự tăng hoặc giảm.
Khi nào việc sắp xếp trước khi tìm không đem lại lợi ích?
Khi danh sách rất ngắn hoặc chỉ cần tìm một lần, thời gian sắp xếp có thể lớn hơn thời gian tìm tuần tự.