Giáo trình Cấu trúc dữ liệu và giải thuật - Nguyễn Thị Thu Hà

 
tốc độ sắp xếp 
tương đối nhanh. Các giải thuật sắp xếp nội bao gồm các nhóm sau: 
- Sắp xếp bằng phương pháp đếm (counting sort), 
- Sắp xếp bằng phương pháp đổi chỗ (exchange sort), 
- Sắp xếp bằng phương pháp chọn lựa (selection sort), 
- Sắp xếp bằng phương pháp chèn (insertion sort), 
- Sắp xếp bằng phương pháp trộn (merge sort). 
Trong phạm vi của giáo trình này chúng ta chỉ trình bày một số thuật toán 
sắp xếp tiêu biểu trong các thuật toán sắp xếp ở các nhóm trên và giả sử thứ 
tự sắp xếp N phần tử có kiểu dữ liệu T trong mảng M là thứ tự tăng. 
 2.1. Sắp xếp bằng phương pháp đổi chỗ (Exchange Sort) 
 Các thuật toán trong phần này sẽ tìm cách đổi chỗ các phần tử 
 đứng sai vị trí (so với mảng đã sắp xếp) trong mảng M cho nhau để 
 cuối cùng tất cả các phần tử trong mảng M đều về đúng vị trí như 
 mảng đã sắp xếp. 
 49 
Các thuật toán sắp xếp bằng phương pháp đổi chỗ bao gồm: 
- Thuật toán sắp xếp nổi bọt (bubble sort), 
- Thuật toán sắp xếp lắc (shaker sort), 
- Thuật toán sắp xếp giảm độ tăng hay độ dài bước giảm dần (shell 
sort), 
- Thuật toán sắp xếp dựa trên sự phân hoạch (quick sort). 
Ở đây chúng ta trình bày hai thuật toán phổ biến là thuật toán 
sắp xếp nổi bọt và sắp xếp dựa trên sự phân hoạch. 
a. Thuật toán sắp xếp nổi bọt (Bubble Sort): 
- Tư tưởng: 
+ Đi từ cuối mảng về đầu mảng, trong quá trình đi nếu phần 
tử ở dưới (đứng phía sau) nhỏ hơn phần tử đứng ngay trên 
(trước) nó thì theo nguyên tắc của bọt khí phần tử nhẹ sẽ bị 
"trồi" lên phía trên phần tử nặng (hai phần tử này sẽ được đổi 
chỗ cho nhau). Kết quả là phần tử nhỏ nhất (nhẹ nhất) sẽ được đưa 
lên (trồi lên) trên bề mặt (đầu mảng) rất nhanh. 
+ Sau mỗi lần đi chúng ta đưa được một phần tử trồi lên đúng chỗ. Do 
vậy, sau N-1 
lần đi thì tất cả các phần tử trong mảng M sẽ có thứ tự tăng. 
- Thuật toán: 
B1: First = 1 
B2: IF (First = N) 
Thực hiện Bkt 
B3: ELSE 
B3.1: Under = N 
B3.2: If (Under = First) 
Thực hiện B4 
B3.3: Else 
B3.3.1: if (M[Under] < M[Under - 1]) 
Swap(M[Under], M[Under - 1]) 
B3.3.2: Under-- 
B3.3.3: Lặp lại B3.2 
B4: First++ 
B5: Lặp lại B2 
Bkt: Kết thúc 
- Cài đặt thuật toán: 
Hàm BubbleSort có prototype như sau: 
void BubbleSort(T M[], int N); 
 50 
