Sắp xếp xếp hàng theo chiều cao: bốn cách mà máy tính cũng dùng

Xếp một hàng bạn bè từ thấp đến cao có nhiều cách, và máy tính dùng đúng những cách ấy để sắp xếp số, tên hay ngày tháng. Bốn cách quen thuộc nhất là nổi bọt (đổi chỗ hai bạn đứng cạnh nhau), chọn (tìm bạn thấp nhất đưa lên đầu), chèn (từng bạn tìm chỗ của mình) và trộn (chia đôi rồi ghép lại). Với hàng mười người, cách nào cũng xong nhanh; với hàng một triệu, chọn đúng cách có thể nhanh hơn hàng chục nghìn lần.

Vì sao sắp xếp quan trọng đến thế

Hãy tưởng tượng một quyển từ điển mà các từ không theo thứ tự chữ cái. Muốn tra một từ, bạn phải đọc từ trang đầu tới khi gặp. Sắp xếp giúp tìm kiếm nhanh, giúp nhận ra cái trùng lặp, giúp thấy ngay cái lớn nhất, nhỏ nhất. Danh sách lớp xếp theo tên, danh bạ điện thoại, thư trong hộp thư xếp theo ngày, sản phẩm trong cửa hàng trực tuyến xếp theo giá: đằng sau mỗi thứ là một thuật toán sắp xếp.

Vì sắp xếp được dùng nhiều đến vậy, các nhà khoa học máy tính đã nghiên cứu nó suốt nhiều chục năm, và đến nay vẫn có người tìm cách làm nó nhanh hơn trong những trường hợp đặc biệt.

Luật chung: chỉ được so hai người một lúc

Để hiểu máy tính sắp xếp thế nào, hãy đặt một luật: không ai được đứng ngoài nhìn cả hàng rồi chỉ chỗ. Mỗi lần chỉ được gọi hai bạn ra so chiều cao với nhau, rồi quyết định có đổi chỗ hay không. Máy tính cũng làm như vậy: nó so hai con số một lần. Số lần so càng ít, cách sắp xếp càng nhanh.

Một lưu ý khi làm trên lớp: chiều cao chỉ là một đặc điểm để luyện thuật toán, không nói lên ai giỏi hơn ai. Nếu có bạn ngại chuyện chiều cao, hãy cho mỗi bạn cầm một tấm thẻ ghi số ngẫu nhiên và sắp xếp theo số trên thẻ. Thuật toán vẫn y nguyên.

Cách 1: sắp xếp nổi bọt

Bắt đầu từ đầu hàng. Hai bạn đứng cạnh nhau so chiều cao, nếu bạn bên trái cao hơn thì đổi chỗ. Dịch sang cặp tiếp theo, làm tương tự, tới cuối hàng. Hết một lượt, bạn cao nhất chắc chắn đã "nổi" về cuối hàng, giống bọt nước nổi dần lên mặt. Làm lượt thứ hai, bạn cao thứ hai về đúng chỗ. Cứ thế cho tới khi một lượt đi qua mà không ai phải đổi chỗ.

Ưu điểm: rất dễ hiểu, dễ làm. Nhược điểm: chậm. Với hàng 8 bạn xếp ngược hoàn toàn, phải so tới 28 lần. Mỗi người có thể phải đổi chỗ nhiều lần mới về đúng vị trí.

Cách 2: sắp xếp chọn

Đi dọc cả hàng để tìm bạn thấp nhất. Cách tìm: bạn đầu hàng tạm giữ danh hiệu "thấp nhất", lần lượt so với từng bạn phía sau, gặp ai thấp hơn thì danh hiệu chuyển sang người đó. Đi hết hàng, đưa bạn thấp nhất lên vị trí số 1. Sau đó làm lại với phần còn lại của hàng, tìm bạn thấp nhất đưa lên vị trí số 2. Cứ thế tới hết.

Số lần so cũng nhiều như nổi bọt: với 8 bạn là 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 lần. Nhưng số lần đổi chỗ thì ít hơn hẳn, mỗi lượt chỉ đổi đúng một lần. Nếu việc so thì nhanh mà việc đổi chỗ thì tốn công, như khi phải bê những thùng hàng nặng, thì cách này có lợi.

Cách 3: sắp xếp chèn

Đây là cách nhiều người tự làm mà không biết tên. Khi xếp lại một chồng sách vừa mang về lên kệ theo chiều cao, ta cầm từng cuốn, nhìn những cuốn đã xếp trên kệ, và nhét nó vào đúng chỗ.

Với hàng người: bạn đầu tiên đứng một mình, coi như đã xếp xong. Bạn thứ hai bước vào, so với bạn thứ nhất, đứng trước hoặc sau. Bạn thứ ba bước vào, đi ngược từ cuối phần đã xếp, so với từng người cho tới khi gặp người thấp hơn mình thì đứng ngay sau người đó. Cứ thế từng bạn một.

Cách chèn có một điểm mạnh đặc biệt: nếu hàng gần như đã đúng thứ tự, chỉ lệch vài người, thì nó xong rất nhanh, vì mỗi bạn mới chỉ cần so một hai lần là tìm thấy chỗ. Đầu năm học, khi lớp chỉ có thêm hai bạn mới, cô giáo không cần xếp lại cả hàng mà chỉ cần chèn hai bạn ấy vào.

Cách 4: sắp xếp trộn, chia đôi rồi ghép

Cách này dùng ý tưởng chia để trị:

1. Chia hàng làm đôi. Chia mỗi nửa làm đôi tiếp. Làm cho tới khi mỗi nhóm chỉ còn một bạn. Một bạn đứng một mình thì coi như đã xếp đúng.
2. Ghép từng cặp nhóm nhỏ thành nhóm lớn hơn đã có thứ tự. Cách ghép hai nhóm đã xếp: nhìn hai bạn đứng đầu hai nhóm, ai thấp hơn thì bước ra đứng vào hàng mới. Lặp lại tới khi hết cả hai nhóm.
3. Ghép tiếp cho tới khi chỉ còn một hàng.

Phép ghép rất nhanh vì mỗi lần chỉ so hai người đứng đầu, không phải nhìn lại phía sau. Ý tưởng này được nhà toán học John von Neumann mô tả từ năm 1945, và đến nay vẫn là nền của nhiều cách sắp xếp mà máy tính dùng hằng ngày.

So sánh: chậm và nhanh khác nhau đến đâu

Bảng dưới so số lần so sánh tối đa của cách nổi bọt hoặc chọn với cách trộn. Con số của cách trộn là giới hạn trên, thực tế thường ít hơn một chút.

Số người cần xếp	Nổi bọt hoặc chọn	Trộn
8	28	17
32	496	129
1.000	499.500	khoảng 9.000
1.000.000	gần 500 tỉ	khoảng 20 triệu

Với 8 người, khác biệt chẳng đáng kể. Với một triệu con số, cách nổi bọt cần nhiều phép so gấp hơn hai mươi nghìn lần cách trộn. Đó là lý do người lập trình quan tâm tới việc chọn thuật toán: số người, số dữ liệu tăng lên thì khác biệt phình to rất nhanh.

Nhưng đừng vội gạt bỏ những cách chậm. Với danh sách ngắn, cách chèn đơn giản lại thường nhanh hơn trong thực tế, vì không tốn công chia nhóm. Nhiều chương trình thật dùng cách trộn cho danh sách dài, rồi chuyển sang cách chèn khi các nhóm đã nhỏ.

Thử làm: ba hoạt động sắp xếp trên sân trường

Hoạt động 1: thi xem cách nào ít lần so nhất

