Một tuần Minh tìm một cuốn sách mất 20 phút. Tuần sau, đúng cuốn đó chỉ mất 20 giây. Cùng thư viện, cùng số sách — vậy điều gì đã đổi?
Thư viện trường đang xếp sách kiểu "ai trả về đâu thì để đó" — không theo quy tắc nào.
Minh muốn tìm một cuốn cụ thể phải lục qua gần hết các kệ, hết cuốn này tới cuốn khác, mất tới 20 phút.
Tuần sau, cô Hạnh xếp lại toàn bộ sách theo đúng thứ tự bảng chữ cái tên tác giả. Lần sau Minh tìm đúng cuốn đó — chỉ mất 20 giây.
Cùng một thư viện, cùng số sách, cùng một cuốn cần tìm — sao thời gian tìm chênh nhau tới 60 lần?
Số sách không đổi. Người tìm (Minh) cũng không đổi. Vậy điều gì đã thay đổi để tìm nhanh hơn hẳn đến thế?
Không phải Minh "tìm giỏi hơn".
Sách đã được SẮP XẾP TRƯỚC theo một trật tự nhất định — nên khi tìm, có thể bỏ qua hẳn một nửa số kệ mỗi lần thu hẹp phạm vi, thay vì phải lục từng cuốn một.
Việc xếp dữ liệu theo một trật tự nhất định gọi là SẮP XẾP (sorting).
Việc dựa vào trật tự đó để tìm nhanh một mục cụ thể gọi là TÌM KIẾM (searching) — hai việc luôn đi cùng nhau trong máy tính.
Nếu dữ liệu không được sắp xếp, cách tìm duy nhất là dò lần lượt từng phần tử (tìm kiếm tuần tự) — với N phần tử, tệ nhất phải dò cả N lần.
Nếu dữ liệu ĐÃ được sắp xếp, có thể dùng cách "chia đôi liên tục" (tìm kiếm nhị phân): so với phần tử ở giữa, biết ngay cần tìm ở nửa nào, bỏ hẳn nửa còn lại. Với 1.000 cuốn sách, chỉ cần khoảng 10 lần so sánh là tìm ra, thay vì tối đa 1.000 lần.
Đánh đổi: sắp xếp trước cũng tốn công (một lần) — nhưng bù lại, mọi lần tìm sau đó đều nhanh vượt trội.
Tra một từ trong từ điển giấy: vì từ điển đã sắp theo bảng chữ cái, ta mở đại một trang giữa, so chữ cái đầu, rồi lật về trước hoặc sau — không ai dò tuần tự từng từ từ trang đầu.
Không sắp xếp/tìm kiếm hiệu quả, mọi tra cứu trên máy tính (tìm một bài hát trong hàng triệu bài, tìm một sản phẩm trên sàn thương mại điện tử) sẽ chậm tới mức không dùng nổi khi dữ liệu đủ lớn.
Danh bạ điện thoại luôn hiện theo thứ tự A-Z; công cụ tìm kiếm trên web trả kết quả gần như tức thì dù đang tìm trong hàng tỷ trang.
Bấm vào ô em nghĩ là đúng.
1. Nếu 1.000 cuốn sách chưa được sắp xếp, tệ nhất phải dò bao nhiêu cuốn để tìm ra một cuốn cụ thể?
2. Sắp xếp trước cũng tốn công — vậy khi nào KHÔNG đáng bỏ công sắp xếp?
3. Tìm kiếm nhị phân đòi hỏi điều kiện gì trước khi dùng được?
Câu hỏi của em sẽ hiện ở đây, chỉ lưu trên máy của em thôi.
Cuộn nốt xuống dưới nhé — sắp xong trang này rồi!