/codegym.vn/ - 156
Bước 4: Danh sách con đã được sắp
xếp là {2, 4, 5, 9}. Chèn số 8 vào danh
sách con.
Bước 5: Danh sách con đã được sắp
xếp là {2, 4, 5, 8, 9}. Chèn số 1 vào danh
sách.
Bước 6: Danh sách con đã được sắp
xếp là {1, 2, 4, 5, 8, 9}. Chèn số 6 vào
danh sách.
Bước 7: Toàn bộ danh sách đã được
sắp xếp.
Quá trì chèn lần lượt các số vào đúng vị trí
Quá trình “chèn” được diễn ra bằng cách dịch chuyển các phần tử ở phía sau vị trí
muốn chèn để tạo một chỗ trống cho phần tử mới. Chẳng hạn như ở Bước 3 ở trên,
để chèn số 4 vào vị trí trước số 5 thì chúng ta phải dịch chuyển số 9 và số 9 về phía
sau để tạo một khoảng trống trước số 5.
Bước 1: Lưu giá trị 4 vào một biến tạm
Bước 2: Dịch chuyển phần tử ở vị trí
list[2] sang vị trí list[3].
Bước 3: Dịch chuyển phần tử ở vị trí
list[1] sang vị trí list[2].
Bước 4: Gán giá trị của biến tạm vào vị
trí list[1].
Quá trình dịch chuyển để chèn một phần tử vào đúng vị trí
Giải thuật
Từ mô tả trên ta đã có một bức tranh khái quát cho giải thuật sắp xếp chèn, chúng ta
sẽ có các bước cơ bản cho giải thuật như sau:
1.
for
(
let
i
=
1
;
i
<
list
.
length
;
i
++)
{
2. ch
è
n ph
ầ
n t
ử
list
[
i
]
v
à
o danh s
á
ch con list
[
0.
.
i
-
1
]
sao cho danh s
á
ch list
[
0.
.
i
]
lu
ô
n
đượ
c s
ắ
p x
ế
p
3.
}
Cài đặt thuật toán sắp xếp chèn
1.
function
insertionSort
(
items
)
{
