[Mỗi ngày 1 thuật toán] Thuật toán sắp xếp chèn – Insertion Sort

Nối tiếp thành công của bài viết đầu tiên, trong chuỗi bài “Mỗi ngày 1 thuật toán”, mang tên: Thuật toán sắp xếp nổi bọt. Hôm nay, CodeGym sẽ mang đến cho bạn những hướng dẫn chi tiết về Thuật toán sắp xếp chèn, bằng các mã nguồn Java, PHP và Python.

1. Ý tưởng chính của Thuật toán sắp xếp chèn

• Chia mảng thành hai phần: phần đã sắp xếp và phần chưa sắp xếp.
• Lần lượt lấy từng phần tử từ phần chưa sắp xếp và chèn vào vị trí thích hợp trong phần đã sắp xếp.

Cụ thể, thuật toán sẽ lặp qua từng phần tử của mảng, bắt đầu từ phần tử thứ hai. Với mỗi phần tử, nó sẽ so sánh và chèn phần tử đó vào vị trí thích hợp trong phần đã sắp xếp (các phần tử từ đầu mảng đến phần tử trước đó).

2. Quá trình diễn ra chi tiết của Thuật toán sắp xếp chèn

• Lấy phần tử đầu tiên làm phần đã sắp xếp, phần còn lại là phần chưa sắp xếp. 
• Lặp qua các phần tử trong phần chưa sắp xếp:
  • Lấy phần tử đầu tiên trong phần chưa sắp xếp.
  • So sánh và chèn phần tử đó vào vị trí thích hợp trong phần đã sắp xếp.
  • Cập nhật phần đã sắp xếp và phần chưa sắp xếp.
• Lặp lại bước 2 cho đến khi phần chưa sắp xếp trống.

3. Ví dụ minh hoạ cho Thuật toán sắp xếp chèn

Cho mảng: [5, 2, 4, 6, 1, 3]

• Bước 1: Xét phần tử đầu tiên 5, vì đây là phần tử duy nhất nên không cần sắp xếp.
• Bước 2: Xét phần tử thứ hai 2, chèn 2 vào trước 5. Lúc này ta được: [2, 5, 4, 6, 1, 3]
• Bước 3: Xét phần tử thứ ba 4, chèn 4 vào giữa 2 và 5. Lúc này ta được: [2, 4, 5, 6, 1, 3]
• Bước 4: Xét phần tử thứ tư 6, giữ nguyên vị trí. Lúc này ta được: [2, 4, 5, 6, 1, 3]
• Bước 5: Xét phần tử thứ năm 1, chèn 1 vào đầu mảng. Lúc này ta được: [1, 2, 4, 5, 6, 3]
• Bước 6: Xét phần tử thứ sáu 3, chèn 3 vào giữa 2 và 4. Lúc này ta được: [1, 2, 3, 4, 5, 6]

Như vậy, mảng đã được sắp xếp theo thứ tự tăng dần.

4. Hình ảnh minh hoạ cho Thuật toán sắp xếp chèn

5. Pseudo code 

6. Mã nguồn trong Java

7. Mã nguồn trong PHP

8. Mã nguồn trong Python

Xem thêm các bài viết thú vị về Thuật toán tại đây!