Các thuật toán $O(N^2)$ dễ cài đặt, trực quan, phù hợp với tập dữ liệu nhỏ ($N < 1000$).

1. Nổi bọt (Bubble Sort)

• Ý tưởng: Liên tục so sánh hai phần tử kề nhau, nếu sai thứ tự thì đổi chỗ. Qua mỗi vòng lặp lớn, phần tử lớn nhất sẽ "nổi" về đúng vị trí cuối mảng.

• Độ phức tạp: $O(N^2)$ xấu nhất và trung bình; $O(N)$ tốt nhất (khi mảng đã sắp xếp và có cờ hiệu kiểm tra).

2. Chọn (Selection Sort)

• Ý tưởng: Tìm phần tử nhỏ nhất trong đoạn chưa sắp xếp, đổi chỗ nó về vị trí đầu tiên của đoạn đó.

• Độ phức tạp: $O(N^2)$ trong mọi trường hợp (số phép so sánh luôn là $\frac{N(N-1)}{2}$).

3. Chèn (Insertion Sort)

• Ý tưởng: Giống như xếp bài tây trên tay. Lấy từng phần tử chèn vào đúng vị trí của dãy đã sắp xếp phía trước.

• Độ phức tạp: $O(N^2)$ xấu nhất; $O(N)$ tốt nhất (rất hiệu quả khi mảng gần như đã được sắp xếp sẵn).

# Cài đặt Insertion Sort - Thuật toán cơ bản hiệu quả nhất trong nhóm O(N^2)
def insertion_sort(arr: list) -> list:
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        # Dịch chuyển các phần tử lớn hơn key sang phải
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr