Xem mẫu

  1. Minh H a Tìm giá tr X = 85 (Tìm th y) Mid = 5 M[mid]= 46 M F L 1 12 23 34 46 69 77 85 90 7 59 X X > M[mid] 11 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
  2. Minh H a Tìm giá tr X = 85 (Tìm th y) Mid = 8 M[mid] = 77 F M L 7 12 23 34 46 69 77 85 90 59 X X > M[mid] 12 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
  3. Minh H a Tìm giá tr X = 85 (Tìm th y) Mid = 9 M[mid] = 85 M F L 7 12 23 34 46 59 69 77 85 90 ðã tìm X th y t i v trí 9 X = M[mid] 13 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
  4. Minh H a Gi s dãy M g m 10 ph n t có khóa như sau (N = 10). 2 3 4 5 8 15 17 22 25 30 Tìm ki m ph n t có giá tr X = 5 (tìm th y): Ln First>L X= X< X> First Last Mid M[Mid] lp ast M[Mid] M[Mid] M[Mid] B.ñ u 1 10 False 5 8 False True False 1 1 4 False 2 3 False False True 2 3 4 False 3 4 False False True 3 4 4 False 4 5 True 14 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
  5. Minh H a Gi s dãy M g m 10 ph n t có khóa như sau (N=10). 1 3 4 5 8 15 17 22 25 30 Tìm ki m ph n t có giá tr X = 7 (không tìm th y) Ln First> X= X< X> First Last Mid M[Mid] lp Last M[Mid] M[Mid] M[Mid] B.ñ u 1 10 False 5 8 False True False 1 1 4 False 2 3 False False True 2 3 4 False 3 4 False False True 3 4 4 False 4 5 False False True 4 5 4 True 15 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
  6. Gi i thu t: 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]) B5.1: Tìm th y t i v trí Mid B5.2: Th c hi n Bkt B6: IF (X < M[Mid]) B6.1: Last = Mid – 1 B6.2: L p l i B3 B7: IF (X > M[Mid]) B7.1: First = Mid + 1 B7.2: L p l i B3 Bkt: K t thúc 16 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
  7. Cài ð t int Timnhiphan(int M[ ], int N, int X){ int First = 1; int Last = N; while (First
  8. 2.2 Các gi i thu t s p x p 2.2.1. Bài toán s p x p 2.2.2. Gi i thu t ñ i ch tr c ti p –Interchange Sort 2.2.3. Gi i thu t ch n tr c ti p-Selection Sort 2.2.4. Gi i thu t chèn tr c ti p-Insert Sort 2.2.5. Gi i thu t n i b t – Bubble Sort 2.2.6. Gi i thu t nhanh – Quick Sort 18 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
  9. 2.2.1. Bài Toán S p X p ð thu n ti n và gi m thi u th i gian thao tác mà ñ c bi t là ñ tìm ki m. Do v y s p x p d li u là m t trong nh ng thao tác c n thi t và thư ng g p trong quá trình lưu tr , qu n lý d li u. S p x p là quá trình x lý m t danh sách các ph n t ñ ñ t chúng theo m t th t tăng ho c gi m d a trên n i dung lưu tr trên m i ph n t . Có r t nhi u thu t toán s p x p song chúng ta ch quan tâm ñ n 5 gi i thu t s p x p thư ng s d ng. 19 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
  10. Khái ni m v ngh ch th : a1 a2 a3 .......... an-1 an Gi s m ng có th t tăng d n, n u iaj thì g i là ngh ch th M c tiêu c a s p x p là kh các ngh ch th (b ng cách hoán v các ph n t ) 20 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
nguon tai.lieu . vn