TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - TS. Nguyễn Thị Kim Thoa

Bài giảng "Cấu trúc dữ liệu và giải thuật" Chương 5 Các giải thuật sắp xếp và tìm kiếm, cung cấp cho người học những kiến thức như Điều kiện bài toán sắp xếp; giải thuật sắp xếp lựa chọn; giải thuật sắp xếp lựa chọn – cài đặt hàm; sắp xếp kiểu thêm dần/chèn; . Mời các bạn cùng tham khảo! | Chương 5 CÁC GIẢI THUẬT SẮP XẾP VÀ TÌM KIẾM Data structures and Algorithms 2 18 2021 Cấu trúc dữ liệu và giải thuật 1 Bài toán sắp xếp trên cấu trúc mảng Sắp xếp cơ bản Sắp xếp kiểu lựa chọn Selection - sort Sắp xếp chèn thêm dần Insertion- sort Sắp xếp đổi chỗ nổi bọt Exchange Bubble - sort Sắp xếp nâng cao sắp xếp nhanh Sắp xếp nhanh Quick-sort Sắp xếp trộn Merge-sort Sắp xếp vun đống Heap-sort 2 18 2021 Cấu trúc dữ liệu và giải thuật 2 Điều kiện bài toán sắp xếp Dãy A có n phần tử A 1 A 2 A n Sắp xếp dãy A theo thứ tự tăng dần hoặc giảm dần 2 18 2021 Cấu trúc dữ liệu và giải thuật 3 Sắp xếp kiểu lựa chọn Selection - sort No. Min A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 32 51 27 83 66 11 45 75 1 11 11 51 27 83 66 32 45 75 2 27 11 27 51 83 66 32 45 75 3 32 11 27 32 83 66 51 45 75 4 45 11 27 32 45 66 51 83 75 5 51 11 27 32 45 51 66 83 75 6 66 11 27 32 45 51 66 83 75 7 75 11 27 32 45 51 66 75 83 Chiến thuật Chọn số nhỏ nhất trong dãy chưa được sắp xếp và đổi chỗ với số đang chiếm vị trí đầu tiên của dãy này 2 18 2021 Cấu trúc dữ liệu và giải thuật 4 Giải thuật sắp xếp lựa chọn Bước 1 Thiết lập Min 1 là vị trí đầu tiên của dãy Bước 2 Tìm kiếm phần tử nhỏ nhất trong danh sách Bước 3 Tráo đổi giá trị tại vị trí Min Bước 4 Tăng Min để trỏ tới vị trí tiếp theo Bước 5 Lặp lại từ bước 2 cho đến khi danh sách được sắp xếp 2 18 2021 Cấu trúc dữ liệu và giải thuật 5 Giải thuật sắp xếp lựa chọn Procedure SELECTION_SORT A n for i 1 to n-1 do Min i for j i 1 to n do if A j lt A Min then Min j EndFor If Mini then temp A Min A Min A i A i temp EndFor Return Đánh giá giải thuật Số vòng lặp for cần thực thi là Ctb n-1 n-2 1 n-1 n-1 1 2 Do đó T n O n2 2 18 2021 Cấu trúc dữ liệu và giải thuật 6 Giải thuật sắp xếp lựa chọn cài đặt hàm void SELECTION_SORT int A int n int Min for int i 0 i lt n-1 i Min i for int j i 1 j lt n j if A j lt A Min Min j if Min i int temp A Min A Min A i A i temp 2 18 2021 Cấu trúc dữ liệu và giải thuật 7 Sắp xếp kiểu thêm dần chèn Insertion sort No. Số so A 1 A 2 A 3

• Cơ sở dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu và giải thuật
• Giải thuật sắp xếp
• Bài toán sắp xếp trên cấu trúc mảng
• Cấu trúc mảng
• Giải thuật sắp xếp chè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 tập Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu
• 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
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu cơ bản
• Kiểu dữ liệu trừu tượng
• Tổng quan về giải thuật
• Kiểu dữ liệu
• Các tiêu chuẩn đánh giá dữ liệu
• Cách diễn đạt giải thuật
• Phân tích giải thuật
• phân tích thiết kế
• thiết kế hướng đối tượng
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm