Chapter 17: SẮP XẾP

Sắp xếp là một quá trình biến đổi một danh sách các đối tượngthành một danh sách thoả mãn một thứ tự xác định nào đó. Sắp xếp đóngvai trò quan trọng trong tìm kiếm dữ liệu. Chẳng hạn, nếu danh sách đãđược sắp xếp theo thứ tự tăng dần (hoặc giảm dần), ta có thể sử dụng kỹthuật tìm kiếm nhị phân hiệu quả hơn nhiều tìm kiếm tuần tự…
Nội dung trích xuất từ tài liệu:
Chapter 17: SẮP XẾP CHƯƠNG 17 SẮP XẾP Sắp xếp là một quá trình biến đổi một danh sách các đối tượngthành một danh sách thoả mãn một thứ tự xác định nào đó. Sắp xếp đóngvai trò quan trọng trong tìm kiếm dữ liệu. Chẳng hạn, nếu danh sách đãđược sắp xếp theo thứ tự tăng dần (hoặc giảm dần), ta có thể sử dụng kỹthuật tìm kiếm nhị phân hiệu quả hơn nhiều tìm kiếm tuần tự… Trongthiết kế thuật toán, ta cũng thường xuyên cần đến sắp xếp, nhiều thuậttoán được thiết kế dựa trên ý tưởng xử lý các đối tượng theo một thứ tựxác định. Các thuật toán sắp xếp được chia làm 2 loại: sắp xếp trong và sắpxếp ngoài. Sắp xếp trong được thực hiện khi mà các đối tượng cần sắpxếp được lưu ở bộ nhớ trong của máy tính dưới dạng mảng. Do đó sắpxếp trong còn được gọi là sắp xếp mảng. Khi các đối tượng cần sắp xếpquá lớn cần lưu ở bộ nhớ ngoài dưới dạng file, ta cần sử dụng cácphương pháp sắp xếp ngoài, hay còn gọi là sắp xếp file. Trong chươngnày, chúng ta trình bày các thuật toán sắp xếp đơn giản, các thuật toán nàydòi hỏi thời gian O(n2) để sắp xếp mảng n đối tượng. Sau đó chúng ta đưara các thuật toán phức tạp và tinh vi hơn, nhưng hiệu quả hơn, chỉ cầnthời gian O(nlogn). Mảng cần được sắp xếp có thể là mảng số nguyên, mảng các sốthực, hoặc mảng các xâu ký tự. Trong trường hợp tổng quát, các đốitượng cần được sắp xếp chứa một số thành phần dữ liệu, và ta cần sắpxếp mảng các đối tượng đó theo một thành phần dữ liệu nào đó. Thànhphần dữ liệu đó được gọi là khoá sắp xếp. Chẳng hạn, ta có một mảngcác đối tượng sinh viên, mỗi sinh viên gồm các thành phần dữ liệu: tên,tuổi, chiều cao,…, và ta muốn sắp xếp các sinh viên theo thứ tự chiều caotăng, khi đó chiều cao là khoá sắp xếp. 187 Từ đây về sau, ta giả thiết rằng, mảng cần được sắp xếp là mảngcác đối tượng có kiểu Item, trong đó Item là cấu trúc sau: struct Item { keyType key; // Khoá sắp xếp // Các trường dữ liệu khác }; Vấn đề sắp xếp bây giờ được phát biểu chính xác như sau. Chomảng A[0..n-1] chứa n Item, chúng ta cần sắp xếp lại các thành phần củamảng A sao cho: A[0].key A[0] A[1] A[2] A[3] A[4] A[5] I k5 9 1 8 3 7 0 21 9 5 8 3 7 1 41 3 5 8 9 7 2 21 3 5 8 9 7 3 51 3 5 7 9 8 4 51 3 5 7 8 9Sau đây là hàm sắp xếp lựa chọn: void SelectionSort(Item A[] , int n) // Sắp xếp mảng A[0..n-1] với n > 0 { (1) for (int i = 0 ; i < n-1 ; i++) { (2) int k = i; (3) for (int j = i + 1 ; j < n ; j++) (4) if (A[j].key < A[k].key) k = j; (5) swap(A[i],A[k]); } }Trong hàm trên, swap là hàm thực hiện trao đổi giá trị của hai biến. Phân tích sắp xếp lựa chọn. Thân của lệnh lặp (1) là các lệnh (2), (3) và (5). Các lệnh (2) và (5)có thời gian chạy là O(1). Ta đánh giá thời gian chạy của lệnh lặp (3). Sốlần lặp là (n-1-i), thời gian thực hiện lệnh (4) là O(1), do đó thời gianchạy của lệnh (3) là (n-1-i)O(1). Như vậy, thân của lệnh lặp (1) có thờigian chạy ở lần lặp thứ i là (n-1-i)O(1). Do đó lệnh lặp (1) đòi hỏi thờigian n −2 ∑ i =0 (n-1-i)O(1) = O(1)(1 + 2 + …+ n-1) = O(1)n(n-1)/2 = O(n2) 189Vậy thời gian chạy của hàm sắp xếp lựa chọn là O(n2).17.1.2 Sắp xếp xen vào Phương pháp sắp xếp xen vào là như sau. Giả sử đoạn đầu củamảng A[0..i-1] (với i >= 1) đã được sắp xếp, tức là ta đã có A[0].key { (1) for ( int i = 1 ; i < n ; i++) (2) for ( int k = i ; k > 0 ; k--) (3) if (A[k].key < A[k-1].key) swap(A[k],A[k-1]); else break; } Phân tích sắp xếp xen vàoSố lần lặp tối đa của lệnh lặp (2) là i, thân của lệnh lặp (2) là lệnh (3)cần thời gian O(1). Do đó thời gian chạy của lệnh (2) là O(1)i. Thời gianthực hiện lệnh lặp (1) là n −1 ∑ O(1) i = O(1)(1 + 2 + ... + n − 1) = O(n i =1 2 )17.1.3 Sắp xếp nổi bọt Ý tưởng của sắp xếp nổi bọt là như sau. Cho chỉ số k chạy từ 0, 1 ,…, n-1, nếu hai ...