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

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 2: Tìm kiếm và sắp xếp nội" cung cấp cho người đọc các kiến thức: Các giải thuật tìm kiếm nội, các giải thuật sắp xếp nội. nội dung chi tiết. | CHƯƠNG 2 Nội Dung Nội Dung Tt TÌM KIẾM VÀ SẮP XẾP NỘI 1 Các giải thuật tìm kiếm nội 1. Tìm kiếm tuyến tính 2. Tìm kiếm nhị phân Các giải thuật sắp xếp nội 1. Đổi chỗ trực tiếp - Interchange Sort 2. Chọn trực tiếp - Selection Sort 3. Nổi bọt - Bubble Sort 2 4. Chèn trực tiếp - Insertion Sort 5. Chèn nhị phân - Binary Insertion Sort 6. Shaker Sort 7. Shell Sort I 8. Heap Sort 5 9. Quick Sort I 10. Merge Sort I 11. Radix Sort ị 3 JT Bài Toán Tìm Kiếm Tìm Kiếm Tuyến Tính Thuật Toán Tìm Kiếm Tuyến Tính Cho danh sách có n phần tử a0 a1 a2. an-1. Để đơn giản trong việc trình bày giải thuật ta dùng mảng 1 chiều a để lưu danh sách các phần tử nói trên trong bộ nhớ chính. Tìm phần tử có khoá bằng X trong mảng Giải thuật tìm kiếm tuyến tính tìm tuần tự Giải thuật tìm kiếm nhị phân Lưu ý Trong quá trình trình bày thuật giải ta dùng ngôn ngữ lập trình C. 4 Ý tưởng So sánh X lần lượt với phần tử thứ 1 thứ 2 .của mảng a cho đến khi gặp được khóa cần tìm hoặc tìm hết mảng mà không thấy. Các bước tiến hành Bước 1 Khởi gán i 0 Bước 2 So sánh a i với giá trị x cần tìm có 2 khả năng a i x tìm thấy x. Dừng a i x sang bước 3 Bước 3 i i 1 Xét tiếp phần tử kế tiếp trong mảng Nếu i N Hết mảng. Dừng Ngược lại Lặp lại bước 2 5 Hàm trả về 1 nếu tìm thấy ngược lại trả về 0 int LinearSearch int a int n int x int i 0 while i n a i x i if i n return 0 Tìm không thấy x else return 1 Tìm thấy 6 1 ĩSỊ Minh Họa Thuật Toán Tìm Kiếm Tuyến Tính Minh Họa Thuật Toán Tìm Kiếm Tuyến Tính tt Tìm thấy 6 tại vị trí 4 i 7 không tìm thấy 0123456 5 Đánh Giá Thuật Toán Tìm Tuyến Tính Trường hợp Css Tốt nhất 1 Xấu nhất N Trung bình N 1 2 Độ phức tạp O N - Cải Tiến Thuật Toán Tìm Tuyến Tính Thuật Toán Tìm Kiếm Nhị Phân Các Bước Thuật Toán Tìm Kiếm Nhị Phân 0 1 2 3 4 5 6 2 Nhận xét Số phép so sánh của thuật toán trong trường hợp xấu nhất là 2 n. Để giảm thiểu số phép so sánh trong vòng lặp cho thuật toán ta thêm phần tử lính canh vào cuối dãy. int LinearSearch int a int n int x int i 0 a n x a n là phần tử lính canh

• Cơ sở dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu
• Cơ sở dữ liệu
• Giải thuật tìm kiếm nội
• Giải thuật sắp xếp nội
• Tìm kiếm nhị phân
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• tài liệu Cấu trúc dữ liệu và giải thuật
• giáo trình Cấu trúc dữ liệu và giải thuật
• bài giảng Cấu trúc dữ liệu và giải thuật
• bài tập Cấu trúc dữ liệu và giải thuật
• Ngôn ngữ diễn đạt giải thuật
• Thiết kế và phân tích giải thuật
• Giải thuật đệ quy
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Tổng quan về giải thuật
• Kiểu dữ liệu
• Các tiêu chuẩn đánh giá dữ liệu
• phân tích thiết kế
• thiết kế hướng đối tượng
• Cách diễn đạt giải thuật
• Phân tích giải thuật
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp