TAILIEUCHUNG - Bài giảng Phân tích thiết kế giải thuật và cấu trúc dữ liệu: Phần 2 - ĐH CNTT&TT

Phần 2 của bài giảng Phân tích thiết kế giải thuật và cấu trúc dữ liệu đi sâu tìm hiểu các cách tổ chức dữ liệu và thuật toán trên kiểu dữ liệu đó. Với mục đích cung cấp cho các bạn sinh viên một cái nhìn toàn thể và cơ bản. Tác giả kỳ vọng kết thúc môn học người học sẽ nắm được những cách tổ chức và cấu trúc dữ liệu. Từ đó áp dụng một phần kiến thức ấy vào nghiên cứu những mảng khác hiệu quả, tối ưu hơn. | Chương 4 CÁC THUẬT TOÁN SẮP XẾP . Các thuật toán sắp xếp cơ bản . Sắp xếp chọn Selection Sort Giải thuật Đây là phương pháp sắp xếp đơn giản nhất được tiến hành như sau Đầu tiên chọn phần tử có khóa nhỏ nhất trong n phần tử từ a 1 đến a n và hoán vị nó với phần tử a 1 . Chọn phần tử có khóa nhỏ nhất trong n-1phần tử từ a 2 đến a n và hoán vị nó với a 2 . Tổng quát ở bước thứ i chọn phần tử có khoá nhỏ nhất trong n-i 1 phần tử từ a i đến a n và hoán vị nó với a i . Sau n-1 bước này thì mảng đã được sắp xếp. Phương pháp này được gọi là phương pháp chọn bởi vì nó lặp lại quá trình chọn phần tử nhỏ nhất trong số các phần tử chưa được sắp. Ví dụ 2-1 Sắp xếp mảng gồm 10 mẩu tin có khóa là các số nguyên 5 6 2 2 10 12 9 10 9 và 3 Bước 1 Ta chọn được phần tử có khoá nhỏ nhất bằng 2 trong các phần tử từ a 1 đến a 10 là a 3 hoán đổi a 1 và a 3 cho nhau. Sau bước này thì a 1 có khoá nhỏ nhất là 2. Bước 2 Ta chọn được phần tử có khoá nhỏ nhất bằng 2 trong các phần tử từ a 2 đến a 10 là a 4 hoán đổi a 2 và a 4 cho nhau. Tiếp tục quá trình này và sau 9 bước thì kết thúc. 57 Bảng sau ghi lại các giá trị khoá tương ứng với từng bước. Kh0a B1IỠC l 42 43J 44 45 4 5 47 4M 49 410 Ban dan 5 6 2 2 LO 12 9 10 9 3 B1IŨC J 2 6 5 2 10 12 9 lữ 9 3 Biufcl 2 5 6 LO 12 9 lũ 9 3 Bum 3 3 6 LO 12 9 lũ 9 5 BwcJ 5 10 12 9 10 9 0 Birâc 5 6 12 9 10 9 10 Bum 6 9 12 10 9 10 Bum 7 9 10 12 10 BirôcS 10 12 10 BiiúcS 10 12 KỄt quà 2 2 3 5 Ế 9 9 10 10 12 Bảng Các bước thực hiện sắp xếp chọn Chương trình PROCEDURE SelectionSort VAR i j LowIndex integer LowKey KeyType BEGIN 1 FOR i 1 TO n-1 DO BEGIN 2 LowIndex i 3 LowKey a i .key 4 FOR j i 1 TO n DO 5 IF a j .key LowKey THEN BEGIN 6 LowKey a j .key 7 LowIndex j END 8 Swap a i a LowIndex END 58 END Đánh giá Phương pháp sắp xếp chọn lấy O n để sắp xếp n phần tử. Trước hết ta có thủ tục Swap lấy một hằng thời gian như đã nói ở mục . Các lệnh 2 3 đều lấy O 1 thời gian. Vòng lặp for 4 - 7 thực hiện n-i lần vì j chạy từ i 1 đến n mỗi lần lấy O 1 nên

