Bài 16. Thuật toán sắp xếp

Sau bài học này em sẽ:

Có hai chất lỏng khác màu là xanh và đỏ, lần lượt được chứa trong hai chiếc cốc A và B (Hình 16.1a). Chúng ta cần đổi chỗ hai chất lỏng này, sao cho cốc A đựng chất lỏng màu đỏ, còn cốc B đựng chất lỏng màu xanh. Để thực hiện công việc này, chúng ta sử dụng thêm một chiếc cốc thứ ba (cốc C) không đựng gì. Em hãy quan sát Hình 16.1b, Hình 16.1c, Hình 16.1d để biết cách thực hiện.

Trong bài học trước, chúng ta đã biết sắp xếp giúp cho việc tìm kiếm được thực hiện dễ dàng. Trong cuộc sống hằng ngày, chúng ta thường xuyên phải thực việc sắp xếp các đồ vật để dễ tìm. Máy tính cũng thường xuyên phải thực hiện thuật toán sắp xếp khi người sử dụng yêu cầu. Ví dụ: Sắp xếp điểm trung bình của học sinh trong lớp bằng phần mềm bảng tính; Sắp xếp tên tệp trong thư mục,... Có nhiều thuật toán sắp xếp khác nhau. Một trong số đó là thuật toán sắp xếp nổi bọt. Giả sử ta cần phải sắp xếp dãy các số 4, 2, 3, 1 để thu được dãy có thứ tự tăng dần. Thuật toán sắp xếp nổi bọt xét từng vị trí từ đầu đến cuối dãy. Tại mỗi vị trí được xét, thuật toán tìm phần tử nhỏ nhất trong những phần tử phía sau để đưa vào vị trí đó. Việc này được thực hiện bằng một vòng lặp, so sánh từng cặp phần tử cạnh nhau và hoán đổi chúng nếu số ở phía sau nhỏ hơn. Các bước thực hiện được mô tả trong Hình 16.2, Hình 16.3, Hình 16.4. Việc hoán đổi được thực hiện giống như việc hoán đổi ở Hoạt động khởi động.

Xét vị trí đầu tiên, vòng lặp thứ nhất thực hiện như sau:

Xét vị trí thứ hai:

Xét vị trí thứ ba:

Sau vòng lặp thứ ba, không có bất kì sự hoán đổi nào được thực hiện nữa nên thuật toán dừng lại. Danh sách được sắp xếp theo đúng thứ tự yêu cầu.

Sắp xếp dãy số theo thứ tự tăng dần bằng thuật toán sắp xếp nổi bọt. 1. Với vị trí đầu tiên, em thực hiện một vòng lặp như sau: 1.1. So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên vị trí đầu tiên. 1.2. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đồi chỗ chúng cho nhau. 1.3. Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ nhất nổi lên vị trí đầu tiên. 2. Với vị trí thứ hai, em thực hiện một vòng lặp tương tự như trên. 2.1. So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên vị trí thứ hai. 2.2. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau. 2.3. Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ thứ nhì nổi lên vị trí thứ hai. 3. Tương tự như trên với các vị trí thứ ba, thứ tư,... đến vị trí trước vị trí cuối cùng. 4. Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến lớn.

Một thuật toán sắp xếp khác có tên là sắp xếp chọn. Thuật toán sắp xếp chọn xét từng vị trí và đưa phần tử nhỏ nhất trong những phần tử phía sau vào vị trí đó. Dưới đây mô tả một phương án của thuật toán sắp xếp chọn, trong đó việc tìm phần tử nhỏ nhất được thực hiện bằng cách so sánh trực tiếp phần tử ở vị trí được xét với những phần tử ở phía sau nó và hoán đổi nếu phần tử phía sau nhỏ hơn. Các bước thực hiện được minh hoạ trong Hình 16.5.

Giả sử ta cần phải sắp xếp dãy các số 3, 4, 1, 5, 2 để thu được dãy có thứ tự tăng dần.

Sắp xếp dãy số theo thứ tự từ nhỏ đến lớn bằng thuật toán sắp xếp chọn. 1. Với vị trí đầu tiên, em thực hiện một vòng lặp như sau: 1.1. So sánh từng phần tử (kể từ vị trí thứ hai đến vị trí cuối cùng) với phần tử tại vị trí đầu tiên. 1.2. Nếu phần tử được xét nhỏ hơn phần tử tại vị trí đầu tiên thì hoán đổi nó với phần tử tại vị trí đầu tiên. 1.3. Cuối vòng lặp, em sẽ nhận được dãy số với phần tử nhỏ nhất được đưa về vị trí đầu tiên. 2. Với vị trí thứ hai, em thực hiện một vòng lặp tương tự như trên. 2.1. So sánh từng phần tử (kể từ vị trí thứ ba đến vị trí cuối cùng) với phần tử tại vị trí thứ hai. 2.2. Nếu phần tử được xét nhỏ hơn phần tử tại vị trí thứ hai thì hoán đổi nó với phần tử tại vị trí thứ hai. 2.3. Cuối vòng lặp, em sẽ nhận được dãy số với phần tử nhỏ thứ nhì được đưa về vị trí thứ hai. 3. Tương tự như trên với các vị trí thứ ba, thứ tư,... đến vị trí trước vị trí cuối cùng. 4. Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến lớn.

