TAILIEUCHUNG - Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 6 - ThS. Phạm Thanh An

Chương 6 trình bày kiến thức về "Sắp xếp". Mục tiêu học tập của chương này là trình bày các thuật toán thông dụng cho việc sắp xếp trong (sắp xếp trên bộ nhớ trong - RAM), minh họa các thuật toán và đánh giá thuật toán. . | Chương 6: Sắp xếp Ths. Phạm Thanh An Bộ môn Khoa học máy tính - Khoa CNTT Trường Đại học Ngân hàng Mục tiêu Trình bày các thuật toán thông dụng cho việc sắp xếp trong (sắp xếp trên bộ nhớ trong - RAM) Minh họa các thuật toán Đánh giá thuật toán Tại sao cần phải sắp xếp dữ liệu Chúng ta cần có trật tự yêu cầu nào đó trên tập dữ liệu Chúng ta cần thực hiện các phép tìm kiếm nhị phân, chỉ mục một CSDL Là bước khởi đầu cho nhiều giải thuật trên tập dữ liệu SẮP XẾP (SORTING) Ví dụ 1: Sắp xếp một danh sách sinh viên theo vần A, B, C Sắp xếp theo thứ tự điểm tổng kết từ cao đến thấp để xét học bổng sinh viên SẮP XẾP (SORTING) Ví dụ 2: Sắp xếp một danh sách cán bộ theo mức thu nhập Sắp xếp danh sách các các em học sinh theo trật tự xếp hàng: thấp đứng trước, cao đứng sau SẮP XẾP (SORTING) Định nghĩa Sắp xếp là quá trình tổ chức lại tập dữ liệu theo một trật tự tăng dần hay giảm dần Hai mô hình sắp xếp Sắp xếp trong (internal), các phần tử cần sắp xếp được lưu sẵn trong RAM Sắp xếp ngoài (external), một số các phần tử cần sắp xếp lưu trong RAM, còn lại được lưu ở bộ nhớ ngoài Các phương pháp sắp xếp Các thuật toán cơ bản Thuật toán “Selection sort” Thuật toán “Insertion sort” Thuật toán “Buble sort” Thuật toán “Heap sort” Thuật toán “Quick sort” Để tiện trình bày, giả sử sắp xếp các phần tử trên mảng A, N phần tử : A [0], A [1], A [2], , A [N-1]. Sắp xếp lựa chọn (selection sort) Ý tưởng: Giải thuật “selection sort” sắp xếp một danh sách các giá trị bằng cách lặp lại việc đặt một giá trị cụ thể vào đúng vị trí thích hợp cho nó trong dãy sắp xếp Nói cách khác, với mỗi vị trí trong danh sách, giải thuật đi tìm giá trị phù hợp cho vị trí đó. Sắp xếp lựa chọn (Selection sort) Ví dụ: sắp xếp một dãy các số nguyên theo trật tự tăng dần, ta làm như sau: Ở bước thứ i, chọn phần tử nhỏ nhất trong dãy a[i], a[i+1], , a[n] Đổi chỗ phần tử này với phần tử a[i] Sắp xếp lựa chọn (Selection sort) 44 55 12 42 94 18 06 67 44 55 12 42 94 18 06 67 06 55 12 42 94 18 44 67 06 12 55 42

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Thuật toán sắp xếp
• Đánh giá thuật toán
• Sắp xếp lựa chọn
• 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
• 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ấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Thiết kế cấu trúc dữ liệu
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• 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
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp