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
a] Cách liệt kê
Bước 1. Nhập N, các số hạng a1, a2,…, aN;
Bước 2. M := N;
Bước 3. Nếu M < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;
Bước 4. M := M – 1, i := 0;
Bước 5. i := i + 1;
Bước 6. Nếu i > M thì quay lại bước 3;
Bước 7. Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;
Bước 8. Quay lại bước 5.
- Một số thuật toán sắp xếp đơn giản [phần 2]
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:
| 7 | 2 | 8 | 4 | 6 | Vì 7 > 2, tráo đổi A[0] với A[1] |
| 2 | 7 | 8 | 4 | 6 | Vì 8 > 4, tráo đổi A[2] với A[3] |
| 2 | 7 | 4 | 8 | 6 | Vì 8 > 6, tráo đổi A[3] với A[4] |
| 2 | 7 | 4 | 6 | 8 |
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 0; i--] { 3 for [int k = 0; k 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 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