Cấu trúc dữ liệu và giải thuật - Chương 2 - Tìm kiếm và sắp xếp
lượt xem 127
download
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
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Cấu trúc dữ liệu và giải thuật - Chương 2 - Tìm kiếm và sắp xếp
- C u trúc d li u và gi i thu t (Data structure and Algorithms) 1
- Chương II. Tìm ki m và s p x p 2
- I. 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 II. 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 ) 3
- I. 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 5
- 1. 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. 6
- 1. 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: 7
- 1. 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 8
- 1. 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 9
- 1. 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! 10
- 1. Tìm ki m tuy n tính c. 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 (i
- 1. Tìm ki m tuy n tính d. 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ích T t nh t 1 Ph n t u tiên có giá tr x X u nh t N+1 Ph n t cu i cùng có giá tr x ho c không tìm th y x Trung 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) 13
- 2. 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ác ph n t trong dãy có quan h ai-1
- 2. Tìm ki m nh phân a. 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: 16
- 2. 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 17
- 2. 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 trí 6 ! • D ng 18
- c. Thu t toán tìm ki m nh phân Function NhiPhan (A, n, X) {Cho dãy A g m n ph n t tăng d n. Gi i thu t này tìm xem trong dãy có ph n t nào có giá tr b ng X hay không. ây dùng các bi n l, r, m ghi nh n ch s ph n t u, ph n t cu i, ph n t gi a c a dãy. N u tìm ki m ư c tho , giá tr cho ra là v trí c a ph n t , n u không thì cho ra giá tr 0} Begin 1) { Kh i u} l:=1; r:=n; 2) {Tìm} While l
- 2. Tìm ki m Nh phân d. ánh giá gi i thu t Trư ng h p S l n so sánh Gi i thích T t nh t 1 Ph n t u tiên có giá tr x X u nh t log2n Không có x trong m ng Log2n/2 Trung bình 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(log2n) 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Giáo trình cấu trúc dữ liệu và giải thuât part 1
16 p | 822 | 365
-
Giáo trình cấu trúc dữ liệu và giải thuât part 2
16 p | 546 | 286
-
Bài giảng Cấu trúc dữ liệu - Bài 1:Tổng quan về cấu trúc dữ liệu và giải thuật
47 p | 172 | 17
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen - Bùi Tiến Lên
25 p | 72 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Các khái niệm cơ bản về Cấu trúc dữ liệu và giải thuật
20 p | 42 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu
193 p | 55 | 7
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)
62 p | 94 | 6
-
Giáo trình Cấu trúc dữ liệu và giải thuật - CĐ Nghề Đắk Lắk
60 p | 40 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (Trường Đại học Hồng Bàng )
62 p | 155 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Chương 1: Tổng quan về giải thuật và cấu trúc dữ liệu
10 p | 63 | 4
-
Giáo trình Cấu trúc dữ liệu và giải thuật (Ngành: Công nghệ thông tin - Cao đẳng) - Trường Cao đẳng Xây dựng số 1
77 p | 6 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)
67 p | 103 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Một số khái niệm cơ bản về cấu trúc dữ liệu và giải thuật
12 p | 91 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Tổng quan - Nguyễn Đức Cương
6 p | 99 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 1: Cấu trúc dữ liệu và giải thuật
42 p | 52 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Th.S Thiều Quang Trung
41 p | 67 | 3
-
Giáo trình Cấu trúc dữ liệu và giải thuật (Nghề: Công nghệ thông tin - Trung cấp) - Trường Trung cấp Công nghệ và Du lịch Hà Nội
59 p | 9 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Ngô Quang Thạch
49 p | 60 | 3
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn