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! KHMT - ĐHBKHN
NỘI DUNG 5.1. Bài toán sắp xếp 5.2. Ba thuật toán sắp xếp cơ bản 5.3. Sắp xếp trộn (Merge Sort) 5.4. Sắp xếp nhanh (Quick Sort) 5.5. Sắp xếp vun đống (Heap Sort) KHMT - ĐHBKHN 3
5.1. Bài toán sắp xếp • 5.1.1. Bài toán sắp xếp • 5.1.2. Giới thiệu sơ lược về các thuật toán sắp xếp KHMT - ĐHBKHN 4
5.1.1. 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á. KHMT - ĐHBKHN 5
5.1.1. 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. KHMT - ĐHBKHN 6
5.1.1. Bài toán sắp xếp Ta có thể hạn chế xét bài toán sắp xếp dưới dạng sau đây: Input: Dãy n số A = (a1, a2, …, an) Output: Một hoán vị (sắp xếp lại) (a'1,…, a’n) của dãy số đã cho thoả mãn a’1 ≤ … ≤ a’n • Ứng dụng của sắp xếp: – Quản trị cơ sở dữ liệu (Database management); – Khoa học và kỹ thuật (Science and engineering); – Các thuật toán lập lịch (Scheduling algorithms), • ví dụ thiết kế chương trình dịch, truyền thông,... (compiler design, telecommunication); – Máy tìm kiếm web (Web search engine); – và nhiều ứng dụng khác… KHMT - ĐHBKHN 7
5.1.1. Bài toán sắp xếp • Các loại thuật toán sắp xếp – Sắp xếp trong (internal sort) • Đòi hỏi họ dữ liệu được đưa toàn bộ vào bộ nhớ trong của máy tính – Sắp xếp ngoài (external sort) • Họ dữ liệu không thể cùng lúc đưa toàn bộ vào bộ nhớ trong, nhưng có thể đọc vào từng bộ phận từ bộ nhớ ngoài • Các đặc trưng của một thuật toán sắp xếp: – Tại chỗ (in place): nếu không gian nhớ phụ mà thuật toán đòi hỏi là O(1), nghĩa là bị chặn bởi hằng số không phụ thuộc vào độ dài của dãy cần sắp xếp. – Ổn định (stable): Nếu các phần tử có cùng giá trị vẫn giữ nguyên thứ tự tương đối của chúng như trước khi sắp xếp. KHMT - ĐHBKHN 8
5.1.1. Bài toán sắp xếp • Có hai phép toán cơ bản mà thuật toán sắp xếp thường phải sử dụng: – Đổi chỗ (Swap): Thời gian thực hiện là O(1) void swap( datatype &a, datatype &b){ datatype temp = a; //datatype-kiểu dữ liệu của phần tử a = b; b = temp; } – So sánh: Compare(a, b) trả lại true nếu a đi trước b trong thứ tự cần sắp xếp và false nếu trái lại. • Các thuật toán chỉ sử dụng phép toán so sánh để xác định thứ tự giữa hai phần tử được gọi là thuật toán sử dụng phép so sánh (Comparison-based sorting algorithm) KHMT - ĐHBKHN 9
NỘI DUNG 5.1. Bài toán sắp xếp 5.2. Ba thuật toán sắp xếp cơ bản 5.3. Sắp xếp trộn (Merge Sort) 5.4. Sắp xếp nhanh (Quick Sort) 5.5. Sắp xếp vun đống (Heap Sort) KHMT - ĐHBKHN 10
5.2. Ba thuật toán sắp xếp cơ bản • 5.2.1. Sắp xếp chèn (Insertion Sort) • 5.2.2. Sắp xếp lựa chọn (Selection Sort) • 5.2.3. Sắp xếp nổi bọt (Bubble Sort) KHMT - ĐHBKHN 11
5.2.1. Sắp xếp chèn (Insertion Sort) Phỏng theo cách làm của người chơi bài khi cần "chèn" thêm một con bài vào bộ bài đã được sắp xếp trên tay. Để chèn 12, ta cần tạo chỗ cho nó bởi việc dịch chuyển đầu tiên là 36 và sau đó là 24. KHMT - ĐHBKHN 12
Sắp xếp chèn (Insertion Sort) Phỏng theo cách làm của người chơi bài khi cần "chèn" thêm một con bài vào bộ bài đã được sắp xếp trên tay. Để chèn 12, ta cần tạo chỗ cho nó bởi việc dịch chuyển đầu tiên là 36 và sau đó là 24. 13 KHMT - ĐHBKHN
Sắp xếp chèn (Insertion Sort) Phỏng theo cách làm của người chơi bài khi cần "chèn" thêm một con bài vào bộ bài đã được sắp xếp trên tay. Để chèn 12, ta cần tạo chỗ cho nó bởi việc dịch chuyển đầu tiên là 36 và sau đó là 24. 14 KHMT - ĐHBKHN
Sắp xếp chèn (Insertion Sort) Phỏng theo cách làm của người chơi bài khi cần "chèn" thêm một con bài vào bộ bài đã được sắp xếp trên tay. Để chèn 12, ta cần tạo chỗ cho nó bởi việc dịch chuyển đầu tiên là 36 và sau đó là 24. 15 KHMT - ĐHBKHN
5.2.1. Sắp xếp chèn (Insertion Sort) • Thuật toán: – Tại bước k = 1, 2, ..., n, đưa phần tử thứ k trong mảng đã cho vào đúng vị trí trong dãy gồm k phần tử đầu tiên. – Kết quả là sau bước k, k phần tử đầu tiên là được sắp thứ tự. void insertionSort(int a[], int array_size) { int i, j, last; for (i=1; i < array_size; i++) { Giải thích: • Ở đầu lần lặp i của vòng last = a[i]; "for" ngoài, dữ liệu từ a[0] j = i; đến a[i-1] là được sắp xếp. while ((j > 0) && (a[j-1] > last)) { • Vòng lặp "while" tìm vị trí a[j] = a[j-1]; cho phần tử tiếp theo (last j = j - 1; } =a[i]) trong dãy gồm i phần a[j] = last; tử đầu tiên. } // end for } // end of isort KHMT - ĐHBKHN 17
Ví dụ Insertion sort (1) 1 2 3 8 7 9 10 12 23 18 15 16 17 14 1 2 3 7 8 9 10 12 23 18 15 16 17 14 1 2 3 7 8 9 10 12 18 23 15 16 17 14 1 2 3 7 8 9 10 12 18 15 23 16 17 14 1 2 3 7 8 9 10 12 15 18 23 16 17 14 1 2 3 7 8 9 10 12 15 18 16 23 17 14 1 2 3 7 8 9 10 12 15 16 18 23 17 14 KHMT - ĐHBKHN 18
Ví dụ Insertion sort (1) 1 2 3 7 8 9 10 12 15 16 18 17 23 14 1 2 3 7 8 9 10 12 15 16 17 18 23 14 1 2 3 7 8 9 10 12 15 16 17 18 14 23 1 2 3 7 8 9 10 12 15 16 17 14 18 23 1 2 3 7 8 9 10 12 15 16 14 17 18 23 1 2 3 7 8 9 10 12 15 14 16 17 18 23 1 2 3 7 8 9 10 12 14 15 16 17 18 23 13 phép đổi chỗ: 20 phép so sánh: KHMT - ĐHBKHN 19
Hiển thị 19 trang đầu. Tải tài liệu để xem đầy đủ.
Chưa có bình luận nào. Hãy là người đầu tiên!
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!