![[Bài 50] Hàm Sort Trong C++](/storage/photos/1/cpp/ham-sap-xep-trong-cpp.png "[Bài 50] Hàm Sort Trong C++")
Hàm sort() trong thư viện algorithm của ngôn ngữ lập trình C++ là một hàm thuật toán rất hiệu quả và được sử dụng thường xuyên trong lập trình. Bài học này sẽ hướng dẫn các bạn cách sử dụng hàm sort() để sắp xếp với mảng, vector, string.
1. Hàm sort() trong C++
Hàm sort() trong C++ là hàm thuật toán thuộc thư viện algorithm, bạn có thể sử dụng ngay hàm này khi cần sắp xếp mà không cần cài đặt lại từ đầu.
Hàm sort() được cài đặt trong C++ là hàm intro - sort, đây là sự kết hợp của 2 thuật toán sắp xếp rất hiệu quả là quick sort và heap sort
Độ phức tạp của hàm sort() là O(NlogN). Bạn có thể sử dụng hàm này để sắp xếp mảng, vector, string.
Mặc định thì hàm này sẽ sắp xếp mảng của bạn tăng dần về giá trị số hoặc từ điển, nếu muốn sắp xếp giảm dần bạn cần thêm tham số greater()
Cú pháp sort mảng :
sort(a, a + n);
// Sắp xếp mảng a từ chỉ số x tới chỉ số y
sort(a + x, a + y + 1);
// Sắp xếp mảng giảm dần
sort(a, a + n, greater<data_type>());
Ví dụ 1 :
#include <algorithm>
using namespace std;
int main() {
int a[] = {3, 1, 2, 5, 6, 4, 8, 9, 10, 7};
int n = 10;
sort(a, a + n);
cout << "Mang a sau khi sap xep tang dan : ";
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
sort(a, a + n, greater<int>());
cout << "\nMang a sau khi sap xep giam dan : ";
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
}
Output :
Mang a sau khi sap xep giam dan : 10 9 8 7 6 5 4 3 2 1
Nếu bạn có mảng string hay mảng char thì hàm sort() sẽ sắp xếp mặc định theo thứ tự từ điển tăng dần.
Ví dụ 2 :
#include <algorithm>
using namespace std;
int main() {
char a[] = {'2', '8', 't', 'e', 'c', 'h', 'a', 'z'};
int n = 8;
sort(a, a + n);
cout << "Mang char sap tang dan : ";
for (int i = 0; i < n; i++) {
cout << a[i] << ' ';
}
sort(a, a + n, greater<char>());
cout << "\nMang char sap giam dan : ";
for (int i = 0; i < n; i++) {
cout << a[i] << ' ';
}
}
Output :
Mang char sap giam dan : z t h e c a 8 2
Cú pháp sắp xếp vector :
sort(a.begin(), a.end());
// Sắp xếp vector a từ chỉ số x tới chỉ số y
sort(a.begin() + x, a.begin() + y + 1);
// Sắp xếp vector giảm dần
sort(a.begin(), a.end(), greater<data_type>());
Ví dụ 3 :
#include <algorithm>
using namespace std;
int main() {
vector<int> v = {3, 1, 2, 5, 4};
sort(v.begin(), v.end());
cout << "Vector sap tang dan : ";
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
sort(v.begin(), v.end(), greater<int>());
cout << "\nVector sap giam dan : ";
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
}
Output :
Vector sap giam dan : 5 4 3 2 1
2. Một số bài tập áp dụng hàm sort()
Có nhiều bài toán mà bạn có thể sử dụng bước sắp xếp trước khi xử lý, phần này mình sẽ hướng dẫn các bạn 3 ví dụ để luyện tập với hàm sort.
Bài 1. Đếm số lượng giá trị khác nhau trong mảng
Thuật toán : Sắp xếp mảng tăng dần để các giá trị giống nhau sẽ đứng cạnh nhau, khi đó bạn chỉ cần so sánh 2 phần tử kề nhau trong mảng để đếm số giá trị khác nhau. Nếu 2 phần tử đứng cạnh nhau mà bằng nhau thì bạn không cần tăng số giá trị khác nhau lên.
Mã nguồn :
#include <algorithm>
using namespace std;
int main() {
int a[] = {1, 3, 3, 3, 2, 1, 2, 2, 2, 4, 0, 2};
int n = 12;
sort(a, a + n);
int dem = 1; // a[0]
for (int i = 1; i < n; i++) {
if (a[i] != a[i - 1]) {
++dem;
}
}
cout << "So gia tri khac nhau : " << dem << endl;
}
Output :
Bài 2 : Tìm độ chênh lệch nhỏ nhất giữa 2 phần tử trong mảng
Thuật toán : Sắp xếp mảng tăng dần (hoặc giảm dần) để những giá trị gần nhau sẽ đứng cạnh nhau khi đó bạn chỉ cần xét độ chênh lệch giữa 2 phần tử đứng cạnh nhau và tìm giá trị nhỏ nhất.
Độ phức tạp sẽ là O(NlogN) thay vì O(N2) nếu bạn dùng 2 for lồng nhau để xét mọi cặp phần tử trong mảng
Mã nguồn :
#include <algorithm>
using namespace std;
int main() {
int a[] = {3, 8, 10, 4, 12, 21, 1};
int n = 7;
sort(a, a + n);
int max_diff = 1000000000;
for (int i = 1; i < n; i++) {
if (a[i] - a[i - 1] < max_diff) {
max_diff = a[i] - a[i - 1];
}
}
cout << "Do chenh lech nho nhat : " << max_diff << endl;
}
Output :
Bài 3. Đếm tần suất xuất hiện của từng giá trị trong mảng và liệt kê theo thứ tự từ nhỏ tới lớn
Thuật toán : Sắp xếp mảng tăng dần sau đó xét các cặp phần tử đứng cạnh nhau để đếm tần suất xuất hiện, vì khi sắp tăng dần thì các giá trị giống nhau sẽ đứng cạnh nhau.
Mã nguồn :
#include <algorithm>
using namespace std;
int main() {
int a[] = {1, 3, 3, 3, 2, 1, 2, 4, 2, 4, 0, 2};
int n = 12;
sort(a, a + n);
int dem = 1; // a[0];
for (int i = 1; i < n; i++) {
if (a[i] == a[i - 1]) {
++dem;
} else {
cout << a[i - 1] << " xuat hien " << dem << " lan\n";
dem = 1;
}
}
cout << a[i - 1] << " xuat hien " << dem << " lan\n";
}
Output :
1 xuat hien 2 lan
2 xuat hien 4 lan
3 xuat hien 3 lan
4 xuat hien 2 lan