Cần 8 bạn, mỗi bạn cầm một thẻ ghi một số bất kỳ (hoặc dùng chiều cao). Thêm một bạn làm người đếm số lần so. Xáo trộn hàng, thử lần lượt cách nổi bọt, chọn, chèn. Mỗi lần hai bạn so với nhau, người đếm ghi một vạch. So kết quả của ba cách. Rồi thử với hàng đã gần đúng thứ tự, chỉ lệch hai bạn, xem cách nào thắng.

Hoạt động 2: mạng sắp xếp vẽ phấn

Đây là hoạt động trong bộ tài liệu Khoa học máy tính không cần máy tính của Đại học Canterbury, New Zealand, ở đây rút gọn cho bốn bạn. Dùng phấn vẽ trên sân bốn làn song song, đánh số làn 1, 2, 3, 4 từ trái sang phải. Vẽ năm "ô gặp nhau" theo ba tầng:

• Tầng 1: một ô nối làn 1 với làn 2, một ô nối làn 3 với làn 4.
• Tầng 2: một ô nối làn 1 với làn 3, một ô nối làn 2 với làn 4.
• Tầng 3: một ô nối làn 2 với làn 3.

Bốn bạn cầm thẻ số, mỗi bạn đứng đầu một làn theo thứ tự bất kỳ, rồi cùng đi tới. Tới ô gặp nhau, hai bạn so số: bạn số nhỏ hơn đi tiếp sang làn có số thứ tự nhỏ hơn, bạn số lớn hơn sang làn còn lại. Tới cuối, bốn bạn luôn đứng đúng thứ tự từ nhỏ tới lớn, dù xuất phát thế nào. Hãy thử hết các cách xuất phát mà các bạn nghĩ ra. Điều đặc biệt là ở tầng 1 và tầng 2, hai cặp so cùng lúc. Máy tính có nhiều bộ xử lý cũng tận dụng việc làm song song như thế.

Hoạt động 3: trộn hai chồng thẻ

Ngồi tại bàn, chia một bộ 16 thẻ số làm đôi. Hai bạn mỗi người tự xếp nửa của mình theo thứ tự. Bạn thứ ba ghép hai chồng: lật hai thẻ trên cùng, lấy thẻ nhỏ hơn đặt xuống chồng mới, lặp lại. Đếm xem ghép mất bao nhiêu lần so, rồi so với lúc một người tự xếp cả 16 thẻ.

Câu hỏi thường gặp

Thuật toán sắp xếp là gì?

Thuật toán sắp xếp là một cách làm từng bước để đưa một danh sách về đúng thứ tự, ví dụ số từ nhỏ đến lớn hay tên theo bảng chữ cái. Các cách phổ biến gồm sắp xếp nổi bọt, chọn, chèn và trộn. Chúng khác nhau ở số lần phải so sánh và đổi chỗ.

Sắp xếp nổi bọt là gì?

Sắp xếp nổi bọt là cách đi dọc danh sách, so từng cặp đứng cạnh nhau và đổi chỗ nếu sai thứ tự. Sau mỗi lượt, phần tử lớn nhất còn lại trôi về cuối, giống bọt nổi lên mặt nước. Cách này dễ hiểu nhưng chậm với danh sách dài.

Thuật toán sắp xếp nào nhanh nhất?

Không có cách nào nhanh nhất trong mọi trường hợp. Với danh sách dài, các cách chia đôi như sắp xếp trộn nhanh hơn rất nhiều so với nổi bọt. Với danh sách ngắn hoặc gần đúng thứ tự, sắp xếp chèn lại thường làm tốt. Nhiều chương trình thật kết hợp vài cách.

Làm sao dạy thuật toán sắp xếp cho học sinh không cần máy tính?

Cho học sinh cầm thẻ số và tự đứng thành hàng, mỗi lần chỉ được so hai người với nhau. Thử lần lượt từng cách và đếm số lần so. Mạng sắp xếp vẽ bằng phấn trên sân cũng là hoạt động được nhiều thầy cô dùng.