Sau 9 lần đi mảng M trở thành: M: 2 5 10 10 15 20 22 25 30 35 - Phân tích thuật toán: + Trong mọi trường hợp: Số phép gán: G = 0 Số phép so sánh: S = (N-1) + (N-2) + + 1 = ½N(N-1) + Trong trường hợp tốt nhất: khi mảng ban đầu đã có thứ tự tăng Số phép hoán vị: Hmin = 0 + Trong trường hợp xấu nhất: khi mảng ban đầu đã có thứ tự giảm Số phép hoán vị: Hmin = (N-1) + (N-2) + + 1. | Chương 2 KỸ THUẬT TÌM KIEM SEARCHING . Khái quát về tìm kiếm Trong thực tế khi thao tác khai thác dữ liệu chúng ta hầu như lúc nào cũng phải thực hiện thao tác tìm kiếm. Việc tìm kiếm nhanh hay chậm tùy thuOc vào trạng thái và trát tư cùa dữ liệu trến đó. Kết quá cùa việc tìm kiếm co thế lá không co không tìm thấy hoác co tìm thay . Nếu kết quá tìm kiếm lá co tìm tháy thì nhiệu khi chung ta con phái xác định xếm vị trí của phán tử dữ liệu tìm thay lá ở đáu Trong pham vi cua chương náy chung ta tìm cách giai quyết các cáu hoi náy. Trữởc khi đi váo nghiến cứu chi tiết chung ta giá sử ráng moi phán tử dữ liệu đữởc Xếm xệt co một thánh phán khoa Kệy đệ nhận diện co kiếu dữ liệu lá T náo đo các thánh phán con lai lá thong tin Info liến quan đến phán tử dữ liệu đo. Nhữ váy moi phán tữ dữ liệu co cau truc dữ liệu nhữ sau typếdếf struct DátáElệmệnt T Kệy InfoTypệ Info DataType Trong tái liệu náy khi noi tơi giá trị cua mọt phán tử dữ liệu chung tá muon noi tơi giá trị khoa Kệy cua phán tữ dữ liệu đo. Đệ đơn gián chung tá giá sử ráng moi phán tử dữ liệu chỉ lá thánh phán khoa nhán diện. Việc tìm kiếm mot phán tử co thế diện ra trện mot dãy máng tìm kiếm nOi hoác diện ra trện mOt táp tin file tìm kiếm ngoai . Phán tử cán tìm lá phán tử cán thoa mán điệu kiện tìm kiếm thữơng co giá trị báng giá trị tìm kiếm . Tuy thuOc váo tững bái toán cu thệ má điệu kiện tìm kiếm co thế khác nhau song chung quy việc tìm kiếm dữ liệu thữơng đữơc ván dụng thệo các thuát toán trình bay sau đáy. . Các giải thuát tìm kiếm nội Tìm kiếm trền dáy máng . Đặ t van đề Giá sử chung tá co mOt manj M gồm N phán tủ . Van đệ đát ra lá co hay khong phán tử co giá trị báng X trong manj M Nếu co thì phán tữ co giá trị báng X lá phán tử thứ may trong manj M . Tìm tuyền tính Linear Search Thuát toán tìm tuyến tính con đữơc goi lá Thuát toán tìm kiếm tuán tự Sệquệntiál Sệarch . a. Tư tưởng Lán lữơt so sánh các phán tử cua manj M vơi giá trị X bát đáu tữ phán tử đáu tiện cho đến khi tìm đến đữơc .
