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. Cơ sở lập ...
(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.
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 a1,...,ak. 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 a1,...,ak − 1 đã được sắp. Để sắp xếp phần tử ak = x ta tìm vị trí thích hợp của nó trong dãy a1,...,ak − 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ó.
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ư a4 = 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 a5 = 4 ta được
| 1 | 3 | 4 | 6 | 7 | - | 2 | 5 |
Làm tiếp theo với a6 = 2 ta được
| 1 | 2 | 3 | 4 | 6 | 7 | - | 5 |
Cuối cùng chèn a7 = 5
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | - |
- 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;
}
}
- Sắp xếp nổi bọt
- Sắp xếp chọn
- Sắp xếp vun đống
- Sắp xếp nhanh
- Sắp xếp trộn
