TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu & thuật toán: Chương 5 - Nguyễn Đức Nghĩa

Bài giảng Cấu trúc dữ liệu & thuật toán - Chương 5: Sắp xếp (Sorting) giúp người học nắm được các kiến thức về bài toán sắp xếp, ba thuật toán sắp xếp cơ bản, sắp xếp trộn, sắp xếp nhanh, sắp xếp vun đống, cận dưới cho độ phức tạp tính toán của bài toán sắp xếp và các phương trình sắp xếp đặc biệt. | Chương 5 Sắp xếp Sorting Heap Sort Quick Sort William A. Martin Sorting. ACM Computing Surveys Vol. 3 Nr 4 Dec 1971 pp. 147-174. .The bibliography appearing at the end of this article lists 37 sorting algorithms and 100 books and papers on sorting published in the last 20 years. Suggestions are made for choosing the algorithm best suited to a given situation. D. Knuth 40 thời gian hoạt động của các máy tính là dành cho sắp xếp NGUYỄN ĐỨC NGHĨA Bộ môn KHMT - ĐHBKHN NỘI DUNG . Bài toán sắp xếp . Ba thuật toán sắp xếp cơ bản . Sắp xếp trộn Merge Sort . Sắp xếp nhanh Quick Sort . Sắp xếp vun đống Heap Sort . Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp . Các phương pháp sắp xếp đặc biệt NGUYỄN ĐỨC NGHĨA Bộ môn KHMT - ĐHBKHN 2 . Bài toán sắp xếp . Bài toán sắp xếp . Giới thiệu sơ lược về các thuật toán sắp xếp 3 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT - ĐHBKHN . Bài toán sắp xếp Sắp xếp Sorting - Là quá trình tổ chức lại họ các dữ liệu theo thứ tự giảm dần hoặc tăng dần ascending or descending order Dữ liệu cần sắp xếp có thể là - Số nguyên Integers - Xâu ký tự Character strings - Đối tượng Objects Khoá sắp xếp Sort key - Là bộ phận của bản ghi xác định thứ tự sắp xếp của bản ghi trong họ các bản ghi. - Ta cần sắp xếp các bản ghi theo thứ tự của các khoá. NGUYỄN ĐỨC NGHĨA Bộ môn KHMT - ĐHBKHN 4 . Bài toán săp xêp Chú ý Việc sắp xếp tiến hành trực tiếp trên bản ghi đòi hỏi di chuyển vị trí bản ghi có thể là thao tác rất tốn kém. Vì vậy người ta thường xây dựng bảng khoá gồm các bản ghi chỉ có hai trường là khoá con trỏ - trường khoá chứa giá trị khoá - trường con trỏ để ghi địa chỉ của bản ghi tương ứng. Việc sắp xếp theo khoá trên bảng khoá không làm thay đổi bảng chính nhưng trình tự các bản ghi trong bảng khoá cho phép xác định trình tự các bản ghi trong bảng chính. phép xác định trình tự các bản ghi trong bảng chính. NGUYỄN ĐỨC NGHĨA Bộ môn KHMT - ĐHBKHN 5 . Bài toán săp xêp . Bài toán săp xêp Ta có thể hạn chế .

• Kỹ thuật lập trình
• Bài giảng Cấu trúc dữ liệu thuật toán
• Cấu trúc dữ liệu thuật toán
• Bài toán sắp xếp
• Ba thuật toán sắp xếp cơ bản
• Sắp xếp trộn
• Sắp xếp nhanh
• Cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• 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
• Cơ sở dữ liệu
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Giải thuật toán
• Thuật toán đồ thị
• Cấu trúc dữ liệu cơ bản
• Thuật toán nén dữ liệu
• Đánh giá thuật toán RLE
• Thuật toán nén RLE
• Bài giảng Cấu trúc dữ liệu và thuật toán
• Cấu trúc dữ liệu và thuật toán
• Các cấu trúc dữ liệu cơ bản
• Kiểu dữ liệu trừu tượng
• Bài toán toán tin học
• Đặc tả vấn đề
• thuật toán
• tài liệu cấu trúc dữ liệu
• giáo trình cấu trúc dữ liệu
• thuật toán trong cấu trúc 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 Phần 2
• Biểu diễn thuật toán
• Cấu trúc dữ liệu ngăn xếp
• Hàng đợi
• Biểu thức toán học
• Phân tích giải thuật
• Tiêu chuẩn đánh giá cấu trúc dữ liệu
• Độ phức tạp của thuật toán
• Thuật toán duyệt đồ thị
• Bài toán duyệt cây nhị phân
• Biểu diễn cây nhị phân
• Cấu trúc Dữ liệu và Giải thuật Phần 1
• Bài toán tìm kiếm
• Phương pháp sắp xếp
• Các thuật toán sắp xếp
• Phương pháp sắp xếp đặc biệt
• Các kỹ thuật thiết kế thuật toán
• Thuật toán đệ qui
• Phân tích thuật toán đệ qui
• Đệ qui có nhớ
• Thuật toán đệ quy
• Cấu trúc dữ liệu động
• Kiểu dữ liệu con trỏ
• Danh sách liên kết