Cấu trúc dữ liệu và giải thuật - Chương 2 - Tìm kiếm và sắp xếp

Tài liệu tham khảo Cấu trúc dữ liệu và giải thuật - Chương 2 - Tìm kiếm và sắp xếp
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật - Chương 2 - Tìm kiếm và sắp xếpC u trúc d li u và gi i thu t (Data structure and Algorithms) 1Chương II. Tìm ki m và s p x p 2I. CÁC GI I THU T TÌM KI M N I 1. Tìm ki m tuy n tính 2. Tìm ki m nh phânII. CÁC GI I THU T S P X P N I 1. Ch n tr c ti p (Selection sort) 2. Chèn tr c ti p (Insertion sort) 3. i ch tr c ti p (Interchange sort) 4. N i b t (Buble sort) 5. S p x p cây (Heap sort) 6. S p x p d a trên phân ho ch (Quick sort) 7. S p x p tr n tr c ti p (Merge sort ) 3I. CÁC GI I THU T TÌM KI M N I 1. Tìm ki m tuy n tính 2. Tìm ki m nh phân 4* Bài toán tìm ki m Cho dãy n ph n t , gi s chúng ư c lưu tr dư i d ng m ng a[1],• a[2], …., a[n], và các ph n t là s t nhiên. Hãy tìm v trí c a ph n t có giá tr là x trong m ng••Có 2 phương pháp tìm ki m: Tìm ki n tuy n tính Tìm ki m nh phân 51. Tìm ki m tuy n tính a. Tư tư ng gi i thu t Ti n hành so sánh x l n lư t v i ph n t th nh t, th 2, …., c a m ng cho n khi g p ư c ph n t có khoá c n tìm, ho c tìm h t m ng mà không th y x. Các bư c ti n hành như sau: Bư c 1: i:=1; // b t u t ph n t u tiên c a dãy Bư c 2: So sánh a[1] v i x, có 2 kh năng a[i]=x: Tìm th y. D ng a[i] x: Sang Bư c 3 Bư c 3: i:=i+1; // xét ti p ph n t k trong m ng N u i>n: H t m ng không tìm th y. D ng Ngư c l i: L p l i Bư c 2. 61. Tìm ki m tuy n tính b. Ví d : Cho dãy s a: 12 2 8 5 1 6 4 15 x=8 Hãy tìm ph n t Các bư c ti n hành như sau: 71. Tìm ki m tuy n tính b. Ví d : i=1 : a[1]8 12 2 8 5 1 6 4 15 X=8 81. Tìm ki m tuy n tính b. Ví d : i=2 : a[2]8 12 2 8 5 1 6 4 15 X=8 91. Tìm ki m tuy n tính b. Ví d : i=3 : a[3]=8=x 12 2 8 5 1 6 4 15 X=8 • K t qu : Tìm th y x=8 v trí th 3! 101. Tìm ki m tuy n tínhc. Thu t toán Function TuyenTinh (A, n, X) {N u tìm th y X, hàm tr v giá tr là v trí c a x trong dãy, ngư c l i tr v giá tr 0} Begin 1) { Kh i u} i:=1; 2) {Tìm khoá x trong dãy} While (a[i] x)and (i1. Tìm ki m tuy n tínhd. Nh n xét M i l n th c hi n l p while ph i ti n hành ki m tra 2 i m ki n i 1. Tìm ki m tuy n tính e. ánh giá gi i thu t Trư ng h p S l n so sánh Gi i thíchT t nh t 1 Ph n t u tiên có giá tr xX u nh t N+1 Ph n t cu i cùng có giá tr x ho c không tìm th y xTrung bình (N+1)/2 Gi s xác su t các ph n t trong m ng nh n giá tr x là như nhau ph c t p thu t toán T(n)=O(n) 132. Tìm ki m nh phân• Áp d ng v i nh ng dãy ã có th t (gi s th t tăng), cácph n t trong dãy có quan h ai-1 2. Tìm ki m nh phâna. Tư tư ng thu t toán - Gi s dãy tìm ki m g m các ph n t a[Left], …, a[Right] các bư c ti n hành như sau: Bư c 1: left:=1; right:=N // Tìm ki m trên t t c các ph nt Bư c 2: mid:= (left+right) div 2 // l y m c so sánh So sánh a[mid] v i x có 3 kh năng a[mid]=x: Tìm th y. D ng a[i] >x: Tìm ti p x trong dãy con trái a[Left], …, a[mid-1] Right:=mid-1; a[i] 2. Tìm ki m Nh phân b. Ví d : Cho dãy s a: 1 2 4 5 6 8 12 15 x=8 Hãy tìm ph n t Các bư c ti n hành như sau: 162. Tìm ki m Nh phân b. Ví d : left=1; right=8; mid=4 1 2 4 5 6 8 12 15 X=8 •So sánh (x=8) > (a[mid]=5) Tìm ki m n a bên ph i left:=4+1=5 right:=8 mid:=(left+right) div 2=6 172. Tìm ki m Nh phân b. Ví d : left=5; right=8; mid=6 1 2 4 5 6 8 12 15 X=8 • So sánh x= a[mid]=8 Tìm th y x=8 v ...