Sắp xếp chèn¶
Sắp xếp chèn là một thuật toán sắp xếp đơn giản, hoạt động tương tự như quy trình sắp xếp một bộ bài bằng tay.
Cụ thể, chúng ta chọn một phần tử cơ sở từ phần chưa được sắp xếp, so sánh lần lượt với các phần tử trong phần đã được sắp xếp ở bên trái nó, và chèn nó vào vị trí thích hợp.
Hình dưới đây minh họa cách một phần tử được chèn vào mảng. Giả sử phần tử cơ sở là base. Chúng ta cần dịch chuyển tất cả phần tử nằm giữa chỉ số mục tiêu và base sang phải một vị trí, sau đó gán base vào chỉ số mục tiêu.
Quy trình thuật toán¶
Quy trình tổng thể của sắp xếp chèn được thể hiện trong hình dưới đây.
- Ban đầu, phần tử đầu tiên của mảng đã được sắp xếp.
- Chọn phần tử thứ hai của mảng làm
base, sau khi chèn nó vào vị trí thích hợp, 2 phần tử đầu tiên của mảng đã được sắp xếp. - Chọn phần tử thứ ba làm
base, sau khi chèn nó vào vị trí thích hợp, 3 phần tử đầu tiên của mảng đã được sắp xếp. - Và cứ tiếp tục như vậy. Ở vòng cuối cùng, chọn phần tử cuối cùng làm
base, sau khi chèn nó vào vị trí thích hợp, tất cả phần tử đều đã được sắp xếp.
Mã nguồn ví dụ được hiển thị dưới đây:
Đặc điểm của thuật toán¶
- Độ phức tạp thời gian là \(O(n^2)\), sắp xếp thích ứng: Trong trường hợp xấu nhất, các thao tác chèn lần lượt yêu cầu \(n - 1\), \(n-2\), \(\dots\), \(2\), và \(1\) lần lặp, tổng cộng là \((n - 1) n / 2\), do đó độ phức tạp thời gian là \(O(n^2)\). Khi dữ liệu đã được sắp xếp, mỗi thao tác chèn sẽ kết thúc sớm. Khi mảng đầu vào đã được sắp xếp hoàn toàn, sắp xếp chèn đạt được độ phức tạp thời gian trong trường hợp tốt nhất là \(O(n)\).
- Độ phức tạp không gian là \(O(1)\), sắp xếp tại chỗ: Các con trỏ \(i\) và \(j\) sử dụng một lượng không gian bổ sung không đổi.
- Sắp xếp ổn định: Trong quá trình chèn, chúng ta đặt các phần tử sang bên phải của các phần tử có cùng giá trị, do đó thứ tự tương đối của chúng không thay đổi.
Ưu điểm của sắp xếp chèn¶
Độ phức tạp thời gian của sắp xếp chèn là \(O(n^2)\), trong khi độ phức tạp thời gian của sắp xếp nhanh (quick sort), thuật toán mà chúng ta sẽ tìm hiểu tiếp theo, là \(O(n \log n)\). Mặc dù sắp xếp chèn có độ phức tạp thời gian cao hơn, nhưng nó thường nhanh hơn trên các tập dữ liệu nhỏ.
Kết luận này tương tự như kết luận về thời điểm áp dụng tìm kiếm tuyến tính và tìm kiếm nhị phân. Các thuật toán như sắp xếp nhanh (quick sort), với độ phức tạp \(O(n \log n)\), là các thuật toán sắp xếp chia để trị và thường liên quan đến nhiều phép toán sơ cấp hơn. Khi tập dữ liệu nhỏ, các giá trị \(n^2\) và \(n \log n\) tương đối gần nhau, vì vậy độ phức tạp tiệm cận không đóng vai trò quyết định; thay vào đó, số lượng phép toán sơ cấp trong mỗi vòng trở thành yếu tố quyết định.
Trong thực tế, các hàm sắp xếp tích hợp của nhiều ngôn ngữ lập trình (như Java) sử dụng sắp xếp chèn. Ý tưởng chung là: đối với các mảng lớn, sử dụng thuật toán sắp xếp chia để trị như sắp xếp nhanh (quick sort); đối với các mảng ngắn, sử dụng trực tiếp sắp xếp chèn.
Mặc dù sắp xếp nổi bọt (bubble sort), sắp xếp chọn (selection sort) và sắp xếp chèn (insertion sort) đều có độ phức tạp thời gian là \(O(n^2)\), nhưng trong thực tế, sắp xếp chèn được sử dụng thường xuyên hơn đáng kể so với sắp xếp nổi bọt và sắp xếp chọn, chủ yếu vì những lý do sau.
- Sắp xếp nổi bọt được thực hiện thông qua hoán đổi phần tử, yêu cầu một biến tạm thời và liên quan đến 3 phép toán sơ cấp; trong khi sắp xếp chèn được thực hiện thông qua gán phần tử và chỉ yêu cầu 1 phép toán sơ cấp. Do đó, sắp xếp nổi bọt thường có chi phí tính toán cao hơn sắp xếp chèn.
- Sắp xếp chọn có độ phức tạp thời gian là \(O(n^2)\) trong mọi trường hợp. Nếu cho trước một tập dữ liệu được sắp xếp một phần, sắp xếp chèn thường hiệu quả hơn so với sắp xếp chọn.
- Sắp xếp chọn không ổn định và không thể áp dụng cho sắp xếp đa cấp.