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

Chia sẻ: You You | Ngày: | Loại File: PDF | Số trang:79

Thêm vào BST

Báo xấu

101
lượt xem 17
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 2 của bài giảng Cấu trúc dữ liệu và thuật toán trang bị cho người học những kiến thức về tìm kiếm và sắp xếp. Trong chương này các bạn sẽ được tìm hiểu về các giải thuật tìm kiếm và các giải thuật sắp xếp. Mời các bạn cùng tham khảo để nắm bắt các nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 2: Tìm kiếm và sắp xếp

Chương 2 TÌM KiẾM & SẮP XẾP 2.1. Các giải thuật tìm kiếm 2.1.1. Bài toán tìm kiếm 2.1.2. Giải thuật tìm kiếm tuyến tính 2.1.3. Giải thuật Tìm kiếm nhị phân 2.2. Các giải thuật sắp xếp 2.2.1. Bài toán sắp xếp 3.2.1 Giải thuật ñổi chổ trực tiếp –Interchange Sort 3.2.2 Giải thuật chọn trực tiếp-Selection Sort 3.2.3 Giải thuật chèn trực tiếp-Insert Sort 3.2.4 Giải thuật nổi bọt – Bubble Sort 3.2.5 Giải thuật nhanh – Quick Sort 1 2.3. Bài tập © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
2.1 Các Giải Thuật Tìm Kiếm 2.1.1. Bài toán tìm kiếm 2.1.2. Giải thuật tìm kiếm tuyến tính 2.1.3. Giải thuật Tìm kiếm nhị phân 2 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
2.1.1 Bài Toán Tìm Kiếm Trong thực tế, khi thao tác, khai thác dữ liệu hầu như lúc nào cũng phải thực hiện thao tác tìm kiếm. Kết quả của việc tìm kiếm có thể là không tìm thấy hoặc tìm thấy. Nếu kết quả là tìm thấy thì nhiều khi còn phải xác ñịnh xem vị trí của phần tử tìm thấy là ở ñâu? Việc tìm kiếm nhanh hay chậm tùy thuộc vào trạng thái và trật tự của dữ liệu trên ñó. Có 2 thuật toán chính: Tìm kiếm tuyến tính & Tìm kiếm nhị phân 3 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
Giả sử chúng ta có một mảng M gồm N phần tử. Vấn ñề ñặt ra là có hay không phần tử có giá trị bằng X trong mảng M? Nếu có thì phần tử có giá trị bằng X là phần tử thứ mấy trong mảng M? 4 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
2.1.2. Giải Thuật Tìm Kiếm Tuyến Tính Ý Tưởng: Tiến hành so sánh x với phần tử thứ nhất, thứ hai…của mảng A cho ñến khi gặp ñược phần tử có khóa cần tìm, hoặc ñã tìm hết mảng mà không thấy x. Ưu ñiểm: Thuật toán này có thể cho ta thực hiện tìm kiếm khi các phần tử trong mảng chưa ñược sắp xếp. Nhược ñiểm: Sẽ mất rất nhiều thời gian nếu như không có phần tử chúng ta cần tìm. 5 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
Minh Họa Chưa VD:Tìm x = 14 Tìm thấy tại hết vị trí thứ 5 mảng 14 12 3 5 1 14 9 0 10 2 7 1 2 3 4 5 6 7 8 9 10 HếtChưa mảng VD:Tìm x = 30 hếttìm không mảng thấy 30 12 3 5 1 14 9 0 10 2 7 1 2 3 4 5 6 7 8 9 10 6 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
Giải thuật: 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[i] với x, có 2 khả năng. • a[i] = x ; // Tìm thấy.Dừng • a[i] != x ; // Thực hiện bước 3. Bước 3 : • i = i+1; // xét phần tử kế tiếp 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. 7 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
Cài ðặt Int Timtuyentinh (int a[] , int N , int x) { int i = 0; while((i < N) && (a[i] != x)) i++; if( i == N) return -1 ; // tìm hết mảng nhưng không có x else return i ; //a[i] là phần tử có khóa x. } ðánh giá giải thuật ðộ phức tập tính toán cấp n: T(n)=O(n) 8 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
2.1.3 Giải Thuật Tìm Kiếm Nhị Phân Ý Tưởng: - Lần tìm kiếm ban ñầu là phần tử ñầu tiên của dãy (First = 1) ñến phần tử cuối cùng của dãy (Last = N). - So sánh giá trị X với giá trị phần tử ñứng ở giữa của dãy M là M[Mid]. - Nếu X = M[Mid]: Tìm thấy - Nếu X < M[Mid]: Rút ngắn phạm vi tìm kiếm về nửa ñầu của dãy M (Last = Mid–1) - Nếu X > M[Mid]: Rút ngắn phạm vi tìm kiếm về nửa sau của dãy M (First = Mid+1) - Lặp lại quá trình này cho ñến khi tìm thấy phần tử có giá trị X hoặc phạm vi tìm kiếm không còn nữa (First > Last). 9 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
Ưu ñiểm: Thuật toán tìm nhị phân sẽ rút ngắn ñáng kể thời gian tìm kiếm. Nhược ñiểm: Chỉ thực hiện ñược trên dãy ñã có thứ tự. 10 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
Minh Họa Tìm giá trị X = 85 (Tìm thấy) Mid = 5 M[mid]= 46 F M L 17 12 23 34 46 59 69 77 85 90 X X > M[mid] 11 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
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 59 69 77 85 90 X X > M[mid] 12 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
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 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
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): Lần First>L X= X< X> First Last Mid M[Mid] lặp 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 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
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) Lần First> X= X< X> First Last Mid M[Mid] lặp 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 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
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 16 Bkt: Kết thúc © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
Cài ðặt int Timnhiphan(int M[ ], int N, int X){ int First = 1; int Last = N; while (First
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 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
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 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM
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 © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM