Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 6: Sắp xếp - Nguyễn Thị Khiêm Hòa

Chương 6: Sắp xếp

Nộ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

pdf78 trang | Chia sẻ: phuongt97 | Lượt xem: 617 | Lượt tải: 0download
Bạn đang xem trước 20 trang nội dung tài liệu Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 6: Sắp xếp - Nguyễn Thị Khiêm Hòa, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Chương 6: Sắp xếp Giảng viên: Ths. Nguyễn Thị Khiêm Hòa Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM Nộ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 2 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 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 4 Sắ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 5 Cá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 7 Phương pháp sắp xếp kiểu lựa chọn (Selection Sort)  Ví dụ: Cho dãy số: i = 7524613 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 8 Phươ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 9 Phươ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 10 Phươ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 11 Phươ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 12 Phươ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 13 Phươ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 14 Phươ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 15 Phươ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 16 Phươ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 17 Phươ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 18 Phươ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 19 Phươ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 20 Phương pháp sắp xếp đổi chỗ (Bubble Sort)  Thuật toán:  Bước 1: i = 1;  Bước 2: j = n;  Trong khi j > i thực hiện: . Nếu Aj < Aj-1 : đổi chổ Aj và Aj-1 . j = j - 1  Bước 3: i = i +1  Nếu i > n-1: Hết dãy -> Dừng  Ngược lại: lặp lại bước 2. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 21 Phương pháp sắp xếp đổi chỗ (Bubble Sort)  Ví dụ:  Cho dãy số: i = 1 j = 37452 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 22 Phương pháp sắp xếp đổi chỗ (Bubble Sort) i = 2 j = 536 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 23 Phương pháp sắp xếp đổi chỗ (Bubble Sort) i = 3 j = 64 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 24 Phương pháp sắp xếp đổi chỗ (Bubble Sort) i = 4 j = 57 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 25 Phương pháp sắp xếp đổi chỗ (Bubble Sort) i = 5 j = 6 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 26 Phương pháp sắp xếp đổi chỗ (Bubble Sort) i = 6 j = 7 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 27 Phương pháp sắp xếp đổi chỗ (Bubble Sort) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 28 Phương pháp sắp xếp đổi chỗ (Bubble Sort) public void Buble_Sort() { for (int i = 0; i < idx - 1; i++) { for(int j = idx - 1; j > i; j--) if(A[j] < A[j-1]) { int tmp = A[j]; A[j] = A[j - 1]; A[j-1] = tmp; } } } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 29 Phương pháp sắp xếp đổi chỗ cải tiến (Shaker_Sort)  Nhận xét:  Phương pháp Buble_Sort không nhận diện được tình trạng đã được sắp xếp của dãy ban đầu => Không hạn chế được phạm vi sắp xếp.  Phần tử nhẹ nổi lên trên nhưng phần tử nặng không chìm xuống. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 30 Phương pháp sắp xếp đổi chỗ cải tiến (Shaker_Sort)  Ý tưởng:  Ghi nhận những đoạn đã sắp xếp bằng cách ghi nhớ vị trí đã xảy ra hoán vị để thu hẹp phạm vi sắp xếp.  Cài đặt  Bài tập cho sinh viên Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 31 So sánh ba phương pháp sắp xếp  Phương pháp sắp xếp chọn  Ở bước thứ i, có (n-i) lần so sánh, với i=1n-1 (n-1) + (n-2) + + 1 = n(n-1)/2 = O(n2)  Thời gian thực hiện giải thuật T(n) ~ O(n2) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 32 So sánh ba phương pháp sắp xếp  Với phương pháp chèn thì số lần so sánh phụ thuộc vào dãy ban đầu. Trường hợp tốt nhất là dãy đã sắp, mỗi lượt chỉ cần 1 lần so sánh nên: n1 Cmin  1  n 1 i1 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 33 So sánh ba phương pháp sắp xếp  Trường hợp xấu nhất là dãy sắp ngược thứ tự, mỗi lượt thứ i cần Ci =(i-1) lần so sánh nên:  Suy ra: n1 n(n 1) Cmax  (i 1)  i1 2 n1 i n2  n  2 Ctb    i1 2 4 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 34 So sánh ba phương pháp sắp xếp  Phương pháp sắp xếp nổi bọt:  Ở bước thứ i, có n-i phép so sánh  Thời gian thực hiện giải thuật T(n) ~ O(n2) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 35 So sánh ba phương pháp sắp xếp  Theo kết quả đánh giá thì phương pháp chèn tỏ ra hiệu quả hơn hai phương pháp kia. Tuy nhiên với n khá lớn thì chi phí về thời gian thực hiện cả ba phương pháp đều có chi phí về thời gian tương đương: T(n) = O(n2) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 36 Phương pháp sắp xếp dựa trên phân hoạch (Quick_Sort)  Ý tưởng:  Chọn một phần tử trong dãy làm khoá  Đưa các phần tử nhỏ hơn khoá về bên trái của khoá, các phần tử lớn hơn đưa về bên phải của khoá.  Tiếp tục thực hiện phân hoạch với các dãy con cho đến khi dãy được sắp xếp Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 37 Phương pháp sắp xếp dựa trên phân hoạch (Quick_Sort)  Thuật toán:  Bước 1: Chọn phần tử giữa có khoá x làm mốc để phân hoạch  Bước 2: Đi từ hai đầu của dãy, phát hiện cặp A[i]>x và A[j]<x, đổi chỗ (A[i],A[j]). Tiếp tục cho đến khi i≥j. Ta có 2 dãy con.  Bước 3: Thực hiện bước 1 và 2 cho từng dãy con nếu số phần tử của dãy con lớn hơn 1. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 38 Phương pháp sắp xếp dựa trên phân hoạch (Quick_Sort)  Ví dụ:  Cho dãy số: Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 39 Phương pháp sắp xếp dựa trên phân hoạch (Quick_Sort) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 40 Phương pháp sắp xếp dựa trên phân hoạch (Quick_Sort) private void QuickSort(int left, int right) { int x = A[(left + right) / 2]; int i = left; int j = right; do { while (A[i] < x) i++; while (A[j] > x) j--; if (i <= j) { Hoan_vi(A[i],A[j]); i++; j--; } } while (i <= j); if (i < right) QuickSort(i, right); if (j > left) QuickSort(left, j); } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 41 Phương pháp sắp xếp dựa trên phân hoạch (Quick_Sort)  Nhận xét:  Khi chọn khoá nhầm phần tử nhỏ nhất (hoặc lớn nhất) sẽ dẫn đến trường hợp xấu nhất của phương pháp.  Khi số lượng phần tử thấp nên chọn phương pháp sắp xếp đơn giản. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 42 Phương pháp sắp xếp dựa trên phân hoạch (Quick_Sort)  Đánh giá:  Gọi T(n) là thời gian thực hiện thuật toán với dãy n phần tử. P(n) là thời gian để phân đoạn dãy n khoá thành 2 dãy con T(n) = P(n) + T(l..j) + T(i..r)  Trường hợp tốt nhất: mỗi bước phân thành 2 đoạn có chiều dài bằng nhau: T(n) = P(n) + 2T(n/2) ~ O(nlog2n) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 43 Phương pháp sắp xếp dựa trên phân hoạch (Quick_Sort)  Đánh giá:  Trường hợp xấu nhất: mỗi bước phân mảng r phần tử thành 2 đoạn có chiều dài bằng 1 và r-1: T(n) = P(n) + T(n-1) + T(1) ~ O(n2) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 44 Phương pháp sắp xếp trên Heap (Heap_Sort)  Đặt vấn đề:  Quick_Sort: Trong trường hợp xấu nhất tốn chi phí O(n2)  SelectionSort: Không tận dụng được thông tin của bước trước đó khi tìm phần tử nhỏ nhất Phương pháp Heap_Sort Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 45 Phương pháp sắp xếp trên Heap (Heap_Sort)  Định nghĩa:  Cây nhị phân Heap: Là cây nhị phân có khoá của nút cha lớn hơn hoặc bằngkhoá hai nút con Nút gốc có giá trị lớn nhất Nút lá là một Heap Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 46 Phương pháp sắp xếp trên Heap (Heap_Sort)  Định nghĩa:  Dãy A, n phần tử được gọi là Heap nếu: Ai ≥ A2i và Ai ≥ A2i+1  (Ai, A2i), (Ai, A2i+1) là các cặp phần tử liên đới  Phần tử đầu dãy là phần tử lớn nhất  Mọi dãy an/2+1, , an là một Heap  Nếu dãy A là một Heap thì khi cắt bỏ một số phần tử ở hai đầu dãy thì dãy còn lại vẫn là một Heap Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 47 Phương pháp sắp xếp trên Heap (Heap_Sort)  Thuật toán:  Bước 1: Hiệu chỉnh dãy A0 .. An-1 thành một Heap  Bước 2: Hoán vị A0 và An-1  Bước 3: Lặp lại bước 1 và 2 với n giảm dần cho đến khi n=1 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 48 Phương pháp sắp xếp trên Heap (Heap_Sort)  Ví dụ:Cho dãy số 12, 2, 8, 5, 1, 6, 4, 15, 9, 7 1 2 2 8 5 1 6 4 1 9 7 5 12 2 8 5 1 6 4 15 9 7 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 49 Phương pháp sắp xếp trên Heap (Heap_Sort) 1 2 2 8 5 1 6 4 1 9 7 12 2 8 5 1 6 4 15 9 7 5 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 50 Phương pháp sắp xếp trên Heap (Heap_Sort) 1 2 2 8 5 7 6 4 1 9 1 12 2 8 5 7 6 4 15 9 1 5 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 51 Phương pháp sắp xếp trên Heap (Heap_Sort) 1 2 2 8 1 7 6 4 5 5 9 1 12 2 8 15 7 6 4 5 9 1 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 52 Phương pháp sắp xếp trên Heap (Heap_Sort) 1 2 1 8 5 2 7 6 4 5 9 1 12 15 8 2 7 6 4 5 9 1 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 53 Phương pháp sắp xếp trên Heap (Heap_Sort) 1 2 1 8 5 9 7 6 4 5 2 1 12 15 8 9 7 6 4 5 2 1 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 54 Phương pháp sắp xếp trên Heap (Heap_Sort) 1 5 1 8 2 9 7 6 4 5 2 1 15 12 8 9 7 6 4 5 2 1 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 55 Phương pháp sắp xếp trên Heap (Heap_Sort) 1 1 8 2 9 7 6 4 5 2 1 5 1 12 8 9 7 6 4 5 2 15 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 56 Phương pháp sắp xếp trên Heap (Heap_Sort) 1 2 9 8 5 7 6 4 1 2 1 5 12 9 8 5 7 6 4 1 2 15 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 57 Phương pháp sắp xếp trên Heap (Heap_Sort) 2 9 8 5 7 6 4 1 1 1 2 5 2 9 8 5 7 6 4 1 12 15 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 58 Phương pháp sắp xếp trên Heap (Heap_Sort) 9 7 8 5 2 6 4 1 1 1 2 5 9 7 8 5 2 6 4 1 12 15 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 59 Phương pháp sắp xếp trên Heap (Heap_Sort) 1 7 8 5 2 6 4 9 1 1 2 5 1 7 8 5 2 6 4 9 12 15 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 60 Phương pháp sắp xếp trên Heap (Heap_Sort) 8 7 6 5 2 1 4 9 1 1 2 5 8 7 6 5 2 1 4 9 12 15 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 61 Phương pháp sắp xếp trên Heap (Heap_Sort) 4 7 6 5 2 1 8 9 1 1 2 5 4 7 6 5 2 1 8 9 12 15 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 62 Phương pháp sắp xếp trên Heap (Heap_Sort) 7 5 6 4 2 1 8 9 1 1 2 5 7 5 6 4 2 1 8 9 12 15 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 63 Phương pháp sắp xếp trên Heap (Heap_Sort) 1 5 6 4 2 7 8 9 1 1 2 5 1 5 6 4 2 7 8 9 12 15 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 64 Phương pháp sắp xếp trên Heap (Heap_Sort) 6 5 1 4 2 7 8 9 1 1 2 5 6 5 1 4 2 7 8 9 12 15 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 65 Phương pháp sắp xếp trên Heap (Heap_Sort) 2 5 1 4 6 7 8 9 1 1 2 5 2 5 1 4 6 7 8 9 12 15 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 66 Phương pháp sắp xếp trên Heap (Heap_Sort) 5 4 1 2 6 7 8 9 1 1 2 5 5 4 1 2 6 7 8 9 12 15 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 67 Phương pháp sắp xếp trên Heap (Heap_Sort) 2 4 1 5 6 7 8 9 1 1 2 5 2 4 1 5 6 7 8 9 12 15 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 68 Phương pháp sắp xếp trên Heap (Heap_Sort) 4 2 1 5 6 7 8 9 1 1 2 5 4 2 1 5 6 7 8 9 12 15 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 69 Phương pháp sắp xếp trên Heap (Heap_Sort) 1 2 4 5 6 7 8 9 1 1 2 5 1 2 4 5 6 7 8 9 12 15 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 70 Phương pháp sắp xếp trên Heap (Heap_Sort) 1 2 4 5 6 7 8 9 1 1 2 5 1 2 4 5 6 7 8 9 12 15 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 71 Phương pháp sắp xếp trên Heap (Heap_Sort) 1 2 4 5 6 7 8 9 1 1 2 5 1 2 4 5 6 7 8 9 12 15 1 2 3 4 5 6 7 8 9 10 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 72 Phương pháp sắp xếp trên Heap (Heap_Sort) public void Heap_Sort() { int right = idx - 1; Create_Heap(); while (right > 0) { int tmp = A[0]; A[0] = A[right]; A[right] = tmp; right--; Shift(0, right); } } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 73 Phương pháp sắp xếp trên Heap (Heap_Sort) private void Create_Heap() { int left =(idx-1)/2; while (left >= 0) { Shift(left, idx - 1); left--; } } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 74 Phương pháp sắp xếp trên Heap (Heap_Sort) private void Shift(int left, int right) { int i = left; int j = 2 * i + 1; int x = A[i]; while (j <= right) { if (j < right) if (A[j] < A[j + 1]) j++; if (A[j] < x) break; A[i] = A[j]; i = j; j = 2 * i + 1; } A[i] = x; } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 75 Phương pháp sắp xếp trên Heap (Heap_Sort)  Đánh giá: Việc đánh giá giải thuật HeapSort rất phức tạp nhưng đã chứng minh được độ phức tạp trong trường hợp xấu nhất: T(n) = O(nlog2n) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 76 Bài tập Thực hiện Cài đặt các thuật toán sắp xếp cho mảng số nguyên 20000 phần tử được đọc từ file. Đo thời gian thực hiện của từng thuật toán. Vẽ biểu đồ so sánh kết quả nhận được. 90 min Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 77 Q&A Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 78

Các file đính kèm theo tài liệu này:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_6_sap_xep_ng.pdf