Chương 2 TÌM KIẾM & SẮP XẾP

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

Thêm vào BST

Báo xấu

129
lượt xem 40
download

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

Đây là bước các SEOer quan tâm nhiều nhất. Sau khi website của bạn đã được index trong data center của Google. Nó sẽ được đánh giá và xếp hạng để hiển thị ra ngoài trang kết quả tìm kiếm (SERP) thông qua thuật toán của

Chủ đề:

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

Lưu

Nội dung Text: Chương 2 TÌM KIẾM & 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 2.3. Bài tập 1 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
 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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
 Minh Họa Chưa Tìm thấy VD:Tìm x = 14 h ết tại vị trí thứ mảng 14 5 12 3 5 1 9 0 10 2 7 14 1 2 3 4 5 6 7 8 9 10 HếtChảa m ưng VD:Tìm x = 30 khôngếtìm ht mảng t h ấy 30 12 3 5 1 14 9 0 10 2 7 1 2 3 4 5 6 7 8 9 10 6 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
 Giải thuật: Bước 1 : // Bắt đầu từ phần tử đầu tiên của dãy i = 1; 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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
 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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
Ư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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
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 59 69 77 85 90 7 X X > M[mid] 11 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
 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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
 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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
 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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net
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 Khoa KTCN Trường ĐH KTKT B.Dương © Dương Thành Phết-www.thayphet.net