1
Môn: CẤU TRÚC DỮ LIỆU
Chương 3: KỸ THUẬT SẮP XẾP
2
NỘI DUNG CHƯƠNG 3
1. Khái quát về sắp xếp
2. Các phương pháp sắp xếp (Sắp xếp trên dãy)

Sắp xếp bằng phương pháp đổi chỗ (Exchange)

Sắp xếp bằng phương pháp chọn (Selection)

Sắp xếp bằng phương pháp chèn (Insertion)

Sắp xếp bằng phương pháp trộn (Merge)
1. Các phương pháp sắp xếp (Sắp xếp trên tập tin)

Sắp xếp tập tin bằng phương pháp trộn

Sắp xếp tập tin theo chỉ mục
BÀI TẬP
3
1. Khái quát về sắp xếp
Sắp xếp là thao tác cần thiết thường được thực hiện trong quá
trình lưu trữ và quản lý dữ liệu.
Thứ tự dữ liệu có thể tăng hay giảm, tăng hay giảm thuật toán sắp
xếp là tương tự.
Hai nhóm giải thuật sắp xếp

Các giải thuật sắp xếp thứ tự nội (sx thứ tự trên mảng)



Sau mỗi lần đi duyệt dãy, 1 phần tử sẽ được đưa lên
đúng chỗ của nó. Đối với mảng M có N phần tử thì
sau N-1 lần đi duyệt dãy  dãy M có thứ tự tăng.
6
2. Sắp xếp trên dãy/mảng (tt)
2.1. a. Bubble Sort (tt) Thuật toán:
B1: First = 1
B2: IF (First == N)
Thực hiện BKT
B3: ELSE
B31: Under = N
B32: IF (Under == First)
Thực hiện B4
B33: ELSE
IF (M[Under]<M[Under – 1])
Chuyển vị trí (M[Under], M[Under – 1])
Under –
Lặp lại B32
B4: First++
B5: Lặp lại B2
BKT: Kết thúc
7
2. Sắp xếp trên dãy/mảng (tt)
2.1. a. Bubble Sort (tt) Cài đặt thuật toán:
void Swap(T &X, T &Y)
{ T Temp = X;
X = Y;
Y = Temp;
return;

= (N-1) + (N-2) +… + 1
9
2. Sắp xếp trên dãy/mảng (tt)
2.1. a. Bubble Sort (tt) Nhận xét thuật toán:

Thuật toán đơn giản dễ cài đặt

Vói Bubble Sort, phần tử “nhỏ” ở dưới được đưa lên
rất nhanh nhưng phần tử “lớn” lại đi xuống chậm,
không tận dụng được chiều ngược lại

Thuật toán không nhận diện được các phần tử ở 2
đầu của mảng đã nằm đúng vị trí để giảm bớt quãng
đường trong mỗi lần duyệt.
10
2. Sắp xếp trên dãy/mảng (tt)
2.1. b. Thuật toán sắp xếp dựa trên phân hoạch (Partitioning Sort)
(thuật toán sx nhanh Quick Sort)
Ý tưởng:
Phân hoạch mảng M thành 3 dãy con:

Dãy con thứ 1 gồm các phần tử có giá trị nhỏ hơn giá trị trung
bình của dãy M

Dãy con thứ 2 gồm các phần tử có giá trị bằng giá trị trung bình
của dãy M

Dãy con thứ 3 gồm các phần tử có giá trị lớn hơn giá trị trung
bình của dãy M
Nếu: dãy con thứ 1, 3 có nhiều hơn 1 phần tử thì tiếp tục phân

B12: ELSE
Phân hoạch đệ quy dãy từ phần tử First đến phần tử thứ J
Phân hoạch đệ quy dãy từ phần tử thứ I đến phần tử Last
BKT: Kết thúc
12
2. Sắp xếp trên dãy/mảng (tt)
2.1. b. Quick Sort (tt) Cài đặt thuật toán
void PartitionSort(T M[], int First, int Last)
{
if (First >=Last)
return;
T X = M[(First + Last)/2];
int I = First;
int J = Last;
do
{
while (M[I] < X)
I++;
while (M[J] > X) J--
if (I<=J)
{
Swap(M[I], M[J]);
I++;
J--;
}
} while (I <=J);
PartitionSort(M, First, J);
PartitionSort(M, I, Last);
Return;
}