Xem mẫu

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 ... - tailieumienphi.vn
nguon tai.lieu . vn