• Cơ sở dữ liệu
• Phân tích giải thuật
• Thiết kế giải thuật
• Cấu trúc dữ liệu
• Thuật toán sắp xếp
• Thuật toán tìm kiếm
• Phép toán trên cây
• Phân tích thiết kế giải thuật
• Bài giảng Phân tích thiết kế giải thuật
• Phân tích thuật toán
• Phương pháp phân tích thuật toán
• Vai trò của phân tích thuật toán
• Quá trình phân tích thuật toán
• Kỹ thuật thiết kế giải thuật
• Bài giảng thiết kế giải thuật
• Kỹ thuật phân tích thiết kế giải thuật
• Giải thuật xấp xỉ
• Bài toán che phủ đỉnh
• Bài toán NP đầy đủ
• Phân tích thiết kế giải thuật chương 37
• Hệ thức truy hồi
• Độ phức tạp giải thuật
• Phân tích giải thuật lặp
• Phân tích giải thuật đệ quy
• Phân tích thuật toán sắp xếp
• Phân tích thuật toán tìm kiếm
• Giải tích đại cương
• Kỹ thuật giải & kinh nghiệm thi giải tích
• Giải tích cuối kì 2
• Tích phân bội
• Tích phân đường
• Tích phân mặt
• Bài giảng Phân tích thiết kế
• Phân tích thiết kế dữ liệu
• Tiêu chuẩn đánh giá giải thuật
• Phương pháp đánh giá giải thuật
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Kỹ thuật phân tích giải thuật
• Đánh giá giải thuật
• Single Source Shortest Paths
• Phân tích thiết kế giải thuật chương 10
• Giải bài toán các đường đi ngắn nhất
• Biểu diễn các đường đi ngắn nhất
• Cây khung nhỏ nhất
• Giải thuật tổng quát
• Giải thuật của Kruskal
• Giải thuật của Prim
• Phương pháp thiết kế thuật giải
• Thuật toán chính xác
• Thuật toán gần đúng
• Bước thiết kế một thuật giải
• Bài tập giải sẵn Giải tích I
• Giải tích I
• Lý thuyết giải tích
• Câu hỏi giải tích
• Ôn tập giải tích
• Tích phân bất định
• Phân tích thiết kế thuật toán
• Thiết kế thuật toán
• Bài giảng Phân tích thiết kế thuật toán
• Kỹ thuật phân tích thuật toán
• Đánh giá một giải thuật
• Chia để trị
• Giải thuật quay lui
• Giải thuật tìm kiếm trong đồ thị
• Biểu diễn của một đồ thị
• Biểu diễn một đồ thị vô hướng
• Biểu diễn một đồ thị có hướng
• Đề thi thử tốt nghiệp THPT Quốc gia
• Đề thi thử tốt nghiệp THPTQG 2021
• Ôn thi THPT Quốc gia 2021
• Kỹ thuật giải Toán tích phân
• Nguyên hàm tích phân
• Hàm lượng giác
• Tích phân từng phần
• Phương trình vi phân
• Ứng dụng của tích phân
• Cắt tỉa Alpha Beta
• Đánh giá độ phức tạp thuật toán
• Đánh giá thuật toán dựa trên thực nghiệm
• Phân tích câu lệnh
• Qui tắc phân tích câu lệnh trong thuật toán
• Giải thuật nâng cao
• Hệ thống thông tin
• Giải thuật hình học
• Giải thuật so khớp chuỗi
• Hình học tính toán
• Giải thuật thô sơ
• Kỹ thuật quét
• Tính đúng đắn
• Kỹ thuật mã hóa
• bài giảng
• giải thuật nhánh và cận
• giải thuật DFS
• bài toán DFS
• Biểu diễn dữ liệu
• Giải thuật đệ quy