Triển khai (phần 2)

Tình huống: Sắp xếp [5, 2, 9, 1, 5]

Bước 1: Trạng thái ban đầu

• Mảng ban đầu: [5, 2, 9, 1, 5]
• Hãy hình dung đây là bộ bài trên tay chúng ta (hoặc mảng số).

Bước 2: Phần tử đầu tiên (i=1, key=2)

• Chúng ta bắt đầu với lá bài thứ hai (phần tử): key = 2.
• So sánh 2 với 5 (phần tử duy nhất đã được sắp xếp đến lúc này).
• Vì 2 nhỏ hơn, chúng ta dịch 5 sang phải rồi chèn 2 vào vị trí đó.
• Mảng sau khi cập nhật: [2, 5, 9, 1, 5]

Bước 3: Phần tử thứ hai (i=2, key=9)

• Chuyển sang lá bài tiếp theo: key = 9.
• So sánh 9 với 5.
• Vì 9 lớn hơn nên không cần dịch.
• Mảng sau khi cập nhật: [2, 5, 9, 1, 5] (không thay đổi)

Bước 4: Phần tử thứ ba (i=3, key=1)

• Chuyển sang lá bài tiếp theo: key = 1.
• So sánh 1 với 9, rồi với 5.
• Dịch 9 và 5 sang phải để tạo chỗ cho 1.
• Mảng sau khi cập nhật: [1, 2, 5, 9, 5]

Bước 5: Phần tử thứ tư (i=4, key=5)

• Chuyển sang lá bài tiếp theo: key = 5.
• So sánh 5 với 9.
• Vì 5 nhỏ hơn nên không cần dịch.
• Mảng sau khi cập nhật: [1, 2, 5, 9, 5] (không thay đổi)

Bước 6: Phần tử thứ năm (i=5, key=5)

• Chuyển đến lá bài cuối cùng: key = 5.
• So sánh 5 với 9.
• Vì 5 nhỏ hơn nên không cần dịch.
• Mảng sau khi cập nhật: [1, 2, 5, 5, 9]

Kết quả cuối cùng:

• Mảng đã sắp xếp: [1, 2, 5, 5, 9]

Ở mỗi bước, chúng ta chọn một lá bài (phần tử), so sánh nó với những phần tử đã được sắp xếp rồi đặt nó vào đúng vị trí, đồng thời dịch các phần tử khác nếu cần. Chúng ta lặp lại quá trình này cho đến khi toàn bộ mảng được sắp xếp.