Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật
Trang: 23
Lần 7: First = 7
J: 8 9 10
M:
2

5

10

10

15

20

22
25 30 35
Lần 8: First = 8
J: 9 10
M:
2

5

10

10

15

- Phân tích thuật toán:
+ Trong mọi trường hợp:
Số phép gán: G = 0
Số phép so sánh: S = (N-1) + (N-2) + … + 1 = ½N(N-1)
+ Trong trường hợp tốt nhất: khi mảng ban đầu đã có thứ tự tăng
Số phép hoán vò: Hmin = 0
+ Trong trường hợp xấu nhất: khi mảng ban đầu đã có thứ tự giảm
Số phép hoán vò: Hmin = (N-1) + (N-2) + … + 1 = ½N(N-1)
+ Số phép hoán vò trung bình: Havg = ¼N(N-1)
- Nhận xét về thuật toán nổi bọt:
+ Thuật toán sắp xếp nổi bọt khá đơn giản, dễ hiểu và dễ cài đặt.
+ Trong thuật toán sắp xếp nổi bọt, mỗi lần đi từ cuối mảng về đầu mảng thì phần tử
nhẹ được trồi lên rất nhanh trong khi đó phần tử nặng lại “chìm” xuống khá chậm
chạp do không tận dụng được chiều đi xuống (chiều từ đầu mảng về cuối mảng).
+ Thuật toán nổi bọt không phát hiện ra được các đoạn phần tử nằm hai đầu của
mảng đã nằm đúng vò trí để có thể giảm bớt quãng đường đi trong mỗi lần đi.
b. Thuật toán sắp xếp dựa trên sự phân hoạch (Partitioning Sort):
Thuật toán sắp xếp dựa trên sự phân hoạch còn được gọi là thuật toán sắp xếp
nhanh (Quick Sort).
- Tư tưởng:
+ Phân hoạch dãy M thành 03 dãy con có thứ tự tương đối thỏa mãn điều kiện:
Dãy con thứ nhất (đầu dãy M) gồm các phần tử có giá trò nhỏ hơn giá trò trung
bình của dãy M,
Click to buy NOW!
P
D
F
-
X
C

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
c
u
-
t
r

B3: IF (First ≥ Last) //Dãy con chỉ còn không quá 01 phần tử
Thực hiện Bkt
B4: X = M[(First+Last)/2] //Lấy giá trò phần tử giữa
B5: I = First //Xuất phát từ đầu dãy 1 để tìm phần tử có giá trò > X
B6: IF (M[I] > X)
Thực hiện B8
B7: ELSE
B7.1: I++
B7.2: Lặp lại B6
B8: J = Last //Xuất phát từ cuối dãy 3 để tìm phần tử có giá trò < X
B9: IF (M[J] < X)
Thực hiện B11
B10: ELSE
B10.1: J
B10.2: Lặp lại B9
B11: IF (I ≤ J)
B11.1: Hoán_Vò(M[I], M[J])
B11.2: I++
B11.3: J
B11.4: Lặp lại B6
B12: ELSE
B12.1: Phân hoạch đệ quy dãy con từ phần tử thứ First đến phần tử thứ J
B12.2: Phân hoạch đệ quy dãy con từ phần tử thứ I đến phần tử thứ Last
Bkt: Kết thúc
- Cài đặt thuật toán:
Click to buy NOW!
P
D
F
-

o
m
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
c
u
-

J ;
if (I <= J)
{ Swap(M[I], M[J]);
I++;
J ;
}
}
while (I <= J);
PartitionSort(M, First, J);
PartitionSort(M, I, Last);
return;
}
//===========================================
void QuickSort(T M[], int N)
{ PartitionSort(M, 0, N-1);
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: 45 55 25 20 15 5 25 30 10 3
Ban đầu: First = 1 Last = 10 X = M[(1+10)/2] =M[5] = 15
First X = 15 Last
M: 45 55 25 20 15 5 25 30 10 3

Phân hoạch:
Click to buy NOW!
P
D
F
-

o
m
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
c
u
-

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

Phân hoạch:
I X = 10 J
M: 3 10 5 15 20 25 25 30 55 45

X = 10 J
M: 3 10 5 15 20 25 25 30 55 45
I
J X = 10
M: 3 5 10 15 20 25 25 30 55 45
I
Phân hoạch các phần tử trong dãy con từ First -> J:
First = 1 Last = J = 2 X = M[(1+2)/2] = M[1] = 3
First Last
M: 3 5 10 15 20 25 25 30 55 45
X = 3
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e


C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o

M: 3 5 10 15 20 25 25 30 55 45
X = 10
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 = 5 Last = 10 X = M[(5+10)/2] = M[7] = 25
First X = 25 Last
M: 3 5 10 15 20 25 25 30 55 45

Phân hoạch:
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

V
i
e
w
e
r


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