Sắp xếp cơ bản
- Độ khó
- ★★☆☆☆ Dễ
- Thời lượng
- Khoảng 90 phút
- Học trước
- Mảng 1 chiều, Vector
- Chủ đề
- sắp xếpvòng lặp
- Trạng thái
Kiến thức cơ bản
Vì sao cần sắp xếp
Cô giáo xếp hàng theo chiều cao, thư viện xếp sách theo thứ tự, bảng xếp hạng được xếp theo điểm. Khi dữ liệu đã ngăn nắp, nhiều việc trở nên rất dễ: số nhỏ nhất ở đầu, số lớn nhất ở cuối, các số bằng nhau đứng cạnh nhau, hai số gần nhau nhất cũng đứng cạnh nhau.
Tuần này em sẽ tự viết các cách sắp xếp để hiểu máy tính "suy nghĩ" như thế nào. Tuần sau, em sẽ học hàm sort() có sẵn của C++ để sắp xếp nhanh hơn rất nhiều.
Đổi chỗ hai phần tử
Muốn đổi nước cam ở ly A với nước chanh ở ly B, em cần một ly trống thứ ba. Máy tính cũng vậy: muốn đổi giá trị của hai biến a và b, ta cần một biến tạm tmp. Ở tuần 7 em đã viết hàm swapVal; C++ có sẵn hàm swap(a, b) làm đúng việc đó.
// Cách 1: tự đổi bằng biến tạm (giống swapVal ở tuần 7)
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
// Cách 2: dùng hàm có sẵn, gọn hơn
swap(a[i], a[j]);
Sắp xếp chọn (Selection Sort)
Câu chuyện: Thỏ muốn xếp 5 bạn thành hàng từ thấp đến cao. Lượt 1, Thỏ nhìn cả hàng, chọn bạn thấp nhất và mời bạn ấy đứng vào vị trí đầu tiên (đổi chỗ với bạn đang đứng đầu). Lượt 2, Thỏ bỏ bạn đầu hàng ra (đã đúng chỗ), chọn bạn thấp nhất trong số còn lại và mời đứng vào vị trí thứ hai. Cứ lặp lại như thế. Hàng n bạn chỉ cần n - 1 lượt.
Mảng ban đầu: 64 25 12 22 11
Lượt 1: nhỏ nhất là 11 (vị trí 4) → đổi chỗ với vị trí 0
[11] | 25 12 22 64 ([...]: phần đã xếp xong)
Lượt 2: đoạn còn lại, nhỏ nhất là 12 (vt 2) → đổi với vt 1
[11 12] | 25 22 64
Lượt 3: nhỏ nhất là 22 (vt 3) → đổi với vt 2
[11 12 22] | 25 64
Lượt 4: nhỏ nhất là 25 (đã đúng chỗ), không cần đổi
[11 12 22 25] 64 → xong
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void selectionSort(vector<int> &a) {
int n = a.size();
for (int i = 0; i < n - 1; ++i) { // lượt i
int minIdx = i; // giả sử a[i] nhỏ nhất
for (int j = i + 1; j < n; ++j)
if (a[j] < a[minIdx]) minIdx = j; // ghi nhớ vị trí
swap(a[i], a[minIdx]); // đưa về đầu đoạn
}
}
int main() {
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
selectionSort(a);
for (int x : a) cout << x << " ";
return 0;
}
Độ phức tạp
Lượt 1 so sánh n - 1 lần, lượt 2 so sánh n - 2 lần, ..., lượt cuối so sánh 1 lần. Tổng cộng (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2 phép so sánh, tức khoảng n2/2. Vậy độ phức tạp là O(n2), dù dãy ban đầu có sẵn thứ tự hay không. Với n = 1000 chỉ khoảng 500 000 phép so sánh, máy tính xong trong một cái chớp mắt; nhưng với n = 105 là khoảng 5.109 phép, quá chậm so với quy ước 108.
Sắp xếp nổi bọt (Bubble Sort)
Câu chuyện: trong ly nước ngọt, bong bóng to nổi lên mặt nước trước. Gấu Po đi từ đầu hàng đến cuối hàng, mỗi lần nhìn hai bạn đứng cạnh nhau: nếu bạn bên trái cao hơn bạn bên phải thì hai bạn đổi chỗ. Sau lượt đầu, bạn cao nhất đã "nổi" về cuối hàng. Lượt sau chỉ cần xét phần còn lại, bạn cao nhì sẽ nổi lên vị trí kế cuối, và cứ thế tiếp tục.
Mảng ban đầu: 5 1 4 2
Lượt 1: (5,1) đổi → 1 5 4 2
(5,4) đổi → 1 4 5 2
(5,2) đổi → 1 4 2 [5]
Lượt 2: (1,4) giữ nguyên; (4,2) đổi → 1 2 [4 5]
Lượt 3: (1,2) giữ nguyên, không đổi lần nào → dừng sớm
Kết quả: 1 2 4 5
void bubbleSort(vector<int> &a) {
int n = a.size();
for (int i = 0; i < n - 1; ++i) { // lượt i
bool swapped = false; // lượt này có đổi không?
for (int j = 0; j < n - 1 - i; ++j) // i số cuối đã đúng chỗ
if (a[j] > a[j + 1]) { // hai bạn cạnh nhau sai thứ tự
swap(a[j], a[j + 1]);
swapped = true;
}
if (!swapped) break; // không đổi: đã xếp xong
}
}
Độ phức tạp
Trường hợp xấu nhất (dãy giảm dần), mọi cặp đều phải đổi chỗ, tổng khoảng n(n - 1)/2 lần, tức O(n2). Nếu dãy đã xếp sẵn, lượt đầu không đổi chỗ lần nào và lệnh break dừng ngay, chỉ tốn khoảng n phép so sánh, tức O(n). Vì vậy lệnh dừng sớm rất đáng giá.
Sắp xếp chèn (không bắt buộc)
Câu chuyện: khi chơi bài, em cầm các lá đã xếp gọn trên tay, rút một lá mới rồi chèn vào đúng chỗ giữa các lá đã xếp: lá nào lớn hơn lá mới thì dịch sang phải một nấc để nhường chỗ.
Mảng ban đầu: 3 1 2
i=1: lá mới 1; dịch 3 sang phải, chèn 1 vào đầu → [1 3] 2
i=2: lá mới 2; dịch 3 sang phải, 1 không lớn hơn 2 → [1 2 3]
void insertionSort(vector<int> &a) {
int n = a.size();
for (int i = 1; i < n; ++i) {
int key = a[i]; // lá bài mới
int j = i - 1;
while (j >= 0 && a[j] > key) { // lá lớn hơn thì dịch phải
a[j + 1] = a[j];
--j;
}
a[j + 1] = key; // chèn key vào chỗ trống
}
}
Sắp xếp chèn cũng là O(n2) khi dãy lộn xộn, nhưng chỉ khoảng O(n) khi dãy gần như đã xếp sẵn.
Sắp xếp giảm dần
Muốn sắp xếp giảm dần, chỉ cần đổi chiều phép so sánh: ở sắp xếp chọn, tìm số lớn nhất (đổi a[j] < a[minIdx] thành a[j] > a[maxIdx]); ở sắp xếp nổi bọt, đổi a[j] > a[j + 1] thành a[j] < a[j + 1].
Các tính chất cần nhớ
- Cả ba cách đều là O(n2) ở trường hợp xấu nhất, nên chỉ nên dùng khi n không quá khoảng 5000 (khi đó khoảng 12,5 triệu phép so sánh). Với n lớn hơn (như 105) cần cách nhanh hơn, tuần sau em sẽ học sort() chạy cỡ n.log(n).
- Sắp xếp chọn thực hiện ít lần đổi chỗ nhất (không quá n - 1 lần).
- Số lần đổi chỗ của sắp xếp nổi bọt bằng số cặp (i < j) mà a[i] > a[j], tức số cặp đứng sai thứ tự.
- Sắp xếp nổi bọt và sắp xếp chèn dùng phép so sánh chặt (> hoặc <), nên hai phần tử bằng nhau không bao giờ đổi chỗ cho nhau; thứ tự ban đầu của chúng được giữ nguyên.
- Hai lỗi hay gặp: viết sai biên vòng lặp (chọn: i chạy đến n - 2, j từ i + 1; nổi bọt: j chạy đến n - 2 - i), hoặc quên đổi chỗ bằng swap mà gán trực tiếp làm mất giá trị.
Một số hàm hữu ích
| swap(a, b) | Đổi chỗ giá trị của hai biến (hoặc hai phần tử như swap(a[i], a[j])) |
|---|---|
| min(a, b) | Trả về số nhỏ hơn trong hai số a, b |
| max(a, b) | Trả về số lớn hơn trong hai số a, b |
| v.size() | Số phần tử của vector v (kiểu unsigned, nên dùng int(v.size()) hoặc gán vào biến int n) |
So sánh ba cách sắp xếp
| Cách sắp xếp | Ý tưởng | Tốt nhất / Xấu nhất |
|---|---|---|
| Chọn | Mỗi lượt chọn số nhỏ nhất của đoạn còn lại, đưa về đầu đoạn | O(n2) / O(n2); ít đổi chỗ nhất |
| Nổi bọt | Đổi chỗ hai phần tử cạnh nhau đứng sai thứ tự; dừng sớm nếu không còn đổi | O(n) / O(n2) |
| Chèn (không bắt buộc) | Chèn từng phần tử vào đoạn đã xếp ở phía trước | O(n) / O(n2); hợp với dãy gần xếp sẵn |
Luyện tập
Bài 1. Đoàn tàu đúng thứ tự
Thỏ xếp n toa tàu đồ chơi, mỗi toa dán một số. Thỏ muốn biết các toa đã được xếp theo thứ tự không giảm từ trái sang phải (mỗi toa có số không nhỏ hơn toa đứng ngay trước nó) hay chưa.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | In YES nếu dãy đã xếp không giảm, ngược lại in NO. | |
| Test | Input | Output |
| 1 | 5 1 2 2 4 9 | YES |
| 2 | 4 3 5 4 8 | NO |
Bài 2. Xếp hàng theo chiều cao
Cô giáo muốn xếp n bạn trong lớp thành một hàng từ thấp đến cao. Em hãy giúp cô bằng cách viết hàm sắp xếp chọn để xếp chiều cao của các bạn.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 1000). Dòng 2: n số nguyên h[i] là chiều cao (cm) của các bạn (1 ≤ h[i] ≤ 300). | |
|---|---|---|
| Đầu ra | Dãy chiều cao sau khi sắp xếp tăng dần, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 6 150 142 160 138 150 155 | 138 142 150 150 155 160 |
| 2 | 1 7 | 7 |
Bài 3. Bảng điểm giảm dần
Gấu Po tổ chức thi bắn cung cho n bạn. Gấu Po muốn công bố bảng điểm từ cao xuống thấp. Hãy dùng sắp xếp nổi bọt để xếp điểm giảm dần nhé.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 1000). Dòng 2: n số nguyên a[i] (0 ≤ a[i] ≤ 100). | |
|---|---|---|
| Đầu ra | Dãy điểm sau khi sắp xếp giảm dần, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 5 8 10 6 9 10 | 10 10 9 8 6 |
| 2 | 4 3 3 3 3 | 3 3 3 3 |
Bài 4. Vết tích sắp xếp chọn
Hổ đang chạy thuật toán sắp xếp chọn (tăng dần) trên dãy a. Ở lượt thứ i (i bắt đầu từ 1), Hổ tìm số nhỏ nhất trong đoạn từ vị trí i đến vị trí n rồi đổi chỗ với số đang đứng ở vị trí i (nếu có nhiều số nhỏ nhất, chọn số đứng bên trái nhất). Hãy cho biết dãy sau đúng k lượt.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ n ≤ 1000; 0 ≤ k ≤ n - 1). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Dãy sau k lượt, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 5 2 64 25 12 22 11 | 11 12 25 22 64 |
| 2 | 4 0 3 1 2 9 | 3 1 2 9 |
Bài 5. Đếm lần đổi chỗ
Thỏ dùng sắp xếp nổi bọt để xếp n thẻ bài tăng dần. Mỗi lần hai thẻ cạnh nhau đứng sai thứ tự và được đổi chỗ, Thỏ ghi một dấu gạch. Hỏi cuối cùng Thỏ ghi bao nhiêu dấu gạch?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 2000). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng số lần đổi chỗ khi chạy sắp xếp nổi bọt. | |
| Test | Input | Output |
| 1 | 4 4 3 2 1 | 6 |
| 2 | 5 1 2 3 5 4 | 1 |
Bài 6. Bong bóng dừng sớm
Trong sắp xếp nổi bọt, mỗi lượt là một lần đi từ đầu dãy đến cuối đoạn chưa xếp, so sánh và đổi chỗ các cặp cạnh nhau. Bong bóng sẽ dừng ngay khi có một lượt mà không đổi chỗ lần nào. Hỏi có bao nhiêu lượt có thực hiện ít nhất một lần đổi chỗ?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 1000). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số lượt có đổi chỗ. | |
| Test | Input | Output |
| 1 | 3 3 1 2 | 1 |
| 2 | 5 5 4 3 2 1 | 4 |
Bài 7. Bục vinh quang
Cuộc thi chạy có n vận động viên, Gấu Po chỉ cần trao giải cho k bạn có điểm cao nhất (hai bạn bằng điểm vẫn tính là hai bạn khác nhau). Hãy in ra điểm của k bạn đó từ cao xuống thấp. Gợi ý: không cần xếp cả dãy, chỉ cần chạy đúng k lượt chọn.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ k ≤ 10 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (0 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | k số nguyên giảm dần (không tăng), cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 6 3 70 95 85 95 60 90 | 95 95 90 |
| 2 | 10 1 5 9 9 2 1 1 3 4 6 8 | 9 |
Bài 8. Xếp lại chữ cái
Thỏ có một xâu s gồm các chữ cái thường được làm bằng nhựa. Thỏ muốn xếp các chữ cái theo thứ tự bảng chữ cái từ a đến z. Em hãy viết chương trình giúp Thỏ nhé.
| Đầu vào | Một dòng duy nhất chứa xâu s (1 ≤ độ dài ≤ 1000), chỉ gồm chữ cái thường. | |
|---|---|---|
| Đầu ra | Xâu sau khi xếp các ký tự theo thứ tự tăng dần. | |
| Test | Input | Output |
| 1 | banana | aaabnn |
| 2 | zebra | aberz |
Bài 9. Bảng thành tích
Hổ có bảng điểm của n bạn, mỗi bạn thi m môn và có một hàng điểm. Hổ muốn sắp xếp các hàng theo tổng điểm tăng dần. Nếu hai hàng có tổng bằng nhau thì giữ nguyên thứ tự ban đầu của chúng.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n ≤ 500; 1 ≤ m ≤ 50). n dòng tiếp theo, mỗi dòng gồm m số nguyên (0 ≤ giá trị ≤ 100). | |
|---|---|---|
| Đầu ra | n dòng, mỗi dòng gồm m số của một hàng sau khi sắp xếp. | |
| Test | Input | Output |
| 1 | 3 3 5 5 5 1 2 3 9 0 6 | 1 2 3 5 5 5 9 0 6 |
| 2 | 2 2 1 1 0 2 | 1 1 0 2 |
Bài tập tự luyện
Bài 1. Á quân
Cuộc thi có n bạn tham gia. Điểm cao nhất thuộc về quán quân; á quân là bạn có điểm cao nhất trong số các bạn có điểm thấp hơn quán quân. Hãy tìm điểm của á quân, hoặc in -1 nếu mọi bạn đều bằng điểm nhau.
| Đầu vào | Dòng 1: số nguyên n (2 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (0 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Điểm của á quân, hoặc -1 nếu không có. | |
| Test | Input | Output |
| 1 | 5 7 9 9 3 8 | 8 |
| 2 | 3 4 4 4 | -1 |
Bài 2. Hai bạn gần nhau nhất
Trong lớp có n bạn, Gấu Po muốn chọn hai bạn có chiều cao chênh nhau ít nhất để làm cặp đôi nhảy múa. Hãy cho biết độ chênh lệch nhỏ nhất đó.
| Đầu vào | Dòng 1: số nguyên n (2 ≤ n ≤ 3000). Dòng 2: n số nguyên h[i] (1 ≤ h[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Giá trị nhỏ nhất của |h[i] - h[j]| với i khác j. | |
| Test | Input | Output |
| 1 | 5 13 4 20 9 15 | 2 |
| 2 | 3 5 5 12 | 0 |
Bài 3. Bạn đứng giữa hàng
Lớp có một số lẻ n bạn. Khi xếp hàng từ thấp đến cao, Thỏ đứng đúng ở giữa hàng (có số bạn bên trái bằng số bạn bên phải). Hãy cho biết chiều cao của bạn đứng giữa hàng.
| Đầu vào | Dòng 1: số nguyên lẻ n (1 ≤ n ≤ 3001). Dòng 2: n số nguyên h[i] (1 ≤ h[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Chiều cao của bạn đứng giữa hàng sau khi xếp. | |
| Test | Input | Output |
| 1 | 5 150 140 165 155 145 | 150 |
| 2 | 1 130 | 130 |
Bài 4. Đếm loại thẻ
Hổ có n thẻ bài, mỗi thẻ ghi một số. Hai thẻ ghi cùng số là cùng loại. Em hãy xếp các thẻ theo thứ tự rồi đếm xem có bao nhiêu loại thẻ khác nhau.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 5000). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số loại thẻ khác nhau. | |
| Test | Input | Output |
| 1 | 7 4 2 4 9 2 7 9 | 4 |
| 2 | 3 5 5 5 | 1 |
Bài 5. Chẵn trước, lẻ sau
Gấu Po muốn xếp n viên kẹo theo luật: các viên có số chẵn đứng trước và xếp tăng dần, các viên có số lẻ đứng sau và xếp giảm dần. Hãy in ra dãy kẹo sau khi xếp.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 2000). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Dãy sau khi xếp, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 8 5 2 8 1 4 7 6 3 | 2 4 6 8 7 5 3 1 |
| 2 | 4 3 4 3 2 | 2 4 3 3 |
Bài 6. Hạng của từng bạn
Thỏ muốn công bố hạng của từng bạn trong kỳ thi. Hạng của một bạn bằng 1 cộng với số bạn có điểm cao hơn bạn đó (hai bạn bằng điểm thì cùng hạng). Hãy in hạng của các bạn theo đúng thứ tự trong danh sách ban đầu.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 3000). Dòng 2: n số nguyên a[i] (0 ≤ a[i] ≤ 1000). | |
|---|---|---|
| Đầu ra | n số nguyên là hạng của từng bạn, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 5 80 95 80 70 100 | 3 2 3 5 1 |
| 2 | 3 5 5 5 | 1 1 1 |
Bài 7. Chèn thẻ vào hàng (không bắt buộc)
Các thẻ bài của Hổ đã được xếp tăng dần. Hổ vừa nhận được một thẻ mới ghi số x và muốn chèn thẻ vào đúng chỗ để dãy vẫn tăng dần. Đây chính là bước cơ bản của sắp xếp chèn.
| Đầu vào | Dòng 1: hai số nguyên n, x (1 ≤ n ≤ 105; 0 ≤ x ≤ 109). Dòng 2: n số nguyên tăng dần (không giảm) a[i] (0 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | n + 1 số của dãy sau khi chèn x, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 5 6 1 3 5 7 9 | 1 3 5 6 7 9 |
| 2 | 3 0 2 4 6 | 0 2 4 6 |
Bài 8. Chia đội cân bằng
Gấu Po có 2n bạn, mỗi bạn có một sức mạnh. Gấu Po chia các bạn thành n cặp, mỗi bạn thuộc đúng một cặp. Sức mạnh của một cặp là tổng sức mạnh hai bạn. Gấu Po muốn cặp mạnh nhất không quá mạnh. Hãy tìm giá trị nhỏ nhất có thể của sức mạnh cặp mạnh nhất.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 1000). Dòng 2: 2n số nguyên s[i] (1 ≤ s[i] ≤ 106). | |
|---|---|---|
| Đầu ra | Giá trị nhỏ nhất có thể của sức mạnh cặp mạnh nhất. | |
| Test | Input | Output |
| 1 | 2 3 5 2 3 | 7 |
| 2 | 3 1 2 3 4 5 6 | 7 |
Bài 9. Thử thách: Ít lần đổi chỗ nhất
Hổ có n tấm thẻ đánh số từ 1 đến n (mỗi số đúng một thẻ) xếp thành hàng theo thứ tự lộn xộn. Mỗi lần đổi chỗ, Hổ chọn hai vị trí bất kỳ rồi hoán đổi hai tấm thẻ ở đó. Hổ muốn xếp thẻ thành 1, 2, ..., n với số lần đổi chỗ ít nhất. Hỏi số lần ít nhất đó là bao nhiêu?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên là một hoán vị của 1, 2, ..., n. | |
|---|---|---|
| Đầu ra | Số lần đổi chỗ ít nhất. | |
| Test | Input | Output |
| 1 | 3 2 1 3 | 1 |
| 2 | 4 4 3 2 1 | 2 |
- Gợi ý chung: Khi chưa chắc về thứ tự các vòng lặp, hãy chạy tay thuật toán trên 4 hoặc 5 số như các sơ đồ ở phần kiến thức rồi mới viết code. Hãy luôn nhìn giới hạn của n: với n khoảng 1000 đến 5000 có thể sắp xếp tay bằng hai vòng lặp (O(n2)); với n khoảng 105 thì phải tìm cách chỉ duyệt vài lần qua dãy (O(n) hoặc O(k.n) với k nhỏ). Một số bài không cần xếp toàn bộ dãy, chỉ cần một vài lượt chọn hoặc một vòng lặp tìm số lớn nhất.