//Đổi chỗ 2 phần tử cho nhau 
Hàm thực hiện việc sắp xếp N phần tử có kiểu dữ liệu T trên 
mảng M theo thứ tự tăng dựa trên thuật toán sắp xếp nổi bọt. Nội 
dung của hàm như sau: 
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; 
}? 
Hàm Swap có prototype như sau: 
void Swap(T????X, T????Y); 
Hàm thực hiện việc hoán vị giá trị của hai phần tử X và Y 
cho nhau. Nội dung của hàm như sau: 
void Swap(T????X, T????Y) 
{ T Temp = X; 
X = Y; 
Y = Temp; 
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: 15 10 2 20 10 5 25 35 22 
30 
Ta sẽ thực hiện 9 lần đi (N - 1 = 10 - 1 = 9) để sắp xếp mảng M: 
- 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. 
 51 
 + 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 
 2.2. sắp_xếp_chọn: 
Vấn đề xếp tiền : Có một xấp tiền gồm nhiều tờ có mệnh giá khác nhau đang để lộn 
 xộn, cần 
 xếp lại theo thứ tự tiền nhỏ trước, tiền lớn sau. 
Phương pháp xếp tiền là: lần lượt chọn ra các tờ tiền từ nhỏ đến lớn để xếp cho 
 đến khi hết 
 xấp tiền. 
Đối với mảng, các bước thực hiện là: 
• Trong N phần tử của mảng, chọn phần tử bé nhất, chuyển lên đầu mảng 
• Trong N-1 phần tử còn lại, chọn phần tử bé nhất, chuyển vào vị trí thứ 2 
• Tiếp tục cho đến khi sắp xếp hết. 
 2.3. sắp xếp chèn: 
Phương pháp: 
• Giống như cách xếp bài khi được chia quân bài. 
• Quân bài mới nhận được chèn vào những quân bài đã có trên tay. 
• Các quân bài trên tay luôn được sắp xếp. 
• Thuật toán: 
void InsertionSort(int a[], int N) 
{ 
 int i, j, temp; 
 for(i = 1; i< N; i++) 
 { 
 temp = a[i]; 
 j = i- 1; 
 while ((j>=0)&&(a[j]>a[j+1])) 
 { 
 a[j+1] = a[j]; 
 j--; 
 52 
 } 
 if (j!=i-1) 
 a[j+1] = temp; 
 } 
2.4. Sắp xếp phân đoạn: 
 – Phương pháp: 
 Dùng giải pháp đệ quy (chia để trị) 
 • Bước 1: Phân hoạch mảng A ban đầu thành 2 mảng con B và C sao cho bi 
 cj  bi B, cj C. 
 • Bước 2: Sắp xếp mảng con B bằng đệ quy 
 • Bước 3: Sắp xếp mảng con C bằng đệ quy 
 • Điều kiện dừng: khi mảng con cần sắp chỉ có 1 phần tử xem như được 
 sắp. 
 • Vì B, C được sắp và bi cj nên mảng A là được sắp 
2.5. Sắp xếp hòa nhập: 
 – Phương pháp: 
 Cũng sử dụng giải pháp chia để trị 
 • Bước 1: Chia mảng A ban đầu thành 2 mảng con B và C. 
 • Bước 2, 3: Sắp xếp mảng con B và C bằng đệ quy (Điều kiện dừng: khi 
 mảng con cần sắp chỉ có 1 phần tử) 
 • Bước 4: Trộn (merge) 2 mảng con đã sắp B, C thành mảng A được sắp. 
Thuật toán: 
int Partition(int a[], int p, int r) 
{ 
 int t; 
 // phân hoạch 
 return t; 
} 
void QuickSort(int a[], int p, int r) 
{ 
 int t = Partition(a, p, r); 
 if (p< t-1) QuickSort(a, p, t-1); 
 if (t+1< r) QuickSort(a, t+1, r); 
 53 
} 
 Chương 6: Tìm Kiếm 
 1. Khái quát về tìm kiếm 
 Trong thực tế, khi thao tác, khai thác dữ liệu chúng ta hầu như lúc 
 nào cũng phải thực hiện thao tác tìm kiếm. Việc tìm kiếm nhanh hay 
 54 
chậm tùy thuộc vào trạng thái và trật tự của dữ liệu trên đó. Kết quả 
của việc tìm kiếm có thể là không có (không tìm thấy) hoặc có (tìm 
thấy). Nếu kết quả tìm kiếm là có tìm thấy thì nhiều khi chúng ta còn 
phải xác định xem vị trí của phần tử dữ liệu tìm thấy là ở 
đâu? Trong phạm vi của chương này chúng ta tìm cách giải quyết 
các câu hỏi này. 
Trước khi đi vào nghiên cứu chi tiết, chúng ta giả sử rằng 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 là T nào đó, các thành phần còn lại là 
thông tin (Info) liên quan đến phần tử dữ liệu đó. Như vậy 
mỗi phần tử dữ liệu có cấu trúc dữ liệu như sau: 
typedef 
{ T 
struct DataElement 
Key; 
InfoType 
} DataType; 
Info; 
Trong tài liệu này, khi nói tới giá trị của một phần tử dữ liệu chúng ta 
muốn nói tới giá trị khóa (Key) của phần tử dữ liệu đó. Để đơn 
giản, chúng ta giả sử rằng mỗi phần tử dữ liệu chỉ là thành phần 
khóa nhận diện. 
Việc tìm kiếm một phần tử có thể diễn ra trên một dãy/mảng (tìm 
kiếm nội) hoặc diễn ra trên một tập tin/ file (tìm kiếm ngoại). Phần tử 
cần tìm là phần tử cần thỏa mãn điều kiện tìm kiếm (thường có giá trị 
bằng giá trị tìm kiếm). Tùy thuộc vào từng bài toán cụ thể mà điều 
kiện tìm kiếm có thể khác nhau song chung quy việc tìm kiếm 
dữ liệu thường được vận dụng theo các thuật toán trình bày sau đây. 
2. Tìm tuần tự (Linear Search) 
Thuật toán tìm tuyến tính còn được gọi là Thuật toán tìm kiếm 
tuần tự (Sequential Search). 
a. Tư tưởng: 
Lần lượt so sánh các phần tử của mảng M với giá trị X bắt 
đầu từ phần tử đầu tiên cho đến khi tìm đến được phần tử có giá trị 
X hoặc đã duyệt qua hết tất cả các phần tử của mảng M thì kết thúc. 
b. Thuật toán: 
B1: k = 1 
B2: IF M[k]?? X AND k?? N 
B2.1: k++ 
 55 
B2.2: Lặp lại B2 
B3: IF k?? N 
Tìm thấy tại vị trí k 
B4: ELSE 
//Duyệt từ đầu mảng 
//Nếu chưa tìm thấy và cũng chưa duyệt hết mảng 
Không tìm thấy phần tử có giá trị X 
B5: Kết thúc 
c. Cài đặt thuật toán: 
Hàm LinearSearch có prototype: 
int LinearSearch (T M[], int N, T X); 
Hàm thực hiện việc tìm kiếm phần tử có giá trị X trên mảng M có N 
phần tử. Nếu tìm thấy, hàm trả về một số nguyên có giá trị từ 0 đến 
N-1 là vị trí tương ứng của phần tử tìm thấy. Trong trường hợp 
ngược lại, hàm trả về giá trị -1 (không tìm thấy). Nội dung của 
hàm như sau: 
int LinearSearch (T M[], int N, T X) 
{ int k = 0; 
while (M[k] != X??? k < N) 
k++; 
if (k < N) 
return (k); 
return (-1); 
}? 
d. Phân tích thuật toán: 
- Trường hợp tốt nhất khi phần tử đầu tiên của mảng có giá trị bằng X: 
Số phép gán: Gmin = 1 
Số phép so sánh: Smin = 2 + 1 = 3 
- Trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng 
X: 
Số phép gán: Gmax = 1 
Số phép so sánh: Smax = 2N+1 
- Trung bình: 
Số phép gán: Gavg = 1 
Số phép so sánh: Savg = (3 + 2N + 1) : 2 = N + 2 
e. Cải tiến thuật toán: 
Trong thuật toán trên, ở mỗi bước lặp chúng ta cần phải thực hiện 2 
phép so sánh để kiểm tra sự tìm thấy và kiểm soát sự hết mảng trong 
quá trình duyệt mảng. Chúng ta có thể giảm bớt 1 phép so sánh nếu 
chúng ta thêm vào cuối mảng một phần tử cầm canh (sentinel/stand 
 56 
by) có giá trị bằng X để nhận diện ra sự hết mảng khi duyệt 
mảng, khi đó thuật toán này được cải tiến lại như sau: 
 B1: k = 1 
B2: M[N+1] = X 
B3: IF M[k]?? X 
B3.1: k++ 
B3.2: Lặp lại B3 
B4: IF k < N 
Tìm thấy tại vị trí k 
B5: ELSE 
//Phần tử cầm canh 
//k = N song đó chỉ là phần tử cầm canh 
Không tìm thấy phần tử có giá trị X 
B6: Kết thúc 
Hàm LinearSearch được viết lại thành hàm LinearSearch1 như sau: 
int LinearSearch1 (T M[], int N, T X) 
{ int k = 0; 
M[N] = X; 
while (M[k] != X) 
k++; 
if (k < N) 
return (k); 
return (-1); 
}? 
f. Phân tích thuật toán cải tiến: 
- Trường hợp tốt nhất khi phần tử đầu tiên của mảng có giá trị bằng X: 
Số phép gán: Gmin = 2 
Số phép so sánh: Smin = 1 + 1 = 2 
- Trường hợp xấu nhất khi không tìm thấy phần tử nào có giá trị bằng 
X: 
Số phép gán: Gmax = 2 
Số phép so sánh: Smax = (N+1) + 1 = N + 2 
- Trung bình: 
Số phép gán: Gavg = 2 
Số phép so sánh: Savg = (2 + N + 2) : 2 = N/2 + 2 
- Như vậy, nếu thời gian thực hiện phép gán không đáng kể thì thuật 
toán cải tiến sẽ chạy nhanh hơn thuật toán nguyên thủy. 
 57 
3. Tìm nhị phân (Binary Search) 
Thuật toán tìm tuyến tính tỏ ra đơn giản và thuận tiện trong trường 
hợp số phần tử của dãy không lớn lắm. Tuy nhiên, khi số phần tử của 
dãy khá lớn, chẳng hạn chúng ta tìm kiếm tên một khách hàng 
trong một danh bạ điện thoại của một thành phố lớn theo thuật 
toán tìm tuần tự thì quả thực mất rất nhiều thời gian. Trong thực tế, 
thông thường các phần tử của dãy đã có một thứ tự, do vậy 
thuật toán tìm nhị phân sau đây sẽ rút ngắn đáng kể thời gian tìm 
kiếm trên dãy đã có thứ tự. Trong thuật toán này chúng ta giả sử các 
phần tử trong dãy đã có thứ tự tăng (không giảm dần), tức là 
các phần tử đứng trước luôn có giá trị nhỏ hơn hoặc bằng 
(không lớn hơn) phần tử đứng sau nó. 
Khi đó, nếu X nhỏ hơn giá trị phần tử đứng ở giữa dãy 
(M[Mid]) thì X chỉ có thể tìm thấy ở nửa đầu của dãy và ngược 
lại, nếu X lớn hơn phần tử M[Mid] thì X chỉ có thể tìm thấy ở nửa sau 
của dãy. 
a. Tư tưởng: 
Phạm vi tìm kiếm ban đầu của chúng ta là từ phần tử đầu tiên 
của dãy (First = 1) cho đến phần tử cuối cùng của dãy (Last = N). 
So sánh giá trị X với giá trị phần tử đứng ở giữa của dãy M là 
M[Mid]. 
Nếu X = M[Mid]: Tìm thấy 
Nếu X < M[Mid]: Rút ngắn phạm vi tìm kiếm về nửa đầu của dãy M 
(Last = Mid-1) 
Nếu X > M[Mid]: Rút ngắn phạm vi tìm kiếm về nửa sau của dãy M 
(First = Mid+1) 
Lặp lại quá trình này cho đến khi tìm thấy phần tử có giá trị 
X hoặc phạm vi tìm kiếm của chúng ta không còn nữa (First > 
Last). 
b. Thuật toán đệ quy (Recursion Algorithm): 
B1: First = 1 
B2: Last = N 
B3: IF (First > Last) 
B3.1: Không tìm thấy 
B3.2: Thực hiện Bkt 
B4: Mid = (First + Last)/ 2 
B5: IF (X = M[Mid]) 
//Hết phạm vi tìm kiếm 
B5.1: Tìm thấy tại vị trí Mid 
B5.2: Thực hiện Bkt 
 58 
B6: IF (X < M[Mid]) 
Tìm đệ quy từ First đến Last = Mid - 1 
B7: IF (X > M[Mid]) 
Tìm đệ quy từ First = Mid + 1 đến Last 
Bkt: Kết thúc 
c. Cài đặt thuật toán đệ quy: 
Hàm BinarySearch có prototype: 
int BinarySearch (T M[], int N, T X); 
Hàm thực hiện việc tìm kiếm phần tử có giá trị X trong mảng M có N 
phần tử đã có thứ tự tăng. Nếu tìm thấy, hàm trả về một số nguyên có 
giá trị từ 0 đến N-1 là vị trí tương ứng của phần tử tìm thấy. 
Trong trường hợp ngược lại, hàm trả về giá trị -1 (không tìm 
thấy). Hàm BinarySearch sử dụng hàm đệ quy RecBinarySearch 
có prototype: 
int RecBinarySearch(T M[], int First, int Last, T X); 
Hàm RecBinarySearch thực hiện việc tìm kiếm phần tử có giá 
trị X trên mảng M trong phạm vi từ phần tử thứ First đến phần 
tử thứ Last. Nếu tìm thấy, hàm trả về một số nguyên có giá trị 
từ First đến Last là vị trí tương ứng của phần tử tìm thấy. 
Trong trường hợp ngược lại, hàm trả về giá trị -1 (không tìm thấy). 
4.Câu hỏi và Bài tập 
1. Trình bày tư tưởng của các thuật toán tìm kiếm: Tuyến tính, Nhị 
phân, Chỉ mục? Các thuật toán này có thể được vận dụng trong các 
trường hợp nào? Cho ví dụ? 
2. Cài đặt lại thuật toán tìm tuyến tính bằng các cách: 
- Sử dụng vòng lặp for, 
- Sử dụng vòng lặp do  while? 
Có nhận xét gì cho mỗi trường hợp? 
Trong trường hợp các phần tử của dãy đã có thứ tự tăng, hãy cải tiến 
lại thuật toán tìm tuyến tính? Cài đặt các thuật toán cải tiến? Đánh giá 
và so sánh giữa thuật toán nguyên thủy với các thuật toán cải tiến. 
4. Trong trường hợp các phần tử của dãy đã có thứ tự giảm, hãy trình 
bày và cài đặt lại thuật toán tìm nhị phân trong hai trường hợp: Đệ 
quy và Không đệ quy? 
5. Vận dụng thuật toán tìm nhị phân, hãy cải tiến và cài đặt lại thuật 
toán tìm kiếm dựa theo tập tin chỉ mục? Đánh giá và so sánh giữa 
thuật toán nguyên thủy với các thuật toán cải tiến? 
 59 
6. Sử dụng hàm random trong C để tạo ra một dãy (mảng) M có tối 
thiểu 1.000 số nguyên, sau đó chọn ngẫu nhiên (cũng bằng hàm 
random) một giá trị nguyên K. Vận dụng các thuật toán tìm tuyến 
tính, tìm nhị phân để tìm kiếm phần tử có giá trị K trong mảng M. 
Với cùng một dữ liệu như nhau, cho biết thời gian thực hiện các thuật 
toán. 
7. Trình bày và cài đặt thuật toán tìm tuyến tính đối với các phần tử 
trên mảng hai chiều trong hai trường hợp: 
- Không sử dụng phần tử “Cầm canh”. 
- Có sử dụng phần tử “Cầm canh”. 
Cho biết thời gian thực hiện của hai thuật toán trong hai trường hợp 
trên. 
8. Sử dụng hàm random trong C để tạo ra tối thiểu 1.000 số nguyên và 
lưu trữ vào mot tập tin có tên SONGUYEN.DAT, sau đó chọn ngẫu 
nhiên (cũng bằng hàm random) một giá trị nguyên K. Vận dụng thuật 
toán tìm tuyến tính để tìm kiếm phần tử có giá trị K trong tập tin 
SONGUYEN.DAT.