Sắp xếp chèn

6.1 Định nghĩa sắp xếp chèn

Sắp xếp chèn (Insertion Sort) — là thuật toán sắp xếp xây dựng một mảng (hoặc danh sách) đã được sắp xếp từng phần tử một. Nó lấy từng phần tử từ phần chưa sắp xếp và chèn chúng vào đúng vị trí trong phần đã sắp xếp.

Nguyên tắc hoạt động:

1. Bắt đầu với phần tử thứ hai của mảng (phần tử đầu tiên được coi là đã sắp xếp).
2. So sánh phần tử hiện tại với các phần tử trước đó và di chuyển nó sang trái cho đến khi tìm thấy vị trí phù hợp.
3. Lặp lại quá trình cho tất cả các phần tử trong mảng, chèn từng phần tử mới vào vị trí thích hợp trong phần đã sắp xếp của mảng.

Độ phức tạp thời gian và không gian của sắp xếp chèn

Độ phức tạp thời gian:

• Trong trường hợp xấu nhất: O(n^2) — xảy ra khi các phần tử ban đầu được sắp xếp theo thứ tự ngược lại.
• Trong trường hợp trung bình: O(n^2) — xảy ra khi các phần tử được sắp xếp ngẫu nhiên.
• Trong trường hợp tốt nhất: O(n) — xảy ra khi các phần tử đã được sắp xếp.

Độ phức tạp không gian:

O(1) — vì thuật toán sử dụng một lượng bộ nhớ bổ sung cố định (chỉ một vài biến để lưu trữ các giá trị tạm thời).

6.2 Phân tích hoạt động của thuật toán

Tại một bước của thuật toán, ta có tình huống như sau:

• Chúng ta có một phần tử hiện tại với chỉ số i.
• Tất cả các phần tử bên trái đã được sắp xếp từ nhỏ nhất đến lớn nhất.
• Chúng ta cố gắng chèn phần tử hiện tại vào phần đã sắp xếp của mảng sao cho thứ tự sắp xếp không bị phá vỡ.

Cố gắng chèn phần tử vào phần đã sắp xếp của mảng như sau:

1. Biến j trong vòng lặp có giá trị từ i - 1 đến 0.
2. Nếu phần tử hiện tại (phần tử thứ i) nhỏ hơn phần tử thứ j, thì ta dời giá trị của phần tử thứ j sang phải 1 vị trí.

Ví dụ: tình huống hiện tại:

• Các phần tử đã sắp xếp được đánh dấu màu xanh lá cây.
• Các phần tử chưa sắp xếp được đánh dấu màu hồng.
• Phần tử hiện tại ở chỉ số 5 — được đánh dấu màu nâu.

Chúng ta cố gắng tìm vị trí thích hợp cho phần tử hiện tại trong phần đã sắp xếp của mảng.

Bước 1 — nhớ giá trị của phần tử hiện tại vào biến key.

Bước 2 — phần tử No4 có lớn hơn key? (10 lớn hơn 5?) Khi đó di chuyển phần tử No4 sang phải:

Bước 3 — phần tử No3 có lớn hơn key? (8 lớn hơn 5?) Khi đó di chuyển phần tử No3 sang phải:

Bước 4 — phần tử No2 có lớn hơn key? (6 lớn hơn 5?) Khi đó di chuyển phần tử No2 sang phải:

Bước 5 — phần tử No1 có lớn hơn key? (4 lớn hơn 5?) Không. Khi đó lưu phần tử key vào vị trí của phần tử No2.

Sau khi đã chèn phần tử No5 vào vị trí cần thiết, chúng ta chuyển sang phần tử No6 và cố gắng tìm vị trí cho nó trong phần đã sắp xếp của mảng:

Sau đó lấy phần tử thứ bảy:

Sau đó phần tử thứ 8:

6.3 Triển khai thuật toán sắp xếp chèn

Đây là cách thuật toán này sẽ trông như thế nào trong Python:

def insertion_sort(arr):
    # Đi qua tất cả các phần tử của mảng, bắt đầu từ phần tử thứ hai
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Di chuyển các phần tử arr[0..i - 1] lớn hơn key lên một vị trí phía trước
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key  # Chèn key vào đúng vị trí
    return arr  # Trả về mảng đã sắp xếp
        
# Ví dụ sử dụng:
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Mảng đã sắp xếp:", sorted_arr)
# Kết quả: Mảng đã sắp xếp: [5, 6, 11, 12, 13]

Giải thích:

• Lưu phần tử hiện tại vào key
• Di chuyển tất cả các phần tử trong phần đã sắp xếp của mảng sang phải
• Chèn phần tử của chúng ta vào vị trí thích hợp

Ví dụ hoạt động của thuật toán

Lấy ví dụ mảng: [12, 11, 13, 5, 6]

1. Lần duyệt đầu tiên (i = 1):

• So sánh 11 và 12, di chuyển 12 sang phải.
• Mảng: [11, 12, 13, 5, 6]

2. Lần duyệt thứ hai (i = 2):

• 13 đã đúng vị trí.
• Mảng: [11, 12, 13, 5, 6]

3. Lần duyệt thứ ba (i = 3):

• So sánh 5 với 13, 12 và 11, di chuyển tất cả sang phải.
• Mảng: [5, 11, 12, 13, 6]

4. Lần duyệt thứ tư (i = 4):

• So sánh 6 với 13, 12 và 11, di chuyển tất cả sang phải.
• Mảng: [5, 6, 11, 12, 13]

Thuật toán hoàn thành vì tất cả các phần tử đã được sắp xếp.