Sắp xếp chèn
Sắp xếp chèn là cách hầu hết mọi người xếp bài trên tay: rút lá kế tiếp và chèn nó vào đúng chỗ giữa những lá đã theo thứ tự. Thuật toán chậm với danh sách ngẫu nhiên dài, nhưng rất nhanh với danh sách ngắn hoặc gần như đã sắp xếp, vì vậy các thư viện sắp xếp thực tế vẫn dùng nó.
Ý tưởng
Giữ cho phần đầu danh sách luôn được sắp xếp. Lúc đầu, phần đã sắp xếp chỉ là giá trị đầu tiên. Lấy giá trị kế tiếp và so sánh với giá trị đứng trước nó. Nếu giá trị đó lớn hơn, hoán đổi chúng rồi so sánh tiếp, lùi thêm một vị trí. Dừng khi giá trị đứng trước không lớn hơn, hoặc khi giá trị đã lên đến đầu. Phần đã sắp xếp đã dài thêm một. Lặp lại với mọi giá trị cho đến cuối.
Ví dụ
Lấy 5, 1, 4, 2, 8. Lượt 1 lấy 1: 5 lớn hơn nên hoán đổi, và 1 lên đến đầu: 1, 5, 4, 2, 8. Lượt 2 lấy 4: hoán đổi với 5, rồi dừng ở 1: 1, 4, 5, 2, 8. Lượt 3 lấy 2: hoán đổi với 5 và với 4, rồi dừng ở 1: 1, 2, 4, 5, 8. Lượt 4 lấy 8, vốn đã lớn hơn 5, nên một phép so sánh là đủ. Tổng cộng 7 phép so sánh và 4 lần hoán đổi. Trên cùng danh sách này, sắp xếp nổi bọt cần 9 phép so sánh, sắp xếp chọn cần 10.
Số hoán đổi bằng số nghịch thế
Nghịch thế là một cặp giá trị sai thứ tự. Hoán đổi hai phần tử kề nhau đang sai thứ tự sẽ xóa đúng một nghịch thế, và sắp xếp chèn chỉ hoán đổi những cặp kề nhau như vậy. Vì thế số lần hoán đổi đúng bằng số nghịch thế của danh sách ban đầu, giống như sắp xếp nổi bọt. Mỗi lượt cũng có tối đa một phép so sánh không dẫn đến hoán đổi, chính là phép làm lượt dừng lại. Vậy số phép so sánh bằng số nghịch thế cộng tối đa n − 1.
Thích ứng: nhanh khi danh sách gần như đã sắp xếp
Vì khối lượng công việc bằng số nghịch thế cộng khoảng n, sắp xếp chèn nhanh mỗi khi có ít nghịch thế. Danh sách đã sắp xếp cần n − 1 phép so sánh và không có hoán đổi. Danh sách mà mỗi giá trị chỉ cách đúng chỗ vài vị trí mất thời gian gần bằng n. Chỉ danh sách còn xa mới được sắp xếp, như danh sách đảo ngược với n(n − 1)/2 nghịch thế, mới mất thời gian tỉ lệ với n². Với danh sách ngẫu nhiên, trung bình cần khoảng n²/4 lần hoán đổi.
Được dùng ở đâu
Sắp xếp chèn ổn định, không cần thêm bộ nhớ và có chi phí phụ rất nhỏ. Với danh sách ngắn, nó nhanh hơn cả những thuật toán nhanh hơn trên lý thuyết. Nhiều hàm sắp xếp trong thư viện, như Timsort trong Python và Java hay introsort dùng trong C++, chuyển sang sắp xếp chèn cho các đoạn nhỏ của danh sách, thường tối đa vài chục giá trị. Nó cũng hợp với dữ liệu đến từng giá trị một, vì mỗi giá trị mới có thể được chèn ngay khi đến.
Khám phá
Mở ứng dụng và nhấn Phát, hoặc nhấn Bước để đi từng phép so sánh. Giá trị đang được chèn có màu riêng, giá trị đang so sánh với nó được tô sáng, và phần đã sắp xếp có màu xanh lá. Khác với sắp xếp nổi bọt và sắp xếp chọn, phần màu xanh chưa phải cuối cùng: một giá trị nhỏ hơn đến sau vẫn có thể chen vào. Hãy thử một danh sách gần như đã sắp xếp để thấy các lượt ngắn thế nào, rồi thử một danh sách đảo ngược.
Câu hỏi thường gặp
Độ phức tạp thời gian của sắp xếp chèn là bao nhiêu?
O(n²) trong trường hợp xấu nhất và trung bình, O(n) trong trường hợp tốt nhất, khi danh sách đã được sắp xếp. Chính xác hơn, thời gian tỉ lệ với n cộng số nghịch thế. Nó chỉ cần thêm O(1) bộ nhớ.
Sắp xếp chèn và sắp xếp chọn khác nhau thế nào?
Sắp xếp chọn quét toàn bộ phần chưa sắp xếp để tìm giá trị nhỏ nhất, nên luôn thực hiện n(n − 1)/2 phép so sánh nhưng ít hoán đổi. Sắp xếp chèn lấy giá trị kế tiếp theo thứ tự và chỉ lùi nó xa đến mức cần thiết, nên ít phép so sánh hơn, nhất là với danh sách gần như đã sắp xếp, nhưng nhiều hoán đổi hơn.
Sắp xếp chèn nhị phân là gì?
Là một biến thể tìm vị trí cho giá trị mới bằng tìm kiếm nhị phân trong phần đã sắp xếp, chỉ cần khoảng log n phép so sánh thay vì tối đa n. Các giá trị vẫn phải được dịch để lấy chỗ, nên số lần di chuyển và trường hợp xấu nhất O(n²) vẫn như cũ.
Sắp xếp chèn có ổn định không?
Có. Một giá trị chỉ lùi qua các giá trị lớn hơn hẳn, nên các giá trị bằng nhau giữ nguyên thứ tự ban đầu.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Thử sắp xếp chèn