Thuật toá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 {\displaystyle 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 {\displaystyle a_{1},…,a_{k-1}} đã được sắp. Để sắp xếp phần tử a k = x {\displaystyle a_{k}=x} ta tìm vị trí thích hợp của nó trong dãy a 1 , . . . , a k − 1 {\displaystyle 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ử ≤xVị trí thích hợpCác phần tử>xCác phần tử chưa sắp
a 1 {\displaystyle a_{1}}
…
a i − 1 {\displaystyle a_{i-1}}
x
a i + 1 {\displaystyle a_{i+1}}
…
a k − 1 {\displaystyle a_{k-1}}
a k + 1 {\displaystyle a_{k+1}}
…
a n {\displaystyle a_{n}}
Ví dụ
Cho danh sách
137-6425
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 {\displaystyle 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.
1367-425
Làm tiếp theo với a 5 = 4 {\displaystyle a_{5}=4} ta được
13467-25
Làm tiếp theo với a 6 = 2 {\displaystyle a_{6}=2} ta được
123467-5
Cuối cùng chèn a 7 = 5 {\displaystyle a_{7}=5}
1234567-
Giải thuật
- 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; }}
// Mã giả viết bằng ngôn ngữ C++
void InsertSort (int a[],int n){ int t,j; for(int i=1;i<n;i++) { j=i-1; t=a[i]; while(j >= 0 && t < a[j]) { a[j+1]=a[j]; j--; } a[j+1]=t; // Chèn } }
Đánh giá
- 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
Tham khảo
Liên kết