Sắp xếp

Sắp xếp nói chung là một khái niệm trong đó các phần tử của một vùng chứa được sắp xếp lại theo một thứ tự hợp lý.

Sắp xếp là một trong những kỹ thuật cơ bản và nền tảng nhất được áp dụng cho dữ liệu thông qua các hàm. Điều này có nghĩa là sắp xếp cho phép chúng ta sắp xếp một chuỗi phần tử theo cách cụ thể mà ta muốn, dựa trên một thứ tự hợp lý.

Các thuật toán sắp xếp giúp thao tác với dữ liệu, đồng thời hỗ trợ giải nhiều bài toán toán học và lập trình.

*Để sử dụng các phương thức, ta cần đưa tệp tiêu đề algorithm vào đầu tệp C++ bằng cách dùng #include <algorithm>.

Bạn sẽ tìm hiểu về các hàm dựng sẵn trong thư viện thuật toán STL dùng để sắp xếp dữ liệu. 
Ba hàm chúng ta sẽ tìm hiểu là:

• sort()
• is_sorted()
• partial_sort()

Phương thức sort

Phương thức sort() của STL sắp xếp nội dung trong phạm vi đã cho. Phương thức này cần một trình lặp bắt đầu và một trình lặp kết thúc, rồi sẽ sắp xếp các phần tử trong phạm vi đó theo thứ tự tăng dần.

Ta có thể dùng phương thức này theo hai cách:

• sort(starting_iterator, ending_iterator) - sắp xếp phạm vi được xác định bởi các trình lặp theo thứ tự tăng dần
• sort(starting_iterator, ending_iterator, comparing_function) - sắp xếp phạm vi được xác định bởi các trình lặp, dựa trên hàm được cung cấp làm tham số thứ ba

vector<int> numbers = {3, 5, 1, 2, 4};

sort(numbers.begin(), numbers.end());

for(auto i = numbers.begin(); i != numbers.end(); i++)
	cout << *i << " ";

Output:
1 2 3 4 5

Như bạn thấy trong đoạn code trên, phương thức sort() đã sắp xếp vector theo thứ tự tăng dần.

bool compare(int a, int b)
{
	return a > b; // trả về 1 nếu a lớn hơn b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4};
	
	sort(numbers.begin(), numbers.end(), compare);
	
	for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
5 4 3 2 1

Như vậy, bạn có thể thấy ta đã dùng cách thứ hai của phương thức sort. Ta tạo hàm compare() sao cho hàm trả về true nếu a lớn hơn b. Nhờ đó, ta có thể sắp xếp vector theo thứ tự giảm dần.

Phương thức is_sorted

Phương thức is_sorted() là một hàm của STL, trả về true hoặc false để cho biết phạm vi đã cho có được sắp xếp hay không. 

Phương thức is_sorted() cũng có hai cách dùng, giống hệt phương thức sort():

• is_sorted(starting_iterator, ending_iterator) - Kiểm tra xem phạm vi được xác định bởi hai trình lặp có được sắp xếp theo thứ tự tăng dần hay không, trả về true nếu có, nếu không thì trả về false
• is_sorted(starting_iterator, ending_iterator, comparing_function) - Kiểm tra xem phạm vi được xác định bởi hai trình lặp có được sắp xếp hay không, dựa trên hàm so sánh.

vector<int> numbers = {3, 5, 1, 2, 4};

cout << is_sorted(numbers.begin(), numbers.end()) << endl;

sort(numbers.begin(), numbers.end());

cout << is_sorted(numbers.begin(), numbers.end());

Output:
0
1

bool compare(int a, int b)
{
	return a > b; // trả về 1 nếu a lớn hơn b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4};
	
	cout << is_sorted(numbers.begin(), numbers.end(), compare) << endl;
	
	sort(numbers.begin(), numbers.end(), compare);
	
	cout << is_sorted(numbers.begin(), numbers.end(), compare);

Output:
0
1

Phương thức partial_sort

Phương thức parital_sort() sắp xếp nửa đầu các phần tử trong phạm vi đã cho và giữ nguyên nửa còn lại. 
Phương thức này cũng có hai cách dùng:

• partial_sort(start, middle, end) - Sắp xếp phạm vi từ start đến end sao cho các phần tử từ trình lặp bắt đầu đến trình lặp giữa được sắp xếp theo thứ tự tăng dần, còn các phần tử từ trình lặp giữa đến trình lặp kết thúc được giữ nguyên
• partial_sort(start, middle, end, compare) - Sắp xếp phạm vi từ start đến end sao cho các phần tử từ start đến middle được sắp xếp dựa trên hàm so sánh, còn các phần tử từ middle đến end được giữ nguyên

vector<int> numbers = {3, 5, 1, 2, 4, 10, 7};

partial_sort(numbers.begin(), numbers.begin() + 4, numbers.end());

for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
1 2 3 4 5 10 7

bool compare(int a, int b)
{
	return a > b; // trả về 1 nếu a lớn hơn b
}

int main()
{
	vector<int> numbers = {3, 5, 1, 2, 4, 10, 7};
	
	partial_sort(numbers.begin(), numbers.begin() + 3, numbers.end(), compare);
	
	for(auto i = numbers.begin(); i != numbers.end(); i++)
		cout << *i << " ";

Output:
10 7 5 1 2 3 4

Như bạn thấy, phương thức partial_sort() hoạt động hơi khác một chút, nhưng bạn không cần bận tâm đến điều đó vì bạn sẽ hiếm khi dùng kiểu sắp xếp một phần. 

Hiện tại, hãy nhớ sắp xếp là gì, nhớ cách dùng đúng các phương thức sort() và is_sorted(), rồi luyện tập sử dụng chúng.