Bài giảng Cấu trúc dữ liệu và giải thuật (Dùng cho sinh viên hệ đào tạo đại học từ xa)

(N-1) + (N-2) + + 2 + 1 = N(N-1)/2 Như vậy, độ phức tạp cũng giải thuật sắp xếp nổi bọt cũng là O(N2). 7.3 QUICK SORT 7.3.1 Giới thiệu Quick sort là một thuật toán sắp xếp được phát minh lần đầu bởi C.A.Hoare vào năm 1960. Đây có lẽ là thuật toán được nghiên cứu nhiều nhất và được sử dụng rộng rãi nhất trong lớp các thuật toán sắp xếp. Quick sort là một thuật toán dễ cài đặt, hiệu quả trong hầu hết các trường hợp, và tiêu tốn ít tài nguyên hơn so với các thuật toán khác. Độ phức tạp trung bình của giải thuật là O(NlogN). Nhược điểm của giải thuật này là phải cài đặt bằng đệ qui (có thể không dùng đệ qui, tuy nhiên cài đặt phức tạp hơn nhiều) và trong trường hợp xấu nhất thì độ phức tạp là O(N2). Ngoài ra, cài đặt cho Quick sort phải đòi hỏi cực kỳ chính xác. Chỉ cần một sai sót nhỏ có thể làm cho chương trình ngừng hoạt động. Kể từ khi Quick sort ra đời lần đầu tiên, đã có rất nhiều nỗ lực nhằm cải tiến thuật toán này. Tuy nhiên, hầu hết các cải tiến này đều không mang lại hiệu quả như mong đợi, vì bản thân Quick sort là một thuật toán rất cần bằng. Một sự cải tiến ở một phần này của thuật toán có thể dẫn đến một tác dụng ngược lại ở phần kia và làm cho thuật toán trở nên mất cân bằng. Ý tưởng cơ bản của Quick sort dựa trên phương pháp chia để trị như đã trình bày trong chương 2. Giải thuật chia dãy cần sắp thành 2 phần, sau đó thực hiện việc sắp xếp cho mỗi phần độc lập với nhau. Để thực hiện điều này, đầu tiên chọn ngẫu nhiên 1 phần tử nào đó của dãy làm khóa. Trong bước tiếp theo, các phần tử nhỏ hơn khoá phải được xếp vào phía trước khoá và các phần tử lớn hơn được xếp vào phía sau khoá. Để có được sự phân loại này, các phần tử sẽ được so sánh với khoá và hoán đổi vị trí cho nhau hoặc cho khoá nếu nó lớn hơn khóa mà lại nằm trước hoặc nhỏ hơn khoá mà lại nằm sau. Khi lượt hoán đổi đầu tiên thực hiện xong thì dãy được chia thành 2 đoạn: 1 đoạn bao gồm các phần tử nhỏ hơn khoá, đoạn còn lại bao gồm các phần tử lớn hơn khoá. 95 Hình 7.1 Quick sort Áp dụng kỹ thuật như trên cho mỗi đoạn đó và tiếp tục làm như vậy cho đến khi mỗi đoạn chỉ còn 2 phần tử. Khi đó toàn bộ dãy đã được sắp. 7.3.2 Các bước thực hiện giải thuật Để chia dãy thành 2 phần thoả mãn yêu cầu như trên, ta lấy một phần tử của dãy làm khoá (chẳng hạn phần tử đầu tiên). Tiến hành duyệt từ bên trái dãy và dừng lại khi gặp 1 phần tử lớn hơn hoặc bằng khoá. Đồng thời tiến hành duyệt từ bên phải dãy cho tới khi gặp 1 phần tử nhỏ hơn hoặc bằng khoá. Rõ ràng 2 phần tử này nằm ở những vị trí không phù hợp và chúng cần phải được đổi chỗ cho nhau. Tiếp tục quá trình cho tới khi 2 biến duyệt gặp nhau, ta sẽ chia được dãy thành 2 nửa: Nửa bên phải khoá bao gồm những phần tử lớn hơn hoặc bằng khoá và nửa bên trái là những phần tử nhỏ hơn hoặc bằng khoá. Ta hãy xem xét quá trình phân đôi dãy số đã cho ở phần trước. 32 17 49 98 06 25 53 61 Chọn phần tử đầu tiên của dãy, phần tủ 32, làm khoá. Quá trình duyệt từ bên trái với biến duyệt i sẽ dừng lại ở 49, vì đây là phần tử lớn hơn khoá. Quá trình duyệt từ bên phải với biến duyệt j sẽ dừng lại ở 25 vì đây là phần tử nhỏ hơn khoá. Tiến hành đổi chỗ 2 phần tử cho nhau. 32 17 25 98 06 49 53 61 Quá trình duyệt tiếp tục. Biến duyệt i dừng lại ở 98, còn biến duyệt j dừng lại ở 06. Lại tiến hành đổi vị trí 2 phần tử 98 và 06. Khoá i j Khoá 96 32 17 25 06 98 49 53 61 Tiếp tục quá trình duyệt. Các biến duyệt i và j gặp nhau và quá trình duyệt dừng lại. 32 17 25 06 98 49 53 61 Như vậy, dãy đã được chia làm 2 nửa. Nửa đầu từ phần tử đầu tiên đến phần tử thứ j, bao gồm các phần tử nhỏ hơn hoặc bằng khoá. Nửa sau từ phần tử thứ i đến phần tử cuối, bao gồm các phần tử lớn hơn hoặc bằng khoá. Quá trình duyệt và đổi chỗ được lặp lại với 2 nửa dãy vừa được tạo ra, và cứ tiếp tục như vậy cho tới khi dãy được sắp hoàn toàn. 7.3.3 Cài đặt giải thuật Để cài đặt giải thuật, trước hết ta xây dựng một thủ tục để sắp một phân đoạn của dãy. Thủ tục này là 1 thủ tục đệ qui, bao gồm việc chia phân đoạn thành 2 đoạn con thỏa mãn yêu cầu trên, sau đó thực hiện lời gọi đệ qui với 2 đoạn con vừa tạo được. Giả sử phân đoạn được giới hạn bởi 2 tham số là left và right cho biết chỉ số đầu và cuối của phân đoạn, khi đó thủ tục được cài đặt như sau: void quick(int left, int right) { int i,j; int x,y; i=left; j=right; x= a[left]; do { while(a[i]<x && i<right) i++; while(a[j]>x && j>left) j--; if(i<=j){ y=a[i];a[i]=a[j];a[j]=y; i++;j--; } }while (i<=j); if (left<j) quick(left,j); if (i<right) quick(i,right); } Tiếp theo, để thực hiện sắp toàn bộ dãy, ta chỉ cần gọi thủ tục trên với tham số left là chỉ số đầu và right là chỉ số cuối của mảng. Khoá i j Khoá j i 97 void quick_sort(){ quick(0, n-1); } Nhược điểm của Quick sort là hoạt động rất kém hiệu quả trên những dãy đã được sắp sẵn. Khi đó, cần phải mất N lần gọi đệ qui và mỗi lần chỉ loại được 1 phần tử. Thời gian thực hiện thuật toán trong trường hợp xấu nhất này là khoảng N2/2, có nghĩa là O(N2). Trong trường hợp tốt nhất, mỗi lần phân chia sẽ được 2 nửa dãy bằng nhau, khi đó thời gian thực hiện thuật toán T(N) sẽ được tính là: T(N) = 2T(N/2) + N Khi đó, T(N) ≈ NlogN. Trong trường hợp trung bình, thuật toán cũng có độ phức tạp khoảng 2NlogN = O(NlogN). Như vậy, quick sort là thuật toán rất hiệu quả trong đa số trường hợp. Tuy nhiên, đối với các trường hợp việc sắp xếp chỉ phải thực hiện một vài lần và số lượng dữ liệu cực lớn thì nên thực thi một số thuật toán khác có thời gian thực hiện trong mọi trường hợp là O(NlogN), sẽ xem xét ở phần sau, để đảm bảo trường hợp xấu nhất không xảy ra khi dùng quick sort. 7.4 HEAP SORT 7.4.1 Giới thiệu Heap sort là một giải thuật đảm bảo kể cả trong trường hợp xấu nhất thì thời gian thực hiện thuật toán cũng chỉ là O(NlogN). Ý tưởng cơ bản của giải thuật này là thực hiện sắp xếp thông qua việc tạo các heap, trong đó heap là 1 cây nhị phân hoàn chỉnh có tính chất là khóa ở nút cha bao giờ cũng lớn hơn khóa ở các nút con. Việc thực hiện giải thuật này được chia làm 2 giai đoạn. Đầu tiên là việc tạo heap từ dãy ban đầu. Theo định nghĩa của heap thì nút cha bao giờ cũng lớn hơn các nút con. Do vậy, nút gốc của heap bao giờ cũng là phần tử lớn nhất. Giai đoạn thứ 2 là việc sắp dãy dựa trên heap tạo được. Do nút gốc là nút lớn nhất nên nó sẽ được chuyển về vị trí cuối cùng của dãy và phần tử cuối cùng sẽ được thay vào gốc của heap. Khi đó ta có 1 cây mới, không phải heap, với số nút được bớt đi 1. Lại chuyển cây này về heap và lặp lại quá trình cho tới khi heap chỉ còn 1 nút. Đó chính là phần tử bé nhất của dãy và được đặt lên đầu. 7.4.2 Các thuật toán trên heap Như vậy, việc đầu tiên cần làm là phải tạo được 1 heap từ 1 dãy phần tử cho trước. Để làm việc này, cần thực hiện thao tác chèn 1 phần tử vào 1 heap đã có. Khi đó, kích thước của heap tăng lên 1, và ta đặt phần tử mới vào cuối heap. Việc này có thể làm vi phạm định nghĩa heap vì nút mới có thể lớn hơn nút cha của nó. Vấn đề này được giải quyết bằng cách đổi vị trí nút mới cho nút cha, và nếu vẫn vi phạm định nghĩa heap thì ta lại giải quyết theo cách tương tự cho đến khi có một heap mới hoàn chỉnh. Giả sử ta đã có 1 heap như sau: 98 Để chèn phần tử 61 vào heap, đầu tiên, ta đặt nó vào vị trí cuối cùng trong cây. Rõ ràng cây mới vi phạm định nghĩa heap vì nút con 61 lớn hơn nút cha 17. Tiến hành đổi vị trí 2 nút này cho nhau: Cây này vẫn tiếp tục vi phạm định nghĩa heap do nút con 61 lớn hơn nút cha 49. Lại đổi vị trí 61 cho 49. 98 49 53 17 06 25 32 98 49 53 17 06 25 32 61 98 49 53 61 06 25 32 17 98 61 53 49 06 25 32 17 99 Do nút con 61 nhỏ hơn nút cha 98 nên cây thoả mãn định nghĩa heap. Như vậy, ta đã có một heap với nút mới được thêm vào là 61. Để chèn một phần tử x vào 1 heap đã có k phần tử, ta gán phần tử thứ k +1, a[k], bằng x, rồi gọi thủ tục upheap(k). void upheap(int m){ int x; x=a[m]; while ((a[(m-1)/2]0)){ a[m]=a[(m-1)/2]; m=(m-1)/2; } a[m]=x; } void insert_heap(int x){ a[m]=x; upheap(m); m++; } Như vậy, với heap ban đầu chỉ có 1 phần tử là phần tử đầu tiên của dãy, ta lần lượt lấy các phần tử tiếp theo của dãy chèn vào heap sẽ tạo được 1 heap gồm toàn bộ n phần tử. Ta hãy xem xét quá trình tạo heap với dãy số đã cho ở phần trước. 32 17 49 98 06 25 53 61 Đầu tiên, tạo 1 heap với chỉ 1 phần tử là 32: Bước 1: Tiến hành chèn 17 vào heap. Do không vi phạm định nghĩa heap nên không thay đổi gì. Bước 2: Tiến hành chèn 49 vào heap. 32 32 17 100 Cây này vi phạm định nghĩa heap do 49>32 nên đổi vị trí 32 và 49 cho nhau. Cây mới thoả mãn định nghĩa heap. Bước 3: Tiến hành chèn 98 vào heap. Cây này vi phạm định nghĩa heap do 98>17 nên đổi vị trí 98 và 17 cho nhau. Cây mới lại vi phạm định nghĩa heap, do 98>49, nên đổi vị trí 98 cho 49. Cây này thoả mãn định nghĩa heap. 32 17 49 49 17 32 49 17 32 98 49 98 32 17 98 49 32 17 101 Bước 4: Tiến hành chèn 06 vào heap. Cây này thoả mãn định nghĩa heap do 06<49. Bước 5: Tiến hành chèn 25 vào heap. Cây này thoả mãn định nghĩa heap do 25<32. Bước 6: Tiến hành chèn 53 vào heap. Cây này vi phạm định nghĩa heap do 53>32 nên đổi vị trí 53 và 32 cho nhau. Cây mới thoả mãn định nghĩa heap. 98 49 32 17 06 98 49 32 17 06 25 98 49 32 17 06 25 53 98 49 53 17 06 25 32 102 Bước 7: Tiến hành chèn 61 vào heap. Cây này vi phạm định nghĩa heap do 61>17 nên đổi vị trí 61 và 17 cho nhau. Cây mới tiếp tục vi phạm định nghĩa heap do 61>49 nên đổi vị trí 61 và 49 cho nhau. Cây này thoản mãn định nghĩa heap, và chính là heap cần tạo. Sau khi tạo được heap, để tiến hành sắp xếp, ta cần lấy phần tử đầu và là phần tử lớn nhất của cây và thay thế nó bằng phần tử cuối của dãy. Điều này có thể làm vi phạm định nghĩa heap vì phần tử mới đưa lên gốc có thể nhỏ hơn 1 trong 2 nút con. Do đó, thao tác thứ 2 cần thực hiện trên heap là tiến hành chỉnh lại heap khi có 1 nút nào đó nhỏ hơn 1 trong 2 nút con của nó. Khi đó, ta sẽ tiến hành thay thế nút này cho nút con lớn hơn. 98 49 53 17 06 25 32 61 98 49 53 61 06 25 32 17 98 61 53 49 06 25 32 17 103 Nếu vẫn vi phạm định nghĩa heap thì ta lại lặp lại quá trình cho tới khi nó lớn hơn cả 2 nút con hoặc trở thành nút lá. Ta xem xét ví dụ với heap vừa tạo được ở phần trước: Lấy nút gốc 98 ra khỏi heap và thay thế bởi nút cuối là 17. Cây này không thoả mãn định nghĩa heap vì 17 nhỏ hơn cả 2 nút con là 61 và 53. Tiến hành đổi chỗ 17 cho nút con lớn hơn là 61. Vẫn tiếp tục vi phạm định nghĩa heap do 17 nhỏ hơn nút con là 49. Tiến hành đổi chỗ 17 cho 49, ta có heap mới hoàn chỉnh. Ta có thủ tục downheap để chỉnh lại heap khi nút k không thoả mãn định nghĩa heap như sau: 98 61 53 49 06 25 32 17 17 61 53 49 06 25 32 61 17 53 49 06 25 32 61 49 53 17 06 25 32 104 void downheap(int k){ int j, x; x=a[k]; while (k<=(m-2)/2){ j=2*k+1; if (j<m-1) if (a[j]<a[j+1]) j++; if (x>=a[j]) break; a[k]=a[j]; k=j; } a[k]=x; } Trong thủ tục này, nút k sẽ được kiểm tra. Nếu nó vi phạm định nghĩa heap thì sẽ được thay bởi 1 trong 2 nút con (nút lớn hơn) tại vị trí 2*k và 2*k+1. Sau khi hoán đổi vị trí, nếu vẫn tiếp tục vi phạm định nghĩa heap thì việc hoán đổi lại được thực hiện. Quá trình tiếp tục cho đến khi không còn vi phạm hoặc tới nút lá. Cuối cùng, thủ tục heap sort thực hiện việc sắp xếp trên heap đã tạo như sau: int remove_node(){ int temp; temp=a[0]; a[0]=a[m]; m--; downheap(0); return temp; } void heap_sort(){ int i; m=0; for (i=0; i<=n-1; i++) insert_heap(a[i]); m=n-1; for (i=n-1; i>=0; i--) a[i]=remove_node(); } Trong đoạn mã trên, hàm remove() sẽ trả về giá trị là nút gốc của heap. Nút này sẽ được chuyển xuống cuối heap, và nút cuối được đổi lên gốc. Kích thước của heap giảm đi 1, tiến hành gọi thủ tục downheap để chỉnh lại heap mới. Thủ tục heap sort đầu tiên tạo 1 heap bằng cách lần lượt chèn các phần tử của dãy vào heap. Tiếp theo, các nút gốc lần lượt được lấy ra, heap mới được tạo và chỉnh lại. Quá trình kết thúc khi heap không còn phần tử nào. Một trong nhưng tính chất của heap sort khiến nó rất được quan tâm trong thực tế đó là thời gian thực hiện thuật toán luôn là O(NlogN) trong mọi trường hợp, bất kể dữ liệu đầu vào có tính 105 chất như thế nào. Đây cũng là ưu điểm của heap sort so với quick sort, thuật toán có thời gian thực hiện nhanh nhưng trong trường hợp xấu nhất thì thời gian lên tới O(N2). 7.5 MERGE SORT (SẮP XẾP TRỘN) 7.5.1 Giới thiệu Tương tự như heap sort, merge sort cũng là một giải thuật sắp xếp có thời gian thực hiện là O(NlogN) trong mọi trường hợp. Ý tưởng của giải thuật này bắt nguồn từ việc trộn 2 danh sách đã được sắp xếp thành 1 danh sách mới cũng được sắp. Rõ ràng việc trộn 2 dãy đã sắp thành 1 dãy mới được sắp có thể tận dụng đặc điểm đã sắp của 2 dãy con. Để thực hiện giải thuật sắp xếp trộn đối với 1 dãy bất kỳ, đầu tiên, coi mỗi phần tử của dãy là 1 danh sách con gồm 1 phần tử đã được sắp. Tiếp theo, tiến hành trộn từng cặp 2 dãy con 1 phần tử kề nhau để tạo thành các dãy con 2 phần tử được sắp. Các dãy con 2 phần tử được sắp này lại được trộn với nhau tạo thành dãy con 4 phần tử được sắp. Quá trình tiếp tục đến khi chỉ còn 1 dãy con duy nhất được sắp, đó chính dãy ban đầu. 7.5.2 Trộn 2 dãy đã sắp Thao tác đầu tiên cần thực hiện khi sắp xếp trộn là việc tiến hành trộn 2 dãy đã sắp thành 1 dãy mới cũng được sắp. Để làm việc này, ta sử dụng 2 biến duyệt từ đầu mỗi dãy. Tại mỗi bước, tiến hành so sánh giá trị của 2 phần tử tại vị trí của 2 biến duyệt. Nếu phần tử nào có giá trị nhỏ hơn, ta đưa phần tử đó xuống dãy mới và tăng biến duyệt tương ứng lên 1. Quá trình lặp lại cho tới khi tất cả các phần tử của cả 2 dãy đã được duyệt và xét. Giả sử ta có 2 dãy đã sắp như sau: 17 32 49 98 06 25 53 61 Để trộn 2 dãy, ta sử dụng một dãy thứ 3 để chứa các phần tử của dãy tổng. Một biến duyệt k dùng để lưu giữ vị trí cần chèn tiếp theo trong dãy mới. Bước 1: Phần tử tại vị trí biến duyệt j là 06 nhỏ hơn phần tử tại vị trí biến duyệt i là 17 nên ta đưa 06 xuống dãy mới và tăng j lên 1. Đồng thời, biến duyệt k cũng tăng lên 1. 17 32 49 98 06 25 53 61 06 i j i j k 106 Bước 2: Phần tử tại vị trí i là 17 nhỏ hơn phần tử tại vị trí j là 25 nên ta đưa 17 xuống dãy mới và tăng i lên 1, biến duyệt k cũng tăng lên 1. 17 32 49 98 06 25 53 61 06 17 Bước 3: Phần tử tại vị trí j là 25 nhỏ hơn phần tử tại vị trí i là 32 nên ta đưa 25 xuống dãy mới và tăng j lên 1, biến duyệt k cũng tăng lên 1. 17 32 49 98 06 25 53 61 06 17 25 Bước 4: Phần tử tại vị trí i là 32 nhỏ hơn phần tử tại vị trí j là 53 nên ta đưa 32 xuống dãy mới và tăng i lên 1, biến duyệt k cũng tăng lên 1. 17 32 49 98 06 25 53 61 06 17 25 32 Bước 5: Phần tử tại vị trí i là 49 nhỏ hơn phần tử tại vị trí j là 53 nên ta đưa 49 xuống dãy mới và tăng i lên 1, biến duyệt k cũng tăng lên 1. 17 32 49 98 06 25 53 61 06 17 25 32 49 i j k i j k i j k i j k 107 Bước 6: Phần tử tại vị trí j là 53 nhỏ hơn phần tử tại vị trí i là 98 nên ta đưa 53 xuống dãy mới và tăng j lên 1, biến duyệt k cũng tăng lên 1. 17 32 49 98 06 25 53 61 06 17 25 32 49 53 Bước 7: Phần tử tại vị trí j là 61 nhỏ hơn phần tử tại vị trí i là 98 nên ta đưa 61 xuống dãy mới và tăng j lên 1, biến duyệt k cũng tăng lên 1. 17 32 49 98 06 25 53 61 06 17 25 32 49 53 61 Bước 8: Biến duyệt j đã duyệt hết dãy thứ 2. Khi đó, ta tiến hành đưa toàn bộ phần còn lại của dãy 1 xuống dãy mới. 17 32 49 98 06 25 53 61 06 17 25 32 49 53 61 98 Như vậy, ta có dãy mới là dãy đã sắp, bao gồm các phần tử của 2 dãy ban đầu. Thủ tục tiến hành trộn 2 dãy đã sắp như sau: void merge(int *c, int cl, int *a, int al, int ar, int *b, int bl, int br){ int i=al, j=bl, k; for (k=cl; k< cl+ar-al+br-bl+1; k++){ if (i>ar){ c[k]=b[j++]; i j k i j k i j k 108 continue; } if (j>br){ c[k]=a[i++]; continue; } if (a[i]<b[j]) c[k]=a[i++]; else c[k]=b[j++]; } } Thủ tục này tiến hành trộn 2 dãy a và b, với các chỉ số đầu và cuối tương ứng là al, ar, bl, br. Kết quả trộn được lưu trong mảng c, có chỉ số đầu là cl. Tuy nhiên, ta thấy rằng để thực hiện sắp xếp trộn thì 2 dãy được trộn không phải là 2 dãy riêng biệt, mà nằm trên cùng 1 mảng. Hay nói cách khác là ta trộn 2 phần của 1 dãy chứ không phải 2 dãy riêng biệt a và b như trong thủ tục trên. Ngoài ra, kết quả trộn lại được lưu ngay tại dãy ban đầu chứ không lưu ra một dãy c khác. Do vậy, ta phải cải tiến thủ tục trên để thực hiện trộn 2 phần của 1 dãy và kết quả trộn được lưu lại ngay trên dãy đó. void merge(int *a, int al, int am, int ar){ int i=al, j=am+1, k; for (k=al; k<=ar; k++){ if (i>am){ c[k]=a[j++]; continue; } if (j>ar){ c[k]=a[i++]; continue; } if (a[i]<a[j]) c[k]=a[i++]; else c[k]=a[j++]; } for (k=al; k<=ar; k++) a[k]=c[k]; } Thủ tục này tiến hành trộn 2 phần của dãy a. Phần đầu có chỉ số từ al đến am, phần sau có chỉ số từ am+1 đến ar. Ta dùng 1 mảng tạm c để lưu kết quả trộn, sau đó sao chép lại kết quả vào mảng ban đầu a. 7.5.3 Sắp xếp trộn 109 Để tiến hành sắp xếp trộn, đầu tiên ta coi các phần tử của dãy như các dãy con 1 phần tử. Tiến hành trộn từng cặp 2 dãy con này để được các dãy con được sắp gồm 2 phần tử. Tiếp tục tiến hành trộn từng cặp dãy con 2 phần tử đã sắp để tạo thành các dãy con được sắp gồm 4 phần tử v.v. Quá trình lặp lại cho tới khi toàn bộ dãy được sắp. Ta xét quá trình sắp xếp trộn với dãy ở phần trước. 32 17 49 98 06 25 53 61 Đầu tiên, coi mỗi phần tử của dãy như 1 dãy con đã sắp gồm 1 phần tử. Tiến hành trộn từng cặp dãy con 1 phần tử với nhau: 32 17 49 98 06 25 53 61 Sau bước này ta được các dãy con đã sắp gồm 2 phần tử. Tiến hành trộn các cặp dãy con đã sắp gồm 2 phần tử để tạo thành dãy con được sắp gồm 4 phần tử. 17 32 49 98 06 25 53 61 Sau bước này ta được các dãy con đã sắp gồm 4 phần tử. Tiến hành trộn 2 dãy con đã sắp gồm 4 phần tử. 17 32 49 98 06 25 53 61 Cuối cùng, ta có toàn bộ dãy đã được sắp: 06 17 25 32 49 53 61 98 Cài đặt cho thuật toán merge_sort bằng đệ qui như sau : void merge_sort(int *a, int left, int right){ int middle; if (right<=left) return; middle=(right+left)/2; merge_sort(a, left, middle); merge_sort(a, middle+1, right); merge(a, left, middle ,right); } 110 Trong thủ tục này, đầu tiên ta tiến hành chia dãy cần sắp làm 2 nửa, sau đó thực hiện lời gọi đệ qui merge_sort cho mỗi nửa dãy. Hai lời gọi đệ qui này đảm bảo rằng mỗi nửa dãy này sẽ được sắp. Cuối cùng, thủ tục merge được gọi để trộn 2 nửa dãy đã sắp này. 7.6 BÀI TOÁN TÌM KIẾM Tìm kiếm là một thao tác rất quan trọng đối với nhiều ứng dụng tin học. Tìm kiếm có thể định nghĩa là việc thu thập một số thông tin nào đó từ một khối thông tin lớn đã được lưu trữ trước đó. Thông tin khi lưu trữ thường được chia thành các bản ghi, mỗi bản ghi có một giá trị khoá để phục vụ cho mục đích tìm kiếm. Mục tiêu của việc tìm kiếm là tìm tất cả các bản ghi có giá trị khoá trùng với một giá trị cho trước. Khi tìm được bản ghi này, các thông tin đi kèm trong bản ghi sẽ được thu thập và xử lý. Một ví dụ về ứng dụng thực tiễn của tìm kiếm là từ điển máy tính. Trong từ điển có rất nhiều mục từ, khoá của mỗi mục từ chính là cách viết của từ. Thông tin đi kèm là định nghĩa của từ, cách phát âm, các thông tin khác như loại từ, từ đồng nghĩa, khác nghĩa v.v. Ngoài ra còn rất nhiều ví dụ khác về ứng dụng của tìm kiếm, chẳng hạn một ngân hàng lưu trữ các bản ghi thông tin về khách hàng và muốn tìm trong danh sách này một bản ghi của một khách hàng nào đó để kiểm tra số dư và thực hiện các giao dịch, hoặc một chương trình tìm kiếm duyệt qua các tệp văn bản trên máy tính để tìm các văn bản có chứa các từ khoá nào đó. Trong phần tiếo theo, chúng ta sẽ xem xét 2 phương pháp tìm kiếm phổ biến nhất, đó là tìm kiếm tuần tự và tìm kiếm nhị phân. 7.7 TÌM KIẾM TUẦN TỰ Tìm kiếm tuần tự là một phương pháp tìm kiếm rất đơn giản, lần lượt duyệt qua toàn bộ các bản ghi một cách tuần tự. Tại mỗi bước, khoá của bản ghi sẽ được so sánh với giá trị cần tìm. Quá trình tìm kiếm kết thúc khi đã tìm thấy bản ghi có khoá thoả mãn hoặc đã duyệt hết danh sách. Thủ tục tìm kiếm tuần tự trên một mảng các số nguyên như sau: int sequential_search(int *a, int x, int n){ int i; for (i=0; i<n ; i ++){ if (a[i] == X) return(i); } return(-1); } Thủ tục này tiến hành duyệt từ đầu mảng. Nếu tại vị trí nào đó, giá trị phần tử bằng với giá trị cần tìm thì hàm trả về chỉ số tương ứng của phần tử trong mảng. Nếu không tìm thấy giá trị trong toàn bộ mảng thì hàm trả về giá trị -1. Thuật toán tìm kiếm tuần tự có thời gian thực hiện là O(n). Trong trường hợp xấu nhất, thuật toán mất n lần thực hiện so sánh và mất khoảng n/2 lần so sánh trong trường hợp trung bình. 7.8 TÌM KIẾM NHỊ PHÂN Trong trường hợp số bản ghi cần tìm rất lớn, việc tìm kiếm tuần tự có thể là 1 giải pháp không hiệu quả về mặt thời gian. Một giải pháp tìm kiếm khác hiệu quả hơn có thể được sử dụng 111 dựa trên mô hình “chia để trị” như sau: Chia tập cần tìm làm 2 nửa, xác định nửa chứa bản ghi cần tìm và tập trung tìm kiếm trên nửa đó. Để làm được điều này, tập các phần tử cần phải được sắp, và sử dụng chỉ số của mảng để xác định nửa cần tìm. Đầu tiên, so sánh giá trị cần tìm với giá trị của phần tử ở giữa. Nếu nó nhỏ hơn, tiến hành tìm ở nửa đầu dãy, ngược lại, tiến hành tìm ở nửa sau của dãy. Qúa trình được lặp lại tương tự cho nữa dãy vừa được xác định này. Hàm tìm kiếm nhị phân được cài đặt như sau (giả sử dãy a đã được sắp): int binary_search(int *a, int x){ int k, left =0, right=n-1; do{ k=(left+right)/2; if (x<a[k]) right=k-1; else l=k+1; }while ((x!=a[k]) && (left<=right)) if (x=a[k]) return k; else return -1; } Trong thủ tục này, x là giá trị cần tìm trong dãy a. Hai biến left và right dùng để giới hạn phân đoạn của mảng mà quá trình tìm kiếm sẽ được thực hiện trong mỗi bước. Đầu tiên 2 biến này được gán giá trị 0 và n-1, tức là toàn bộ mảng sẽ được tìm kiếm. Tại mỗi bước, biến k sẽ được gán cho chỉ số giữa của đoạn đang được tiến hành tìm kiếm. Nếu giá trị x nhỏ hơn giá trị phần tử tại k, biến right sẽ được gán bằng k-1, cho biết quá trình tìm tại bước sau sẽ được thực hiện trong nửa đầu của đoạn. Ngược lại, giá trị left được gán bằng k+1, cho biết quá trình tìm tại bước sau sẽ được thực hiện trong nửa sau của đoạn. 06 17 25 32 49 53 61 98 Xét 1 ví dụ với dãy đã sắp ở trên, để tìm kiếm giá trị 61 trong dãy, ta tiến hành các bước như sau: Bước 1: Phân chia dãy làm 2 nửa, với chỉ số phân cách là 3. 0 1 2 3 4 5 6 7 06 17 25 32 49 53 61 98 Giá trị phần tử tại chỉ số này là 32, nhỏ hơn giá trị cần tìm là 61. Do vậy, tiến hành tìm kiếm phần tử tại nửa sau của dãy. Bước 2: Tiếp tục phân chia đoạn cần tìm làm 2 nửa, với chỉ số phân cách là 5. 112 4 5 6 7 49 53 61 98 Giá trị phần tử tại chỉ số này là 53, nhỏ hơn giá trị cần tìm là 61. Do vậy, tiến hành tìm kiếm phần tử tại nửa sau của đoạn. Bước 3: Tiếp tục phân chia đoạn, với chỉ số phân cách là 6. 6 7 61 98 Giá trị phần tử tại chỉ số này là 61, bằng giá trị cần tìm. Do vậy, quá trình tìm kiếm kết thúc, chỉ số cần tìm là 6. Thuật toán tìm kiếm nhị phân có thời gian thực hiện là lgN. Tuy nhiên, thuật toán đòi hỏi dãy đã được sắp trước khi tiến hành tìm kiếm. Do vậy, nên áp dụng tìm kiếm nhị phân khi việc tìm kiếm phải thực hiện nhiều lần trên 1 tập phần tử cho trước. Khi đó, ta chỉ cần tiến hành sắp tập phần tử 1 lần và thực hiện tìm kiếm nhiều lần trên tập phần tử đã sắp này. 7.9 CÂY NHỊ PHÂN TÌM KIẾM Tìm kiếm bằng cây nhị phân là một phương pháp tìm kiếm rất hiệu quả và được xem như là một trong những thuật toán cơ sở của khoa học máy tính. Đây cũng là một phương pháp đơn giản và được lựa chọn để áp dụng trong rất nhiều tình huống thực tế. Ý tưởng cơ bản của phương pháp này là xây dựng một cây nhị phân tìm kiếm. Đó là một cây nhị phân có tính chất sau: Với mỗi nút của cây, khoá của các nút của cây con bên trái bao giờ cũng nhỏ hơn và khoá của các nút của cây con bên phải bao giờ cũng lớn hơn hoặc bằng khoá của nút đó. Như vậy, trong một cây nhị phân tìm kiếm thì tất cả các cây con của nó đều thoả mãn tính chất như vậy. Hình 7.2 Ví dụ về cây nhị phân tìm kiếm 7.9.1 Tìm kiếm trên cây nhị phân tìm kiếm 49 25 61 17 32 53 98 06 113 Việc tiến hành tìm kiếm trên cây nhị phân tìm kiếm cũng tương tự như phương pháp tìm kiếm nhị phân đã nói ở trên. Để tìm một nút có k