Lý thuyết bài học SVIP

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 hoạ:

- 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

Ở mỗi lượt robot thực hiện

- 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.

➩ Kết luận: Thuật toán sắp xếp nổi bọt thực hiện nhiều lượt so sánh và đổi chỗ các cặp phần tử liền kề cho đến khi không còn bất kì cặp phần tử liền kề (a_i, a_i+1) nào trái thứ tự mong muốn.