Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 6 - ThS. Nguyễn Thị Khiêm Hòa (ĐH Ngân hàng TP.HCM)

Chương 6 Sắp xếp nằm trong bài giảng cấu trúc dữ liệu và giải thuật nhằm trình bày về các nội dung chính: các phương pháp sắp xếp cơ bản, đánh giá các phương pháp, Quick - Sort và Heap_Sort, 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).

Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 6 - ThS. Nguyễn Thị Khiêm Hòa (ĐH Ngân hàng TP.HCM)Chương 6: Sắp xếp Giảng viên: Ths. Nguyễn Thị Khiêm HòaKhoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCMNội dung  Các phương pháp sắp xếp cơ bản  Đánh giá các phương pháp  Quick_Sort  Heap_Sort Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 2Mụ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 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 3Đặt vấn đề Trong công việc hàng ngày cũng như các bài toán quản lý kinh tế cần tìm kiếm dữ liệu  Dễ dàng  Nhanh chóng Ví dụ: danh sách sinh viên, từ điển … Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 4Sắp xếp (Sorting) Định nghĩa  Sắp xếp là quá trình tổ chức lại một tập hợp k đối tượng theo một trật tự nào đó 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 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 5Các phương pháp sắp xếp cơ bản Phương pháp sắp xếp kiểu lựa chọn Phương pháp sắp xếp chèn Phương pháp sắp xếp đổi chỗ Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 6 Phương pháp sắp xếp kiểu lựa chọn (Selection Sort) Ý tưởng:  Tìm phần tử nhỏ nhất đem về đầu dãy  Loại phần tử này ra khỏi dãy  Tiếp tục tìm phần tử nhỏ nhất của dãy còn lại. Thuật toán:  Ở bước thứ i ta chọn trong Ai, Ai+1, …, An phần tử có khóa nhỏ nhất và đổi chỗ với Ai.  Sau n lượt ta có dãy A được sắp thứ tự Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 7Phương pháp sắp xếp kiểu lựa chọn(Selection Sort) Ví dụ: Cho dãy số: i=7 6 4 2 3 1 5 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 8Phương pháp sắp xếp kiểu lựa chọn(Selection Sort)public void SelectionSort(){ int min,vt; for (int i = 0; i < idx-1; i++) { min = A[i]; vt = i; for (int j = i + 1; j < idx; j++) { if (A[j] < min) { min = A[j]; vt = j; } } if (vt != i) { A[vt] = A[i]; A[i] = min; } }} Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 9Phương pháp sắp xếp chèn (Insertion Sort) Thuật toán:  Dãy ban đầu A1,A2,…,An xem như đã có đoạn gồm 1 phần tử A1 đã được sắp.  Thêm A2 vào A1 sẽ có đoạn A1A2 đã được sắp.  Thêm A3 vào A1A2 sẽ có đoạn A1A2 A3 đã được sắp.  Tiếp tục cho đến khi thêm xong An vào đoạn A1,A2,…,An-1 sẽ có dãy A1,A2,…,An đã được sắp xếp. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 10Phương pháp sắp xếp chèn (Insertion Sort) Ví dụ:  Cho dãy số: i=2 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 11Phương pháp sắp xếp chèn (Insertion Sort) i=3 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 12Phương pháp sắp xếp chèn (Insertion Sort) i=4 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 13Phương pháp sắp xếp chèn (Insertion Sort) i=5 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 14Phương pháp sắp xếp chèn (Insertion Sort) i=6 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 15Phương pháp sắp xếp chèn (Insertion Sort) i=7 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 16Phương pháp sắp xếp chèn (Insertion Sort) i=8 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 17Phương pháp sắp xếp chèn (Insertion Sort) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 18Phương pháp sắp xếp chèn (Insertion Sort)public void Insertion_Sort(){ for (int i = 1; i < idx; i++) { int x = A[i]; int j = i - 1; while ((j >= 0)&&(A[j] > x)) { A[j + 1] = A[j]; j--; } A[j + 1] = x; }} Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 19Phương pháp sắp xếp đổi chỗ (Bubble Sort) Ý tưởng:  Xét từ cuối dãy ngược về vị trí i  Nếu hai phần tử kế cận ngược thứ tự thì đổi chỗ cho nhau  Thực hiện đến khi không còn phần tử để xét. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM ...