/codegym.vn/ - 157
2.
for
(
let
i
=
1
;
i
<
items
.
length
;
i
++)
{
3.
let
current
=
items
[
i
];
4.
let
j
=
i
-
1
;
5.
6.
while
(
j
>=
0
&&
items
[
j
]
>
current
)
{
7. items
[
j
+
1
]
=
items
[
j
];
8. j
--;
9.
}
10. items
[
j
+
1
]
=
current
;
11.
}
12.
return
items
;
13.
}
5. Thuật toán sắp xếp chọn
Ý tưởng
Chẳng hạn, nếu chúng ta muốn sắp xếp một danh sách theo trật tự tăng dần. Chúng
ta sẽ tìm ra phần tử nhỏ nhất trong danh sách, rồi đưa phần tử đó về vị trí đầu tiên.
Sau đó, chúng ta tìm phần tử nhỏ nhất trong danh sách còn lại (trừ phần tử đầu tiên
trước đó) và đưa nó về vị trí đầu tiên trong danh sách còn lại đó, cứ như thế cho đến
phần tử cuối cùng.
Ví dụ: Để sắp xếp danh sách các số {2, 9, 5, 4, 8, 1, 6} sử dụng thuật toán sắp xếp
chọn, chúng ta sẽ tiến hành các bước như sau:
Bước 1: Tìm được phần tử nhỏ nhất
trong danh sách đó là 1. Hoán đổi vị trí
của số 1 cho số 2 (nằm ở vị trí đầu tiên).
Bước 2: Danh sách còn lại là {9, 5, 4, 8,
2, 6}, loại trừ số 1 vì nó đã được sắp xếp.
Tìm được phần tử nhỏ nhất là 2, hoán
đổi vị trí của số 2 với số 9 (nằm ở vị trí
đầu tiên của danh sách còn lại).
Bước 3: Danh sách còn lại là {5, 4, 8, 9,
6}.
Tìm được phần tử nhỏ nhất là 4, hoán
đổi vị trí của số 4 với số 5.
Bước 4: Danh sách còn lại là {5, 8, 9, 6}.
Tìm được phần tử nhỏ nhất là 5, nhưng
không cần hoán đổi vì nó đã nằm ở vị trí
đầu tiên.
