Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 28
I X = 25 J
M: 3 5 10 15 20 25 25 30 55 45

I X = 25
M: 3 5 10 15 20 25 25 30 55 45
J
First X = 25 I Last
M: 3 5 10 15 20 25 25 30 55 45
J
Phân hoạch các phần tử trong dãy con từ First -> J:
First = 5 Last = J = 6 X = M[(5+6)/2] = M[5] = 20
First Last
M: 3 5 10 15 20 25 25 30 55 45
X = 20
Phân hoạch:
I J
M: 3 5 10 15 20 25 25 30 55 45
X = 20
I≡J
M: 3 5 10 15 20 25 25 30 55 45
X = 20
J I
M: 3 5 10 15 20 25 25 30 55 45
X = 20
First J I Last
M: 3 5 10 15 20 25 25 30 55 45

Phân hoạch các phần tử trong dãy con từ I -> Last:
First = I = 7 Last = 10 X = M[(7+10)/2] = M[8] = 30

w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

V

First≡J I Last
M: 3 5 10 15 20 25 25 30 55 45
X = 30
Phân hoạch các phần tử trong dãy con từ I -> Last:
First = I = 9 Last = 10 X = M[(9+10)/2] = M[9] = 55
First Last
M: 3 5 10 15 20 25 25 30 55 45
X = 55
Phân hoạch:
I J
M: 3 5 10 15 20 25 25 30 55 45
X = 55
J I
M: 3 5 10 15 20 25 25 30 45 55
X = 55

M: 3 5 10 15 20 25 25 30 45 55

Toàn bộ quá trình phân hoạch kết thúc, dãy M trở thành:
M: 3 5 10 15 20 25 25 30 45 55

- Phân tích thuật toán:
+ Trường hợp tốt nhất, khi mảng M ban đầu đã có thứ tự tăng:
Số phép gán: Gmin = 1 + 2 + 4 + … + 2^[Log
2
(N) – 1] = N-1
Số phép so sánh: Smin = N×Log
2
(N)/2
Số phép hoán vò: Hmin = 0

e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D
F
-
X
C
h
a
n

3.2.2. Sắp xếp bằng phương pháp chọn (Selection Sort)
Các thuật toán trong phần này sẽ tìm cách lựa chọn các phần tử thỏa mãn điều kiện
chọn lựa để đưa về đúng vò trí của phần tử đó, cuối cùng tất cả các phần tử trong
mảng M đều về đúng vò trí.
Các thuật toán sắp xếp bằng phương pháp chọn bao gồm:
- Thuật toán sắp xếp chọn trực tiếp (straight selection sort),
- Thuật toán sắp xếp dựa trên khối/heap hay sắp xếp trên cây (heap sort).
Ở đây chúng ta chỉ trình bày thuật toán sắp xếp chọn trực tiếp
Thuật toán sắp xếp chọn trực tiếp (Straight Selection Sort):
- Tư tưởng:
+ Ban đầu dãy có N phần tử chưa có thứ tự. Ta chọn phần tử có giá trò nhỏ nhất
trong N phần tử chưa có thứ tự này để đưa lên đầu nhóm N phần tử.
+ Sau lần thứ nhất chọn lựa phần tử nhỏ nhất và đưa lên đầu nhóm chúng ta còn lại
N-1 phần tử đứng ở phía sau dãy M chưa có thứ tự. Chúng ta tiếp tục chọn phần
tử có giá trò nhỏ nhất trong N-1 phần tử chưa có thứ tự này để đưa lên đầu nhóm
N-1 phần tử. …. Do vậy, sau N–1 lần chọn lựa phần tử nhỏ nhất để đưa lên đầu
nhóm thì tất cả các phần tử trong dãy M sẽ có thứ tự tăng.
+ Như vậy, thuật toán này chủ yếu chúng ta đi tìm giá trò nhỏ nhất trong nhóm N-K
phần tử chưa có thứ tự đứng ở phía sau dãy M. Việc này đơn giản chúng ta vận
dụng thuật toán tìm kiếm tuần tự.
- Thuật toán:
B1: K = 0
B2: IF (K = N-1)
Thực hiện Bkt
B3: Min = M[K+1]
B4: PosMin = K+1
B5: Pos = K+2
B6: IF (Pos > N)
Thực hiện B8
B7: ELSE

w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

tăng dựa trên thuật toán sắp xếp chọn trực tiếp. Nội dung của hàm như sau:
void SelectionSort(T M[], int N)
{ int K = 0, PosMin;
while (K < N-1)
{ T Min = M[K];
PosMin = K;
for (int Pos = K+1; Pos < N; Pos++)
if (Min > M[Pos])
{ Min = M[Pos];
PosMin = Pos
}
Swap(M[K], M[PosMin]);
K++;
}
return;
}
- Ví dụ minh họa thuật toán:
Giả sử ta cần sắp xếp mảng M có 10 phần tử sau (N = 10):
M: 1 60 2 25 15 45 5 30 33 20
Ta sẽ thực hiện 9 lần chọn lựa (N - 1 = 10 - 1 = 9) phần tử nhỏ nhất để sắp xếp
mảng M:
Lần 1: Min = 1 PosMin = 1 K = 0
K+1
M: 1 60 2 25 15 45 5 30 33 20

Lần 2: Min = 2 PosMin = 3 K = 1
K+1
M:
1
60 2 25 15 45 5 30 33 20

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D
F
-
X

m
.
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 32
Lần 4: Min = 15 PosMin = 5 K = 3
K+1
M:
1 2 5
25 15 45 60 30 33 20

K+1
M:
1 2 5 15
25 45 60 30 33 20

Lần 5: Min = 20 PosMin = 10 K = 4
K+1
M:
1 2 5 15
25 45 60 30 33 20

K+1
M:
1 2 5 15 20
45 60 30 33 25

Lần 6: Min = 25 PosMin = 10 K = 5
K+1
M:
1 2 5 15 20

Lần 9: Min = 45 PosMin = 10 K = 8
K+1
M:
1 2 5 15 20 25 30 33
60 45
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.
d
o

r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
.