Xem mẫu
- Môn: CẤU TRÚC DỮ LIỆU
Chương 3: KỸ THUẬT SẮP XẾP
1
- 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
BÀI TẬP
2
- 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 3
- 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)
4
- 2. Sắp xếp trên dãy/mảng (tt)
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.
5
- 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]
- 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;
}
void BubbleSort(T M[], int N)
{ for(int I =0; II; J--)
if (M[J] < M[J-1])
Swap(M[J], M[J-1]);
return;
7
- 2. Sắp xếp trên dãy/mảng (tt)
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
8
- 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.
9
- 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
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
10
- 2. Sắp xếp trên dãy/mảng (tt)
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
- 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
- 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 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;
}
13
- 2. Sắp xếp trên dãy/mảng (tt)
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ự.
14
- 2. Sắp xếp trên dãy/mảng (tt)
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
15
- 2. Sắp xếp trên dãy/mảng (tt)
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
- 2. Sắp xếp trên dãy/mảng (tt)
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
17
- 2. Sắp xếp trên dãy/mảng (tt)
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í
18
- 2. Sắp xếp trên dãy/mảng (tt)
2.3. (tt) Thuật Toán Chèn trực tiếp (Straight Insertion Sort)
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 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
19
- 2. Sắp xếp trên dãy/mảng (tt)
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 (KM[Position])
Position ++;
for (int I = K; I > Position; I--)
M[I] = [I-1];
M[Position] = X;
K++
}
return;
}
20
nguon tai.lieu . vn
