tailieunhanh - 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 | 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 .