tailieunhanh - Giáo trình giải thuật - tìm kiếm và sắp xếp

* Tìm kiếm và sắp xếp là 2 bài toán rất kinh điển trong tin học * Tìm kiếm là thao tác được thực hiện nhiều nhất trong các hệ thống lưu trữ và quản lý dữ liệu - Tra từ điển, tìm kiếm sinh viên, tìm kiếm khách hàng. - Thao tác tìm kiếm sẽ thực hiện hiệu quả khi dữ liệu được tổ chức theo một trật tự nào đó. | H2ffWM0 . Nội dung 1. Bài toán tìm kiếm và sắp xếp 2. Một sôi phương pháp tìm kiếm 3. Một sôi phương pháp sắp xếp . Bài toán tìm kiếm và sắp xếp 0 Tìm kiêm và sắp xếp là 2 bài toán rất kinh điên trong tin học 0 Tìm kiếm là thao tác được thực hiện nhiều nhất trong các hệ thông lưu trữ và quản lý dữ liệu Tra từ điển tìm kiếm sinh viên tìm kiếm khách hàng . Thao tác tìm kiếm sẽ thực hiện hiệu quả khi dữ liệu được tổ chức theo một trật tự nào đó 0 Sắp xếp dữ liệu cũng là yêu cầu cần phải có trong các hệ thông thông tin quản lý . 1 H2 WM0 Bài toán tìm kiêm và sắp xếp 0 Bài toán tìm kiêm Cho một tập gồm N phần tử dữ liệu. Cho biết sự tồn tại hoặc chỉ ra vị trí xuất hiện của một phần tử nào đó với thông tin xác định được cho trước 0 Bài toán sắp xếp Cho một tập gồm N phần tử dữ liệu. Sắp xếp các phần tử dữ liệu có thứ tự tăng hoặc giảm dần theo một tiêu chí cho trước Bài toán tìm kiêm và sắp xếp 0 Tính hiệu quả của các phương pháp tìm kiếm và sắp xếp phụ thuộc vào tính chất Của CTDL 0 Các phương pháp tìm kiếm và sắp xếp cũng phụ thuộc vào dữ liệu lưu trữ ở bộ nhớ trong hay bộ nhớ ngoài 0 Các giải thuật được trình bày dành cho dữ liệu lưu trữ ở bộ nhớ trong . Nội dung 1. Bài toán tìm kiếm và sắp xếp 2. Một số phương pháp tìm kiếm 3. Một sô phương pháp sắp xếp 2 lEKWJifl Bài toán tìm kiếm 0 Bài toán Cho mảng 1 chiều A gồm N phần tử nguyên. Cho biết số nguyên x có tồn tại trong A hay không Nếu có thì cho biết 1 vị trí xuất hiện của x trong A Input Mảng A gồm N phần tử nguyên số nguyên x Ouput p 0 là vị trí xuất hiện của x trong A p 0 nếu x không tồn tại trong A 7 Tìm kiếm tuần tự Ý tưởng Xét lần lượt từng phần tử trong toàn bộ không gian tìm kiếm để tìm ra 1 phần tử thỏa tiêu chí hoặc không tìm thấy phần tử nào thỏa tiêu chí Thao tác dừng lại ngay khi tìm thấy phần tử đầu tiên thỏa tiêu chí hoặc xét hết tất cả phần .