Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2. Lặp lại quá trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.
Các bước tiến hành như sau:
Bước 1: i=1
Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n]
Bước 3: Hoán vị a[min] và a[i]
Bước 4: Nếu i<=n-1 thì i=i+1; Lặp lại bước 2
Ngược lại: Dừng. n-1 phần tử đã nằm đúng vị trí.
Ví dụ 1 thuật toán sắp xếp chọn
Ví dụ 2: Cho dãy a = (12,2,8,5,1,6,4,15)
12 2 8 5 1 6 4 15
Bước 1: 1 2 8 5 12 6 4 15
Bước 2: 1 2 8 5 12 6 4 15
Bước 3: 1 2 4 5 12 6 8 15
Bước 4: 1 2 4 5 12 6 8 15
Bước 5: 1 2 4 5 6 12 8 15
Bước 6: 1 2 4 5 6 8 12 15
Bước 7: 1 2 4 5 6 8 12 15
-
#include <iostream.h>
-
-
void
selectionSort
(
int
*
array,
int
length
)
//selection sort function
-
{
-
int
i,j,min,minat
;
-
for
(
i
=
0
;
i
<
(
length
–
1
)
;
i
++
)
-
{
-
minat
=
i
;
-
min
=
array
[
i
]
;
-
-
for
(
j
=
i
+
1
;
j
<
(
length
)
;
j
++
)
//select the min of the rest of array
-
{
-
if
(
min
>
array
[
j
]
)
//ascending order for descending reverse
-
{
-
minat
=
j
;
//the position of the min element
-
min
=
array
[
j
]
;
-
}
-
}
-
int
temp
=
array
[
i
]
;
-
array
[
i
]
=
array
[
minat
]
;
//swap
-
array
[
minat
]
=
temp
;
-
}
-
}
-
void
printElements
(
int
*
array,
int
length
)
//print array elements
-
{
-
int
i
=
0
;
-
for
(
i
=
0
;
i
<
10
;
i
++
)
-
cout
<<
array
[
i
]
<<
endl
;
arrayendl
-
}
-
-
-
void
main
(
)
-
{
-
-
int
a
[
]
=
{
9
,
6
,
5
,
23
,
2
,
6
,
2
,
7
,
1
,
8
}
;
// array to sort
-
selectionSort
(
a,
10
)
;
//call to selection sort
-
printElements
(
a,
10
)
;
// print elements
-
}
-
5.
6.Simple insertion sort.(Sắp xếp chèn)
7. Shell sort.
8.Merge sort. (Sắp xếp hòa nhập)
5. Heap sort. (Sắp xếp vun đống)
C++ Code:
