/codegym.vn/ - 158
Bước 5: Danh sách còn lại là {8, 9, 6}.
Tìm được phần tử nhỏ nhất là 6, hoán
đổi vị trí số 6 với số 8.
Bước 6: Danh sách còn lại là {9, 8}.
Tìm được phần tử nhỏ nhất là 8, hoán
đổi vị trí của số 8 và số 9.
Bước 7: Danh sách còn lại chỉ một phần
tử duy nhất là số 9.
Không cần thực hiện thêm thao tác nào
nữa. Danh sách đã được sắp xếp.
Quá trì sắp xếp chọn lần lượt các số vào đúng vị trí
Giải thuật
Từ mô tả ở trên, chúng ta có thể có một giải thuật cho thuật toán sắp xếp chọn như
sau:
1.
for
(
int
i
=
0
;
i
<
list
.
length
-
1
;
i
++)
{
2. t
ì
m ph
ầ
n t
ử
nh
ỏ
nh
ấ
t trong danh s
á
ch list
[
i
..
list
.
length
-
1
];
3. ho
á
n
đổ
i ph
ầ
n t
ử
nh
ỏ
nh
ấ
t v
ớ
i ph
ầ
n t
ử
list
[
i
]
n
ế
u c
ầ
n thi
ế
t
4.
// list[i] đã nằm đúng vị trí của nó.
5.
// lần lặp tiếp theo được thực hiện trong danh sách còn lại list[i+1..list.length-1]
6.
}
Cài đặt thuật toán sắp xếp chọn
1.
function
selectionSort
(
arr
)
{
2.
let
minIndex
,
temp
,
len
=
arr
.
length
;
3.
for
(
let
i
=
0
;
i
<
len
;
i
++)
{
4. minIndex
=
i
;
5.
// tìm index của giá trị nhỏ nhất
6.
for
(
let
j
=
i
+
1
;
j
<
len
;
j
++)
{
7.
if
(
arr
[
j
]
<
arr
[
minIndex
])
{
8. minIndex
=
j
;
9.
}
10.
}
11.
12.
// Đổi chỗ
13. temp
=
arr
[
i
];
14. arr
[
i
]
=
arr
[
minIndex
];
15. arr
[
minIndex
]
=
temp
;
16.
}
17.
return
arr
;
18.
}
