Ví dụ về thuật toán sắp xếp bằng tráo đổi
|
1. Xác định bài toán
- Input: Dãy A gồm N số nguyên a1, a2,..., aN.
- Output: Dãy A được sắp xếp lại thành dãy không giảm.
2. Thuật toán
Chắc hẳn ngồi trên ghế giảng đường đại học thì ai cũng sẽ được làm quen với thuật toán. Nghe thì thật là trừu tượng và mơ hồ, nhưng để tối ưu hóa những bài toán đặt ra thì bắt buộc các bạn phải học đến nó. Mình xin chia sẻ 1 chút lí thuyết mà mình học được về các thuật toán sắp xếp đơn giản, mong là có thể giúp các bạn áp dụng vào bài toán thực tế của mình! Sắp xếp nổi bọt ( bubble sort)Đây có lẽ là loại sắp xếp quen thuộc nhất với mọi người. Ý tưởng của thuật toán sắp xếp nổi bọt như sau: cho chỉ số i chạy từ 0, 1, ..., n-1, nếu hai phần tử kề nhau không đúng trật tự, có nghĩa là A[i].key > A[i+1].key thì ta tráo đổi hai phần tử A[i] và A[i+1]. Cứ tiếp tục làm như vậy thì ta sẽ đẩy dữ liệu có khóa lớn nhất lên vị trí sau cùng là A[n-1]. Ví dụGiả sử ta có mảng số nguyên A[0..4] = (7, 2, 8, 4, 6). Kết quả thực hiện việc tráo đổi sẽ được thực hiện trong bảng sau:
Lặp lại quá trình trên với mảng A[0, ..., n-2] để đẩy phần tử lớn nhất lên vị trí A[n-2], khi đó ta có A[n-2].key <= A[n-1].key. Tiếp tục lặp như vậy với các đoạn đầu A[0..i], với i = n-3, ...., 1, ta sẽ thu được mảng được sắp. Thuật toán1void BubbleSort (int A[], int n) { 2 for (int i = n-1; i > 0; i--) { 3 for (int k = 0; k < i; k++) { 4 if (A[k].key > A[k+1].key) { 5 Swap(A[k], A[k+1]); 6 } 7 } 8 } 9}Ta sẽ dễ thấy thời gian chạy của thuật toán này là O(n2) Tuy nhiên giờ ta cũng có thể cải tiến thuật toán sắp xếp nổi bọt bằng cách thêm 1 biến booblean là check, biến này trả về true nếu A[0..i] đã được sắp xếp và ngược lại. Nếu check nhận giá trị true thì vòng for đầu tiên sẽ dừng lại. Mục đích là ở lện lặp đầu tiên, nếu đến chỉ số i nào đó mà đoạn đầu A[0..i] đã được sắp xếp thì ta có thể dừng không lặp nữa, giảm thiểu được thời gian chạy. void BubbleSort (int A[], int n) { for (int i = n-1; i > 0; i--) { bool check = true; for (int k = 0; k < i; k++) { if (A[k].key > A[k+1].key) { Swap(A[k], A[k+1]); check = false; } } if (check) { break; } } }Sắp xếp lựa chọn (selection sort)Ý tưởng của thuật toán này cũng đơn giản không kém sắp xếp nổi bọt: Giả sử ta chọn được thành phần có khóa nhỏ nhất trên mảng là A[k]. Tráo đổi A[0] với A[k], vậy thì lúc này ta sẽ nhận được A[0] là phần tử có khóa nhỏ nhất. Giả sử đến bước thứ i ta đã có A[0].key <= A[1].key <= ... <= A[i-1].key. Bây giờ ta cần tìm thành phần có khóa nhỏ nhất trong các phần tử từ A[i] đến A[n-1]. Giả sử thành phần đó là A[k] sao cho i <= k <= n-1. Ta lại tráo đổi A[i] với A[k], ta có A[0].key <= A[1].key <= ... <= A[i-1].key <= A[i].key. Lặp lại cho tới i = n-1, ta có mảng A được sắp xếp Ví dụTa lại xét mảng A ở ví dụ trên A[0..4] = [7, 2, 8, 4, 6]. Kết quả được thể hiện trong bảng sau: Chọn phần tử có khóa nhỏ nhất là A[0]
Ok vậy là bài toán có thể giải quyết nhanh gọn  Thuật toán1void SelectionSort(int A[], int n) { 2 for (int i = 0; i < n - 1; i++) { 3 int k = i; 4 for (int j = i + 1; j < n; j++) { 5 if (A[j].key < A[k].key) { 6 k = j; 7 Swap(A[i], A[k]); 8 } 9 } 10 } 11}Thời gian chạy của thuật toán này cũng tương tự như thuật toán sắp xếp nổi bọt là O(n2). Sắp xếp xen vào (insertion sort)Đây là thuật toán cuối cùng mà mình sẽ giới thiệu ở bài ngày hôm nay. Ý tưởngCái tên của thuật toán cũng giúp mình hình dung được phần nào ý tưởng của thuật toán. Giả sử đoạn đầu của mảng A[0..i-1] (với i >= 1) đã được sắp xếp, nghĩa là ta đã có A[0].key <= A[1].key <= ... <= A[i-1].key. Ta xen A[i] vào vị trí thích hợp trong đoạn đầu A[0..i-1] để nhận được A[0..i] được sắp xếp. Với i = 1 thì coi như đoạn đã được sắp xếp. Lặp lại quá trình đó với i = 2, ..., n-1 để có được mảng sắp xếp. Việc sắp xếp sẽ được tiến hành như sau: Cho chỉ số k chạy từ i, nếu A[k].key < A[k-1].key thì ta tráo đổi vị trí của A[k] và A[k-1] rồi giảm k đi 1. Ví dụTa có 1 mảng số nguyên A[0..5] = (1, 3, 7, 2, 8, 4) và đoạn đầu A[0..2] = (1, 3, 7) đã được sắp xếp Đầu tiên ta sẽ chọn i = 3 ( vì giá trị từ 0 đến 2 đã được sắp xếp) và k = i = 3. Nhận thấy A[3] < A[2] nên ta tráo đổi A[3] và A[2], ta có:
Đến đây thì ta có k = 2, A[2] < A[1] nên ta lại tráo A[2] cho A[1]:
Lúc này k = 1 và A[1] >= A[0] nên ta dừng lại và ta đã có đoạn đầu A[0..3] được sắp xếp Lặp lại các bước trên với i = 4, 5 ta sẽ được mảng sắp xếp tăng dần Thuật toánHàm sắp xếp xen vào được viết như sau: void InsertionSort(A[], int n) { for (int i = 1; i < n-1; i++) { for (int k = i; k > 0; k--) { if (A[k].key < A[k-].key) { Swap(A[k], A[k-1]); } else { break; } } } }Thuật toán sắp xếp này cũng có thời gian chạy là O(n2) Bài này mình xin phép dừng tại đây. Bài sau mình sẽ giới thiệu thêm 1 số thuật toán sắp xếp ít được sử dụng hơn nhưng lại có thời gian chạy nhanh hơn hẳn 3 thuật toán trên. Hi vọng mọi người đón đọc và cho những lời góp ý! Many thanks! Tham khảo
|
