[toc:ul] 

BÀI 4: SẮP XẾP NỔI BỌT

1. Ý TƯỞNG SẮP XẾP BẰNG CÁCH ĐỔI CHỖ CÁC PHẦN TỬ LIỀN KỀ

- Ví dụ: Cho dãy 5 hộp kẹo với số lượng kẹo trong mỗi hộp khác nhau, tương ứng là:

- Minh họa ý tưởng:

- Giải thích:

+ Ở lượt thứ nhất, so sánh hai hộp đầu tiên, nếu số kẹo ở hộp đứng trước lớn hơn số kẹp ở hộp đứng sau thì đổi vị trí hai hộp này cho nhau. Tiếp tục như vậy cho đến hết dãy là hết một lượt => ta thu được hộp cuối là hộp chứa nhiều kẹo nhất

+ Tiếp tục các lượt thứ hai, thứ ba theo cách trên, cứ lặp lại như vậy cho đến khi gặp một lượt mà suốt cả lượt đó robot không phải đổi chỗ hai hộp nào thì dãy đã được sắp xếp xong.

2. THUẬT TOÁN SẮP XẾP NỔI BỌT 

- Xuất phát từ đầu dãy, i = 1, xét cặp (a₁, a₂), nếu a₁ > a₂ (trái thứ tự mong muốn) thì đổi chỗ cho nhau; trái lại không cần làm gì.

- Dịch sang phải một vị trí, xét cặp (a₂, a₃); so sánh và đổi chỗ nếu cần

- Quá trình tiếp tục, dịch sang phải một vị trí, xét cặp (a_i+1, a_i+2) so sánh và đổi chỗ nếu cần.

- Khi hết dãy thì xong một lượt xét các cặp số kề nhau để đổi chỗ.

- Thực hiện nhiều lượt như trên cho đến khi không còn bất kì cặp liền kề (a_i, a_i+1) nào trái thứ tự mong muốn, ta được dãy đã sắp xếp.

Chú ý:

- Sau lượt đổi chỗ thứ nhất, giá trị lớn nhất của dãy số đã ở cuối dãy, đúng vị trí cuối cùng của nó

- Chỉ một lượt đổi chỗ chưa đảm bảo dãy có thứ tự tăng dần