The following is the main part of bubble sort pseudocode: do swapped := false for i := 0 to n-2 if a[i] > a[i+1] then swap(a[i],a[i+1]) swapped := true end if end for while swapped Consider the list of ten integers below: 6, 4, 9, 10, 2, 8, 1, 3, 7, 5 What is the list after the FIRST iteration (for i = 0 to n-2) in a bubble sort? (sorting from smallest to largest).

Đáp án đúng: "4, 6, 9, 2, 8, 1, 3, 7, 5, 10". Một lượt của vòng for chỉ so từng cặp kề nhau và đổi chỗ khi trái lớn hơn phải: 6 với 4 đổi thành 4, 6; 6 với 9 và 9 với 10 giữ nguyên; rồi 10 lớn hơn mọi số sau nó nên bị đẩy dần qua 2, 8, 1, 3, 7, 5 và nằm ở cuối, các số bị vượt lùi lên đúng một ô mà không đổi thứ tự tương đối. Vậy sau một lượt chỉ 6 và 4 hoán vị, còn 10 về cuối. "4, 6, 9, 8, 2, 1, 3, 7, 5, 10" sai vì nó đổi thêm 2 với 8, nhưng khi so cặp đó thì phần tử đang mang theo là 10 chứ không phải 8. "4, 6, 9, 1, 2, 8, 3, 7, 5, 10" sai vì nó đẩy 1 lên trước 2 và 8, một bước nhảy mà phép so cặp kề nhau không làm được trong một lượt. "4, 6, 9, 2, 8, 1, 3, 5, 7, 10" sai vì nó đổi thêm 7 với 5 ở gần cuối, trong khi cặp đang so lúc đó là 10 với 7 rồi 10 với 5.