Hướng dẫn chi tiết giải thuật- tìm kiếm

Tham khảo tài liệu hướng dẫn chi tiết giải thuật- tìm kiếm, công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Hướng dẫn chi tiết giải thuật- tìm kiếm Hướng dẫn chi tiết các giải thuật tìm kiếmMerge sortNguyên tắc :VD ta có12 13 45 32 100 34 65 10Ta có ở trên là 8 phần tử cần được sắp xếp :Ý tưởng của merge sort là thay vì sắp xếp 8 phần tử (khó sắp ) thì ta chia đôi dãy đó ra làmđôi (số phần tử nhỏ hơn --> sắp dễ hơn ) và sắp xếp các dãy con rồi ghép 2 dãy con lại( gọi là merge 2 dãy con )Vậy ta làm như sau:Chia đôi --> được hai dãy con mới là 12 13 45 32 và 100 34 65 10sắp 2 dãy con lại : 12 13 45 32 gọi là dãy A100 34 65 10 gọi là dãy B+ Muốn sắp A ta cũng làm y như trênChia đôi A , được 2 dãy mới là A11 = { 12 13 } A12 = {45 32 }Chia đôi B được 2 dãy mới là B11 = {100 34} B12 = {65 10 }+ Sắp xếp A11, B11 , A12 , B12+ Muốn sắp xếp A11 thì ta cũng chia đôi đến khi sắp đượcta có 2 dãy con là A21 = {12} A22 = { 13}Sắp 2 dãy con trên được ( đơn giản vì chỉ có một phần tử ) là A21 = {12 } A22 = {13}Sắp xong thì ta merge lại thành A11 = { 12 13 }+ Tương tự sắp xếp cho B11 , A12 , B12 ta cũng cóB11 = {34 100} B12 = {10 65 } A12 = {32 45 }+Sắp xếp xong , ta sẽ merge lại A11 , A12 thành A = { 12 13 32 45 }B11 , B12 thành B = { 10 34 65 100 }Sắp xong A , B , ta sẽ merge chúng lại thành dãy ban đầu :{10 12 13 32 34 45 65 100 }Phương pháp merge:VD A = { 12 13 32 45 }B = { 10 34 65 100}Đầu tiên lấy phần tử đầu tiên của A và B : 12 và 1010 < 12 nên ta lấy 10 bỏ vào mảng kết quả là C = {10}Giử lại số 12 , và lấy tiếp phần tử thay thế 10 trong mảng B là 34So sánh 12 và 34 . 12 < 34 , lấy 12 ra và bỏ vào C = {10 12}Giử lại 34 . Lấy phần tử kế tiếp để thay cho 12 trong mảng A là 32So sánh 32 và 34 chọn 32 bỏ vảo C = { 10 12 32 }........ Làm tương tự ......Đến bước cuối cùng A hết phần tử B còn lại B = { 65 100}Ta sẽ bỏ toàn bộ mảng B vào C . Kết quả C đã được merge và có thứ tựGiải thuật cho trường hợp dùng list để chứa các phần tử cần sort)Sortable_List là một lớp list có đặc điểm là có hàm sortNode là một template class biểu diễn cho các node trong listRecord là class dùng để biểu diễn data cần sắp xếp . ( VD như sắp một dãy các số nguyên ,hay VD là sắp theo tên của các record bao gồm tên , tuổi , số điện thoại ...)sublist là list cần sắp xếpQuick sortÝ tưởng:Gần giống như merge sort , ta sẽ chia đôi mảng cần xếp rồi sắp xếp các mảng con , sau đósẽ ghép mảng con đã sắp xếp thành mảng ban đầu nhưng đã sắp xếpĐiểm khác nhau: Là chổ ta chia đôi mảng con theo nguyên tắc riêng :Gọi điểm mà tại đó ta chia đôi mảng ban đầu có trị là pivot (không nhất thiết là nằm đúngvị trí chính giữa . Nhưng giải thuật sẽ chạy tốt nếu nó nằm gần điểm chính giữa) và ta sẽkhông cần merge 2 dãy con (do đó nhìn chung sẽ chạy nhanh hơn ) , thỏa điều kiện là tất cảnhững phần tử bên trái pivot đều nhỏ hơn pivot và nằm bên phải pivot thì lớn hơn pivotVD :2 4 6 7 18 14 13Ta chọn phần tử pivot = 7 ( do bên trái của nó nhỏ hơn pivot = 7 , bên phải lớn hơn pivot =7 ) (Thực ra ta phải tìm pivot , do ở đây làm bằng tay nên dễ thấy )Chia đôi : A = { 2 4 6 } B = { 18 14 13 }+ Sắp A+ Trong dãy A ta cũng chọn phần tử pivot là 4+ Được 2 dãy con là A11 = {2 } A12 = {6}+ Sắp A11 ( sắp sẵn rồi )+ Sắp A12 ( sắp sẵn rồi )+ Tạo lại mảng A = { A11 được sắp , pivot , A12 được sắp } = {2 4 6 }+Sắp B . Trong B ta không thấy được pivot do chọn cái nào ta cũng không thấy thỏa .Nhưng mục tiêu của quick sort là làm sao ta được dãy pivot < D= dãy có trị lớn hơn pivot >Sắp 2 dãy con C , D rồi ghép lại ta được dãy sắp thứ tự .Vì vậy áp dụng một giải thuật tìm pivot trong B( sẽ trình bày sau ) ta sẽ được C = { 13} D= {18} và pivot là 14 .+ Sắp dãy con C , D ( do chỉ có một phần tử nên không sắp , hoặc tìm pivot)+ Ghép lại tạo thành mảng B được sắp B = { 13 14 18 }+Ghép A và B để tạo thành mảng được sắp xếp ban đầuPS : Hiệu quả của giải thuật quicksort phụ thuộc rất nhiều vào việc chọn cho được pivottốt ( tức nếu pivot nằm gần chính giữa thì đạt gần tối ưu )Heap SortHeap là một cấu trúc dữ liệu , có thể được biểu diễn thông qua 2 cách :-Dạng thứ 1: Dạng cây nhị phân có đặc điểm là node cha thì lớn hơn 2 node con trực tiếpcủa nó .-Dạng thứ 2: nếu ta đánh số các node theo thứ tự từ trên xuống và từ trái qua . Bắt đầu lànode root = 0 , thì ta có thể định nghĩa heap thông qua mảng một chiều , có đặc điểm làphần tử thứ k sẽ lớn hơn các phần tử thứ 2k+1 và 2k+2 . Ta có thể dễ nhận thấy là phàn tửthứ 0 sẽ tương ứng với root trong cây ở cách biểu diễn thứ 1Nguyên tắc sắp xếp của heap sortDựa vào tính chất của heap trong cách biểu diễn thứ 1 và thứ 2 , ta có thể thấy phần tử đầutiên trong cách biểu diễn theo mảng sẽ là phần tử lớn nhất ---> cách sắp xếp đơn giản là : (Gọi mảng ban đầu là A )Khởi tạo : Tạo heap từ mảng ban đầu đã cho (mảng A )1. Lấy phần tử đầu tiên trong mảng ra bỏ vào mảng kết quả2. Tạo lại heap từ mảng A3.Quay lại bước 1VD : Ta lấy một mảng đã được tạo thành một heap :yrpdfbkacLấy ph ...