Sắp xếp chèn

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Sắp xếp chèn
Insertion-sort-example-300px.gif
Thông tin chung
Phân loại: Sắp xếp chèn
Cấu trúc dữ liệu: Cấu trúc dữ liệu mảng
Phức tạp thời gian: О(n2)
Phức tạp dữ liệu: О(n) tổng, O(1) phụ
Tối ưu: Không có

Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp bắt chước cách sắp xếp quân bài của những người chơi bài. Muốn sắp một bộ bài theo trật tự người chơi bài rút lần lượt từ quân thứ 2, so với các quân đứng trước nó để chèn vào vị trí thích hợp.

Thuật toán[sửa | sửa mã nguồn]

Cơ sở lập luận của sắp xếp chèn có thể mô tả như sau: Xét danh sách con gồm k phần tử đầu a_1,...,a_{k}. Với k = 1, danh sách gồm một phần tử đã được sắp. Giả sử trong danh sách k-1 phần tử đầu a_1,...,a_{k-1} đã được sắp. Để sắp xếp phần tử a_k=x ta tìm vị trí thích hợp của nó trong dãy a_1,...,a_{k-1}. Vị trí thích hợp đó là đứng trước phần tử lớn hơn nó và sau phần tử nhỏ hơn hoặc bằng nó.

Các phần tử ≤x Vị trí thích hợp Các phần tử>x Các phần tử chưa sắp
a_1 ... a_{i-1} x a_{i+1} ... a_{k-1} a_{k+1} ... a_n

Ví dụ[sửa | sửa mã nguồn]

Cho danh sách

1 3 7 - 6 4 2 5

Danh sách con gồm 3 phần tử bên trái 1,3,7 đã được sắp. Để tiếp tục sắp xếp phần tử thứ tư a_4=6 vào danh sách con đó, ta tìm vị trí thích hợp của nó là sau 3 và trước 7.

1 3 6 7 - 4 2 5

Làm tiếp theo với a_5=4 ta được

1 3 4 6 7 - 2 5

Làm tiếp theo với a_6=2 ta được

1 2 3 4 6 7 - 5

Cuối cùng chèn a_7=5

1 2 3 4 5 6 7 -

Giải thuật[sửa | sửa mã nguồn]

  • Danh sách a bắt đầu từ chỉ số 1 tới length
 Procedure insert (array a, int k, value) {
      int i:= k-1;
     while (i > 0 and a[i] > value) {
         a[i+1]:= a[i];
         i:= i - 1;
     }
     a[i+1]:= value;
 }
 Procedure InsertSort (array a, int length) {
     int k:= 2;
     while (k <= length) {
         insert(a, k, a[k]);
         k:= k + 1;
     }
 }

Đánh giá[sửa | sửa mã nguồn]

  • Thuật toán sử dụng trung bình n2/4 phép so sánh và n2/4 lần hoán vị, n2/2 phép so sánh và n2/2 lần hoán vị trong trường hợp xấu nhất, n-1 phép so sánh và 0 lần hoán vị trong trường hợp tốt nhất.
  • Thuật toán thích hợp đối với mảng đã được sắp xếp một phần hoặc mảng có kích thước nhỏ.

Xem thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

Liên kết[sửa | sửa mã nguồn]