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)
3. 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
29 trang |
Chia sẻ: phuongt97 | Lượt xem: 381 | Lượt tải: 0
Bạn đang xem trước 20 trang nội dung tài liệu Bài giảng môn Cấu trúc dữ liệu - Chương 3: Kỹ thuật sắp xếp, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Chương 3:
KỸ THUẬT SẮP XẾP
48
49
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)
3. 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
50
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)
• Các giải thuật sắp xếp thứ tự ngoại (sx thứ tự trên tập tin)
Xem như mỗi phần tử dữ liệu được xem xét có một thành phần khóa (Key)
để nhận diện có kiểu dữ liệu T, các thành phần còn lại là thông tin (Info),
như vậy mỗi phần tử có cấu trúc như sau:
typedef struct DataElement
{
T Key;
InfoData Info;
} DataType;
Để đơn giản, quan tâm thành phần dữ liệu chỉ là khóa nhận diện
51
2. Sắp xếp trên dãy/mảng
2.1. Sắp xếp bằng phương pháp đổi chỗ (Exchange)
a. Thuật toán sắp xếp nổi bọt (Bubble Sort)
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)
2.2. Sắp xếp bằng phương pháp chọn (Selection Sort)
Chọn trực tiếp (Straight Selection Sort)
2.3. Sắp xếp bằng phương pháp chèn (Insertion Sort)
Chèn trực tiếp (Straight Insertion Sort)
2.4. Sắp xếp bằng phương pháp trộn (Merge Sort)
a. Trộn trực tiếp (Straight Merge Sort)
b. Trộn tự nhiên (Natural Merge Sort)
52
2. Sắp xếp trên dãy/mảng
2.1. a. Thuật toán sắp xếp nổi bọt (Bubble Sort)
Ý tưởng:
• Đi từ cuối mảng đến đầu mảng, nếu phần tử ở dưới <
phần tử đứng trên nó thì sẽ được “đưa lên trên”.
• 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.
53
2. Sắp xếp trên dãy/mảng
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
54
2. Sắp xếp trên dãy/mảng
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;
}
void BubbleSort(T M[], int N)
{ for(int I =0; I<N-1; I++)
for(int J =N-1; J>I; J--)
if (M[J] < M[J-1])
Swap(M[J], M[J-1]);
return;
}
55
2. Sắp xếp trên dãy/mảng
2.1. a. Bubble Sort (tt) 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
• Số phép hoán vị các phần tử Hmin = 0
• Trong trường hợp xấu nhất
• Số phép hoán vị các phần tử Hmax = (N-1) + (N-2) + + 1
56
2. Sắp xếp trên dãy/mảng
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.
57
2. Sắp xếp trên dãy/mảng
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
hoạch các dãy này.
Tìm giá trị trung bình của dãy là mất thời gian trong thực tế
chọn phần tử đứng giữa là dãy con thứ 2.
Việc phân hoạch dãy được thực hiện: tìm các cặp phần tử (của
dãy 1 và dãy 3) sai thứ tự để hoán vị cho nhau
58
2. Sắp xếp trên dãy/mảng
2.1. b. Quick Sort (tt) Thuật toán
B1: First = 1
B2: Last = N
B3: IF (First >= Last) // mảng con chỉ còn không quá 1 phần tử
Thực hiện BKT
B4: X = M[(First + Last)/2]
B5: I = First // Từ dãy con số 1 tìm phần tử có giá trị lớn hơn X
B6: IF (M[I] > X)
Thực hiện B8
B7: ELSE
I++
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ị nhỏ hơn X
B9: IF (M[J] < X)
Thực hiện B11
B10: ELSE
J--
Lặp lại B9
B11: IF (I <=J)
Thực hiện hoán vị M[I], M[J]
Tăng I++
Giảm J--
Lặp lại B6
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
59
2. Sắp xếp trên dãy/mảng
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;
}
60
2. Sắp xếp trên dãy/mảng
2.1. b. Quick Sort (tt) Cài đặt thuật toán
void Swap(T &X, T &Y)
{
T Temp = X;
X = Y;
Y = Temp;
return
}
void QuickSort(T M[], int N)
{
PartitionSort(M, 0, N-1);
return;
}
61
2. Sắp xếp trên dãy/mảng
2.2. Sắp xếp bằng phương pháp chọn (Selection Sort)
Chọn trực tiếp (Straight Selection Sort)
• Dãy M có N phần tử chưa có thứ tự. Chọn phần tử nhỏ
nhất của dãy này đưa lên đầu dãy.
• Sau lần chọn thứ nhất, còn lại N-1 phần tử chưa có thứ
tự. Tiếp tục thực hiện, sau N-1 lần lựa chọn và đưa
phần tử nhỏ nhất lên trên dãy M có thứ tự tăng dần.
• Để tìm phần tử nhỏ nhất của dãy dựa vào cách tìm
kiếm duyệt dãy tuần tự.
62
2. Sắp xếp trên dãy/mảng
2.2. (tt) Straight Selection Sort: Thuật toán
B1: K=0
B2: IF (K = N-1)
Thực hiện BKT
B3: Min = M[K+1]
B4: PositionMin = K+1
B5: Position = K+2
B6: IF(Position > N)
Thực hiện B8
B7: ELSE
IF (Min >M[Postion])
Min = M[Position]
PositionMin = Pos
Position ++
Lặp lại B6 kiểm tra vị trí so với N
B8: Hoán vị (M[K+1], M[PositionMin])
B9: K++
B10: Lặp lại B2
BKT: Kết thúc
63
2. Sắp xếp trên dãy/mảng
2.2. (tt) Straight Selection Sort: Cài đặt thuật toán
void StraightSelectionSort(T M[], int N)
{ int K = 0;
int PositionMin;
while (K<N-1)
{ T Min = M[K];
PositionMin = K;
for (int Position = K + 1; Position <N; Position ++)
{
if (Min >M[Position])
{ Min = M[Position];
PositionMin = Position;
}
}
Swap (M[K], M[PositionMin]);
K++;
}
return;
}
64
2. Sắp xếp trên dãy/mảng
2.2. (tt) Chọn trực tiếp (Straight Selection Sort)
Phân tích thuật toán:
• Trong mọi trường hợp
• Số phép so sánh S = (N-1) + (N-2) + + 1 = ½N(N-1)
• Số phép hoán vị H = N-1
• Trong trường hợp tốt nhất
• Số phép gán Gmin = 2 x (N-1)
• Trong trường hợp xấu nhất
• Số phép gán Gmax = 2 x [(N-1) + (N-2) + + 1]
• Trong trường hợp trung bình
• Số phép gán Gavg = (Gmin+Gmax)/2
65
2. Sắp xếp trên dãy/mảng
2.3. Sắp xếp bằng phương pháp chèn (Insertion Sort)
Chèn trực tiếp (Straight Insertion Sort)
• Để chèn phần tử thứ K+1 vào K phần tử đầu dãy đã có
thứ tự tiến hành tìm đúng của phần tử K+1 trong K
phần tử đầu bằng giải thuật tìm kiếm tuần tự.
• Khi tìm được vị trí chèn, dời các phần tử từ vị trí chèn
đến phần tử thứ K sang phải 1 vị trí
66
2.3. (tt)2. Thuật Sắp Toán xếpChèn trực trên tiếp (Straight dãy/mảng Insertion Sort) (tt)
B1: K=0
B2: IF (K = N) Thực hiện BKT
B3: X = M[K+1]
B4: Position = 1
B5: IF(Position > K) Thực hiện B7
B6: ELSE
B61: IF (X <=M[Postion])
Thực hiện B7
B62: Position ++
B63: Lặp lại B61
B7: I = K+1
B8: IF (I > Position)
B81: M[I] = M[I-1]
B82: I --
B83: Lặp lại B8
B9: ELSE
B91: M[Position] = X
B92: K++
B93: Lặp lại B2
BKT: Kết thúc
67
2. Sắp xếp trên dãy/mảng
2.3. (tt) Cài đặt Thuật Toán Chèn trực tiếp (Straight Insertion Sort)
void StraightInsertionSort(T M[], int N)
{
int K = 1;
int Position;
while (K<N)
{
T X = M[K];
Position = 0;
while (X>M[Position])
Position ++;
for (int I = K; I > Position; I--)
M[I] = [I-1];
M[Position] = X;
K++
}
return;
}
68
2. Sắp xếp trên dãy/mảng
2.3. Chèn trực tiếp (Straight Insertion Sort) (tt)
Phân tích thuật toán
• Trong trường hợp tốt nhất
• Số phép gán Gmin = 2 × (N-1)
• Số phép so sánh Smin = 1 + 2 + +(N-1) = N ×(N-1)/2
• Số phép hoán vị Hmin = 0
• Trong trường hợp xấu nhất
• Số phép gán Gmax = [2 × (N-1)] + [1+2++(N-1)]
• Số phép so sánh Smax = (N-1)
• Số phép hoán vị Hmax = 0
• Trong trường hợp trung bình
• Số phép gán Gavg = (Gmin+Gmax)/2
Quá trình tìm vị trí chèn của phần tử thứ K+1 và quá trình
dời
69
2. Sắp xếp trên dãy/mảng
2.4. Phương pháp sắp xếp Trộn (Merge Sort)
• Các thuật toán trộn tìm cách tách các mảng con theo các
đường chạy (run) rồi tiến hành nhập các mảng theo từng
cặp để tạo thành các đường mới có chiều dài lớn hơn
đường chạy cũ. Sau một số lần tách nhập, cuối cùng mảng
M chỉ còn 1 đường chạy đuợc sắp xếp thứ tự.
• Đường chạy (run): Dãy M[I], M[I+1],M[J] (I>=1, I<=J,
J<=N) là một đường chạy nếu nó có thứ tự
• Chiều dài của đường chạy (run’s length): Là số phần tử của
một đường chạy. Một dãy sẽ bao gồm nhiều đường chạy.
• Trộn các đường chạy: Khi trộn các đường chạy với nhau sẽ
tạo ra đường chạy mới có tổng chiều dài bằng các đường
chạy ban đầu.
70
2. Sắp xếp trên dãy/mảng
2.4. a. Trộn trực tiếp (Straight Merge Sort)
• Dãy M có N đường chạy (runs) với chiều dài L=1, tiến hành
phân phối luân phiên N runs của dãy về 2 dãy phụ T1, T2
(N/2 runs)
• Trộn từng cặp các dãy phụ T1, T2 thành 1 run có chiều dài
là L=2 đưa trở về dãy M, (lúc này M gồm N/2 runs) với
chiều dài mỗi run là L =2
• Sau mỗi lần phân phối, số run trên M giảm đi ½ và chiều dài
mỗi run tăng gấp đôi. Sau log2N lần phân phối và trộn thì
dãy M chỉ còn lại 1 run với chiều dài được sắp xếp dãy
M có thứ tự.
• Thuật giải chia làm 2 phần
• Thuật giải phân phối các đường chạy L trên M về 2 dãy phụ T1 & T2
• Thuật giải trộn các cặp đường chạy trên T1 & T2 có chiều dài L về M
thành các đường chạy với chiều dài 2*L
71
2. Sắp xếp trên dãy/mảng
2.4. a. (tt) Phân tích thuật toán Straight Merge Sort
• Thực hiện log2N lần phân phối và trộn các run
• Mỗi lần phân phối thực hiện N phép gán, 2N phép so
sánh
• Mỗi lần trộn N phép gán, 2N+N/2 phép so sánh
• Số phép hoán vị cho mọi trường hợp: H = 0
• Thuật giải dùng 2 dãy phụ, tổng số phần tử trong 2 dãy
phụ = N lãng phí bộ nhớ cải tiến dùng 1 dãy phụ
và kết hợp quá trình trộn và phân phối luân phiên về 2
dãy. Sau đó đổi vai trò 2 dãy này với nhau
72
2. Sắp xếp trên dãy/mảng
2.4. b. Trộn tự nhiên (Natural Merge Sort)
• Tận dụng đường chạy tự nhiên trên dãy, tiến hành trộn
tương ứng các cặp đường chạy tự nhiên nằm 2 đầu
của dãy thành 1 đường chạy mới và phân phối luân
phiên các đường chạy mới này về 2 đầu dãy phụ T.
• Từ dãy phụ T, tiếp tục trộn cặp tương ứng ở 2 đầu tạo
thành 1 run mới và phân phối luân phiên run mới này
về 2 đầu dãy M. Tiếp tục quá trình cho đến khi M
hay T chỉ còn lại 1 run
73
2. Sắp xếp trên dãy/mảng
2.4. b. Phân tích giải thuật Natural Merge Sort
• Trong trường hợp tốt nhất
• Số phép gán Gmin = 1
• Số phép so sánh Smin = 2N(N-1)
• Số phép hoán vị Hmin = 0
• Trong trường hợp xấu nhất
• Số phép gán Gmax = N × Log2N + 1
• Số phép so sánh Smax = 2N × Log2N + 2
• Số phép hoán vị Hmax = 0
• Trong trường hợp trung bình
• Số phép gán Gavg = (Gmin+Gmax)/2
74
3. Sắp xếp trên tập tin
3.1. Sắp xếp trong file bằng phương pháp trộn
• a. Trộn trực tiếp (Straight Merge Sort)
• b. Trộn tự nhiên (Natural Merge Sort)
3.2. Sắp xếp theo chỉ mục
75
3. Sắp xếp trên tập tin
Trộn trực tiếp (File Straight Merge Sort)
• Tương tự trộn trực tiếp trên mảng
• Ban đầu tập tin Fd có N runs chiều dài mỗi run là L=1, tiến hành phân
phối luân phiên các runs của Fd về K tập tin phụ Ft1, Ft2, FtK, mỗi tập
tin có N/K runs.
• Trộn tương ứng từng bộ K runs ở K tập tin phụ Ft1, Ft2, FtK thành 1
run mới có chiều dài L=K để đưa về tập tin Fd, tập tin Fd lúc này có N/K
runs với chiều dài mỗi run L= K.
• Sau mỗi lần phân phối và trộn các run trên Fd số các run giảm K lần,
và tương ứng chiều dài mỗi run trên Fd sẽ tăng K lần. Sau Log2N lần
phân phối và trộn Fd chỉ còn lại 1 rund với chiều dài N dữ liệu tập
tin Fd có thứ tự
• Thuật giải chia làm 2 phần
• Thuật giải phân phối các đường chạy L trên Fd về 2 dãy phụ Ft1 &
Ft2
• Thuật giải trộn các cặp đường chạy trên Ft1 & Ft2 có chiều dài L về
Fd thành các đường chạy với chiều dài 2*L
76
BÀI TẬP
• Bài tập chương 3 (trang 84 - 85)
• (Lý thuyết) Cho một mảng số nguyên bao gồm 20 phần
tử như sau 23 34 46 16 8 9 7 6 13 22 65
45 18 29 45 15 3 10 84 21
Tính số phép gán, số lần so sánh, hoán vị của mỗi
thuật toán (Bubble Sort, QuickSort, Straight Selection
Sort, Straight Insertion Sort , Straight Merge Sort,
Natural Merge Sort) là bao nhiêu?
• (Lý thuyết) Nếu đối với dãy có giá trị phần tử giữa dãy
lớn nhất, áp dụng phương pháp nào nhanh hơn
QuickSort hay Bubble Sort?
(VD: dãy : 23 4 6 77 45 5 6 7)
• Cài đặt các giải thuật sắp xếp trong lý thuyết đối với
các dãy | mảng có giá trị giảm dần
Các file đính kèm theo tài liệu này:
- bai_giang_mon_cau_truc_du_lieu_chuong_3_ky_thuat_sap_xep.pdf