Trong thuật toán sắp xếp nổi bọt, khi nào hai phần từ liền kề được đổi 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ẹo ở hộp đứng sau thì đổi vị trí hai hộp này cho nhau. Tiếp tục làm như vậy với hộp thứ hai và thứ ba, với hộp thứ ba và thứ tư, … cho đến hết dãy hộp kẹo là hết một lượt.

Tiếp tục các lượt thứ hai, thứ ba theo cách như lượt thứ nhất, 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 cho hai hộp nào thì dãy đã được sắp xếp xong, robot kết thúc công việc.

Ta có dãy số: 5, 2, 4, 1, 3. Sắp xếp giảm dần.

Bước 1. So sánh số 5 và 2. Ta thấy số 5 lớn hơn 2. Nên ta giữ nguyên kết quả. Dãy số sau khi đổi: 5, 2, 4, 1, 3.

Bước 2. So sánh số 2 và 4. Ta thấy số 4 lớn hơn 2 và ta tiến hành đổi chỗ số 4 và 2. Dãy số sau khi đổi: 5, 4, 2, 1, 3.

Bước 3. So sánh số 2 và 1. Ta thấy số 2 lớn hơn 1, ta giữ nguyên dãy số: 5, 4, 2, 1, 3.

Bước 4. So sánh số 1 và 3, ta thấy số 3 lớn hơn số 1, ta tiến hành đổi chỗ số 3 và số 1. Dãy số sau khi đổi: 5, 4, 2, 3, 1.

Bước 5. Tiến hành duyệt dãy số một lần nữa để chắc chắn dãy số đã được sắp xếp giảm dần. So sánh số 5 và 4, số 5 lớn hơn 4 giữ nguyên, dãy thu được: 5, 4, 2, 3, 1.

Bước 6. So sánh số 4 và 2, số 4 lớn hơn 2 giữ nguyên.

Bước 7. So sánh số 2 và 3, số 3 lớn hơn số 2, ta tiến hành đổi vị trí số 2 và 3. Dãy số thu được: 5, 4, 3, 2, 1.

Bước 8. So sánh số 2 và 1, số 2 lớn hơn số 1, nên ta giữ nguyên.

Ta sẽ đi tám lượt đi thì thuật toán mới kết thúc.

Tổng số lần đổi vị trí phần tử là 3 lần.