Mô tả thuật toán sắp xếp nổi bọt bằng ngôn ngữ tự nhiên:
Sắp xếp dãy số theo thứ tự tăng dần bằng thuật toán sắp xếp nổi bọt.
1. Với vị trí đầu tiên, em thực hiện một vòng lặp như sau:
1.1. So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên vị trí đầu tiên.
1.2. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau.
1.3. Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ nhất nổi lên vị trí đầu tiên.
2. Với vị trí thứ hai, em thực hiện một vòng lặp tương tự như trên.
2.1. So sánh hai phần tử đứng cạnh nhau theo thứ tự từ cuối dãy lên vị trí thứ hai.
2.2. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước thì đổi chỗ chúng cho nhau.
2.3. Cuối vòng lặp em sẽ nhận được dãy số với phần tử nhỏ thứ nhì nổi lên vị trí thứ hai.
3. Tương tự như trên với các vị trí thứ ba, thứ tư ... đến vị trí trước vị trí cuối cùng.
4. Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến lớn.

tử nhỏ nhất được thực hiện bằng cách so sánh trực tiếp phần tử ở vị trí được xét với những phần tử ở phía sau nó và hoán đổi nếu phần tử phía sau nhỏ hơn. Các bước thực hiện được minh hoạ trong Hình 16.5.

Mô tả thuật toán sắp xếp chọn bằng ngôn ngữ tự nhiên:
Sắp xếp dãy số theo thứ tự từ nhỏ đến lớn bằng thuật toán sắp xếp chọn.
1. Với vị trí đầu tiên, em thực hiện một vòng lặp như sau:
1.1. So sánh từng phần tử (kể từ vị trí thứ hai đến vị trí cuối cùng) với phần tử tại vị trí đầu tiên.
1.2. Nếu phần tử được xét nhỏ hơn phần tử tại vị trí đầu tiên thì hoán đổi nó với phần tử tại vị trí đầu tiên.
1.3. Cuối vòng lặp, em sẽ nhận được dãy số với phần tử nhỏ nhất được đưa về vị trí đầu tiên.
2. Với vị trí thứ hai, em thực hiện một vòng lặp tương tự như trên.
2.1. So sánh từng phần tử (kể từ vị trí thứ ba đến vị trí cuối cùng) với phần tử tại vị trí thứ hai.
2.2. Nếu phần tử được xét nhỏ hơn phần tử tại vị trí thứ hai thì hoán đồi nó với phần tử tại vị trí thứ hai.
2.3. Cuối vòng lặp, em sẽ nhận được dãy số với phần tử nhỏ thứ nhì được đưa về vị trí thứ hai.
3. Tương tự như trên với các vị trí thứ ba, thứ tư,... đến vị trí trước vị trí cuối cùng.
4. Kết thúc, em sẽ nhận được dãy số đã được sắp xếp theo thứ tự từ nhỏ đến lớn.

Trong quá trình thực hiện cả hai thuật toán sắp xếp nổi bọt và sắp xếp chọn, ta đều thấy xuất hiện nhiều lần thuật toán đơn giản hơn: hoán đổi giá trị hai phần tử. Như vậy, bài toán sắp xếp đã được giải quyết dựa trên lời giải của bài toán nhỏ hơn là bài toán hoản đổi giá trị.
Xem xét thuật toán tìm kiếm nhị phân ở bài học trước, ta cũng nhận thấy thuật toán tìm kiếm nhị phân thực hiện chia bài toán thành những

bài toán nhỏ hơn. Trong đó, bài toán nhỏ hơn là một phần của bài toán ban đầu. Cụ thể, ở mỗi lần lặp, thuật toán tìm kiếm nhị phân đã thu hẹp vùng tìm kiếm chỉ còn một nửa.
Một cách khái quát, để giải quyết một bài toán, chúng ta đã dựa trên lời giải của bài toán nhỏ hơn. Việc chia một bài toán thành những bài toán nhỏ hơn giúp việc giải bài toán đó dễ dàng hơn, đồng thời việc mô tả thuật toán dễ hiểu và dễ thực hiện hơn.