owned this note
owned this note
Published
Linked with GitHub
---
title
Sắp xếp (Sorting)
---
Sắp xếp (Sorting)
===
---
###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]
---
# Lời nói đầu
- Sắp xếp là một trong những thuật toán quan trọng nhất và phổ biến nhất trong lập trình nói riêng và chương trình chuyên tin nói chung.
- Thuật toán sắp xếp còn được ứng dụng để kết hợp với nhiều thuật toán khác (điển hình là tìm kiếm nhị phân sẽ được nói trong những bài viết sau).
- Thật ra nếu ta sử dụng C++ thì đã có sẵn thư viện để sử dụng. Tuy nhiên, việc biết một số thuật toán sắp xếp sẽ giúp ta tư duy thuật toán tốt hơn.
- Bài viết này sẽ cung cấp thuật toán sắp xếp để có thể giải quyết bài toán sau:
---
Cho một số nguyên dương $n$ và mảng $a$ gồm $n$ phần tử. Hãy sắp xếp mảng $a$ theo thứ tự **không giảm**.
#### Input
- Dòng đầu là số nguyên dương $n$ ($n \le 10^3$).
- Dòng thứ hai gồm $n$ số nguyên $a_1,a_2,...,a_n$ ($a_i \le 10^4$).
#### Output
- Gồm $n$ số nguyên tương ứng với mảng $a$ sau khi đã được sắp xếp.
# Các thuật toán sắp xếp
## 1. Sắp xếp nổi bọt (Bubble sort)
- Đây là thuật toán dễ hiểu nhất mà đa số những người mới đều học.
### 1.1. Ý tưởng
- Duyệt qua từng cặp phần tử liên tiếp, nếu phần tử **ở sau** lớn hơn phần tử **ở trước**, ta thực hiện **đổi chỗ** hai phần tử. Thực hiện cho đến khi mảng đã được sắp xếp.
- Nhận thấy ta cần lặp lại quá trình trên không quá $N-1$ lần ($N$ là số phần tử của mảng).
::: success
::: spoiler **Chứng minh**
- Lần lặp đầu tiên chắc chắn đưa phần tử lớn nhất ra vị trí cuối trong mảng.
- Lần lặp thứ hai chắc chắn đưa phần tử lớn nhì ra vị trí kế cuối trong mảng.
- Tiếp tục như vậy $N-1$ lần, ta chắc chắn đưa $N-1$ số cuối cùng về đúng vị trí, điều đó có nghĩa là số bé nhất còn lại cũng đã nằm đúng vị trí.
- Vậy mảng đã được sắp xếp.
:::
### 1.2. Cài đặt
``` cpp=
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int a[n + 1];
for (int i = 1; i <= n; i++) cin >> a[i];
for (int t = 1; t <= n-1; t++)
{
for (int i = 1; i <= n-1; i++)
{
if(a[i] > a[i + 1]) swap(a[i], a[i + 1]);
}
}
for (int i = 1; i <= n; i++) cout << a[i] << ' ';
return 0;
}
```
### 1.3. Độ phức tạp
- Lặp lại $N-1$ lần, mỗi lần duyệt qua $N-1$ cặp, độ phức tạp của thuật toán là $O(n^2)$.
### 1.4. Ưu điểm
- Dễ cài đặt, dễ nhớ.
- Không tốn thêm bộ nhớ.
### 1.5. Nhược điểm
- Thuật toán có độ phức tạp lớn, thường chạy chậm khi xử lí dữ liệu lớn.
## 2. Sắp xếp chèn (Insertion sort)
### 2.1. Ý tưởng
- Ta sẽ chia mảng thành 2 phần, phần **đã sắp xếp** và phần **chưa sắp xếp**.
- Giả sử ta đã sắp xếp $k$ phần tử đầu, ta sắp xếp $k+1$ bằng cách tìm vị trí phù hợp của phần tử thứ $k+1$ và thực hiện "chèn" nó vào đó.
- Ví dụ: ta có phần $[1,2,3,5,4,...]$ đã sắp xếp phần $[1,2,3,5]$, ta xếp phần tử thứ $5$ là số $4$ bằng cách tìm vị trí thích hợp để chèn $4$ vào, là vị trí sau phần tử thứ $3$. Mảng sau khi thực hiện thao tác trên trở thành $[1,2,3,4,5,...]$.
### 2.2. Cài đặt
``` cpp=
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int a[n + 1];
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 2; i <= n; i++)
{
int j = i;
// Tìm vị trí thích hợp
while(j > 1 && a[i] < a[j - 1]) j--;
// Thực hiện chèn
int temp = a[i];
for (int k = i; k > j; k--) a[k] = a[k - 1];
a[j] = temp;
}
for (int i = 1; i <= n; i++) cout << a[i] << ' ';
return 0;
}
```
### 2.3. Độ phức tạp
- Trong trường hợp tệ nhất, ta cần chèn tất cả phần tử đang xét vào vị trí đầu tiên, độ phức tạp thuật toán là $O(n^2)$.
### 2.4. Ưu điểm
- Thuật toán chạy **rất nhanh** với mảng có **ít** phần tử hoặc mảng **gần đúng thứ tự**.
- Không tốn thêm bộ nhớ.
### 2.5. Nhược điểm
- Thuật toán có độ phức tạp lớn, thường chạy chậm khi xử lí dữ liệu lớn.
## 3. Sắp xếp nhanh (Quick sort)
### 3.1. Ý tưởng
- Ta sẽ chọn một phần tử làm **khóa**, sau đó thực hiện:
- Đưa các phần tử nhỏ hơn phần tử **khóa** về bên trái.
- Đưa các phần tử lớn hơn hoặc bằng phần tử **khóa** về bên phải.
- Tiếp tục làm tương tự cho 2 vùng vừa chia (Từ biên trái đến khóa, và từ khóa đến biên phải).
### 3.2. Cài đặt
``` cpp=
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int a[N]; // Trong cách cài đặt này, ta khai báo mảng toàn cục để sử dụng trong hàm
void quicksort(int left, int right)
{
int i = left, j = right;
int pivot = a[(left + right)/2]; // Phần tử khóa có thể chọn bất kì (thường là ngẫu nhiên)
// Tuy nhiên, để minh họa thì đoạn code này sẽ chọn phần tử trung vị
while(i <= j)
{
while(a[i] < pivot) i++;
while(a[j] > pivot) j--;
if(i <= j)
{
swap(a[i], a[j]);
i++;
j--;
}
}
// Tiếp tục xử lí cho 2 vùng đã được chia
if(left < j) quicksort(left, j);
if(i < right) quicksort(i, right);
}
int main()
{
int n;
cin >> n;
for (int i = 1;i <= n; i++) cin >> a[i];
quicksort(1, n);
for (int i = 1; i <= n; i++) cout << a[i] << ' ';
return 0;
}
```
### 3.3. Độ phức tạp
- Tùy vào cách chọn **khóa**, 2 vùng được chia ra không tốt, độ phức tạp trong trường hợp xấu nhất là $O(n^2)$. Tuy nhiên, nếu ta chọn hoàn toàn ngẫu nhiên, độ phức tạp trung bình của thuật toán là $O(n\log{n})$.
### 3.4. Ưu điểm
- Thuật toán có độ phức tạp trung bình nhanh.
### 3.5. Nhược điểm
- Khó cài đặt.
- Có tỉ lệ gặp trường hợp xấu dẫn đến thuật toán chạy chậm.
- Các phần tử bằng nhau có thể không nằm theo vị trí ban đầu sau khi sắp xếp.
## 4. Sắp xếp đếm (Counting sort)
### 4.1. Ý tưởng
- Ta gọi mảng `cnt_i` là số phần tử có giá trị bằng $i$ trong mảng $A$.
- Ví dụ: `A = {1, 2, 1, 2, 3}` có `cnt = {0, 2, 2, 1}`
- Sau khi có được mảng $cnt$, ta duyệt từ $0$ đến phần tử lớn nhất trong mảng, khi này $i$ sẽ tăng dần, với mỗi số $i$ ta in $cnt_i$ lần giá trị $i$. Những số được in ra theo thứ tự là mảng $A$ sau khi sắp xếp.
- ***Lưu ý:** Trong bài viết này, ta sẽ mặc định các phần tử của mảng đều không âm. Trong trường hợp cần xử lí số âm thì ta thực hiện `+d` vào tất cả phần tử của mảng `A` với `d` là giá trị tuyệt đối của số âm nhỏ nhất, sau đó `-d` khi in ra kết quả.*
### 4.2. Cài đặt
``` cpp=
#include <bits/stdc++.h>
using namespace std;
const int maxA = 1e4 + 5;
int main()
{
int n;
cin >> n;
int a[n + 1];
int cnt[maxA + 1] = {0}; // maxA là phần tử lớn nhất có thể xuất hiện trong mảng, ban đầu gán tất cả cnt[i] = 0
for (int i = 1;i <= n; i++)
{
cin >> a[i];
cnt[a[i]]++; // Tăng giá trị của cnt[a[i]] với mỗi phần tử a[i]
}
for (int i = 0; i <= maxA; i++)
{
for (int j = 0; j < cnt[i]; j++) cout << i << ' ';
}
return 0;
}
```
### 4.3. Độ phức tạp
- Khác với những thuật toán sắp xếp đã nêu ở trên, thuật toán này có độ phức tạp còn dựa vào phần tử lớn nhất trong mảng, vì ta cần duyệt tất cả giá trị trong khoảng đó và in ra tất cả phần tử.
- Tóm lại, độ phức tạp của thuật toán là $O(maxA_i+n)$
### 4.4. Ưu điểm
- Trong trường hợp bộ dữ liệu có nhiều phần tử nhưng các phần tử không quá lớn, thuật toán này chạy cực nhanh.
- Cài đặt tương đối đơn giản.
### 4.5. Nhược điểm
- Tốn thêm bộ nhớ.
- Không chạy được khi khoảng cách giữa số lớn nhất và số nhỏ nhất quá lớn.
## 5. Các thuật toán sắp xếp khác
- Ngoài 3 thuật toán đã được nêu ở trên, vẫn còn rất nhiều thuật toán sắp xếp khác như:
- Sắp xếp chọn (Selection sort)
- Sắp xếp trộn (Merge sort)
- Sắp xếp theo cơ số (Radix sort)
- Mỗi thuật toán đều có ưu điểm và nhược điểm riêng, khuyến khích bạn đọc tự tìm hiểu.
# Sắp xếp trong C++
## 1. Giới thiệu hàm `std::sort()`
- Thực tế, trong C++ có thư viện `algorithm` (thuộc thư viện `bits/stdc++.h`) đã có sẵn hàm `std::sort()` rất mạnh mẽ.
- Ta được sử dụng hàm này trong kì thi tuyển sinh 10 của cả **Sở Giáo dục TP.HCM** và của **trường Phổ Thông Năng Khiếu**, giúp tối ưu thời gian làm bài đồng thời tránh những lỗi đáng tiếc.
- Cụ thể, bài viết này sẽ hướng dẫn cách dùng thông qua đoạn code dưới đây:
``` cpp=
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
int a[n + 1];
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
// Tham số đầu là địa chỉ biên trái của vùng muốn sắp xếp
// Tham số thứ hai là địa chỉ biên phải của vùng muốn sắp xếp
// Để sắp xếp cả mảng, ta truyền vào địa chỉ (a + 1, a + n + 1) do mảng được đếm từ 1 đến n
for (int i = 1; i <= n; i++) cout << a[i] << ' ';
return 0;
}
```
- ***Lưu ý:** hàm `std::sort()` nằm trong `namespace std` nên nếu đã `using namespace std;` thì ta có thể gọi trực tiếp `sort()`, để ngắn gọn thì bài viết này cũng sẽ gọi hàm là `sort()`*
- Cụ thể hơn, hàm `sort()` cần ít nhất 2 tham số lần lượt là địa chỉ biên trái và địa chỉ biên phải của vùng muốn sắp xếp:
``` cpp
sort([địa chỉ biên trái], [địa chỉ biên phải]);
```
- Hàm sẽ sắp xếp trong khoảng từ địa chỉ **biên trái** đến **địa chỉ ngay trước** địa chỉ **biên phải** theo thứ tự **không giảm**.
- ***Lưu ý:** 2 địa chỉ phải là 2 địa chỉ của cùng 1 dãy dữ liệu (1 mảng thường, 1 `array`, 1 `vector` hoặc 1 `string`).*
- Một số ví dụ:
- Ta có `int a[] = {5, 1, 4, 3, 2}`, sau khi thực hiện `sort(a, a + 3);`: `a` trở thành `{1,4,5,3,2}` (Vùng được sắp xếp bao gồm những địa chỉ $a, a+1, a+2$, lần lượt có giá trị tương ứng là $1,5,4$).
- Ta có `vector<double> b = {0.5, 0.01, 0.2}`, sau khi thực hiện `sort(b.begin(),b.end())`: `b` trở thành `{0.01, 0.2, 0.5}` (Vùng được sắp xếp là từ `b.begin()` đến `--b.end()`, hay nói cách khác là cả vector $b$).
- Ta có `string s = "s2g"`, sau khi thực hiện `sort(s.begin(),s.begin()+1)`: `s` trở thành `"2sg"` (Vùng được sắp xếp bao gồm `s.begin()` và `s.begin()+1`, là 2 phần tử đầu tiên).
- Để trực quan hóa: gọi $l,r$ lần lượt là vùng cần sắp xếp
- Sắp xếp một mảng bình thường: `sort(a + l, a + r + 1);`
- Sắp xếp một vector, string, array: `sort(a.begin() + l, a.begin() + r + 1);`
- Sắp xếp cả vector, string, array: `sort(a.begin(), a.end());`
- Để sắp xếp theo thứ tự **không tăng**, ta thêm tham số `greater<[data_type]>()` vào làm tham số thứ 3, với `[data_type]` là kiểu dữ liệu ta đã khai báo.
- Cách hoạt động của tham số thứ 3 sẽ được trình bày rõ hơn ở phần sau.
- Ví dụ:
``` cpp=
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a[] = {1, 2, 3, 4, 5};
sort(a, a + 5, greater<int>()); // mảng a kiểu int nên ta gọi tham số greater<int>()
for (int i = 0; i < 5; i++) cout << a[i] << ' ';
}
```
- Chương trình sẽ xuất ra: `5 4 3 2 1`.
- Hàm này có độ phức tạp là $O(n\cdot \log{n})$
## 2. Sắp xếp có điều kiện
### 2.1. Tham số so sánh
- Trong nhiều bài toán, ta có thể sẽ phải sắp xếp lại dãy theo một thứ tự bất kì nào đó, không nhất thiết phải sắp xếp lại dãy theo thứ tự từ bé đến lớn (và ngược lại) như hàm `sort` mặc định của C++.
- Để làm được điều đó, hàm `sort` trong C++ có hỗ trợ sắp xếp lại dãy theo một thứ tự bất kì từ một hàm so sánh hai phần tử cho trước. Cụ thể hơn, ta có cú pháp như sau:
```cpp
sort([tham số đầu], [tham số thứ hai], [compare]);
```
- Trong đó:
- `tham số đầu` là địa chỉ biên trái của vùng muốn sắp xếp.
- `tham số thứ hai` là địa chỉ biên phải của vùng muốn sắp xếp.
- `compare` là tên gọi của một hàm `bool` **(hàm này có thể mang tên khác)** được ta định nghĩa từ trước cho biết điều kiện thứ tự trước sau của hai phần tử bất kì trong dãy cần được sắp xếp.
- Hàm `compare` sẽ được truyền vào hai giá trị có **cùng** kiểu dữ liệu với nhau và đồng thời **cùng** kiểu dữ liệu với dãy phần tử cần được sắp xếp.
- Để dễ hiểu hơn, giả sử ta muốn sắp xếp một mảng $a$ có $n$ phần tử có giá trị tối đa là $`10^6`$ cho trước theo thứ tự từ **lớn đến bé**, ta có thể viết hàm `compare` và `sort` như sau:
```cpp
bool compare(int x, int y)
{
return x > y;
}
```
Gọi hàm `sort`:
```cpp
sort(a + 1, a + n + 1, compare);
```
- Trong đó:
- Hàm `sort` sẽ đưa vào hàm `compare` hai phần tử $x$ và $y$, với $x$ và $y$ là hai phần tử bất kì cần được so sánh khi sử dụng hàm `sort`.
- Ở hàm `compare`, dựa vào hai phần tử $x$ và $y$ cho trước từ hàm `sort`, ta sẽ so sánh hai giá trị $x$ và $y$ rồi trả về giá trị `bool` nào đó.
- Nếu giá trị hàm `compare` được trả về là `true` thì phần tử có giá trị $x$ sẽ đứng trước phần tử có giá trị $y$ trong mảng đã được sắp xếp.
- Ngược lại nếu trả về `false` thì phần tử có giá trị $y$ sẽ đứng trước phần tử có giá trị $x$.
- Tóm lại, để thực hiện việc **sắp xếp có điều kiện** trong C++, ta sẽ thực hiện như sau:
1. Cần viết sẵn một hàm `compare` kiểu dữ liệu `bool` và truyền vào hai phần tử nào đó có **cùng** kiểu dữ liệu với dãy phần tử cần được sắp xếp.
2. Hàm này sẽ so sánh hai phần tử được truyền vào và sẽ trả về `true` (sau vài bước xử lí nào đó với hai phần tử trên) nếu phần tử được truyền vào đầu tiên **xuất hiện đằng trước phần tử được truyền vào sau** trong mảng đã được sắp xếp và ngược lại.
3. Cuối cùng ta truyền hàm `compare` này vào hàm `sort` để sắp xếp dãy phần tử cho trước theo thứ tự được định nghĩa trong hàm `compare`.
### 2.2. Bài toán
#### Đề bài
Giả sử ta có bài toán sau:
Có $n$ bạn học sinh được đánh số từ $1$ đến $n$ đang đứng xếp thành một hàng dọc, bạn thứ $i$ ($1 \le i \le n$) có chiều cao là $h_i$ *cm* và cân nặng là $w_i$ *kg*. Các bạn học sinh sẽ được sắp xếp theo điều kiện sau:
- Những bạn có **chiều cao** bé hơn sẽ được đứng trước những bạn có **chiều cao** lớn hơn.
- Nếu có hai bạn có cùng **chiều cao** thì bạn có **cân nặng** bé hơn sẽ đứng trước bạn có **cân nặng** lớn hơn.
- Nếu cả hai bạn đều có cùng **chiều cao** và **cân nặng** thì bạn có **mã số** bé hơn sẽ đứng trước bạn có **mã số** lớn hơn.
#### Input
- Dòng đầu là số nguyên dương $n$ ($n \le 10^5$) - số học sinh đang xếp hàng.
- $n$ dòng sau, mỗi dòng gồm hai số nguyên dương $h_i$ và $w_i$ - lần lượt là **chiều cao** và **cân nặng** của học sinh thứ $i$.
#### Output
- Gồm $n$ số nguyên tương ứng với **mã số** của $n$ bạn học sinh sau khi được sắp xếp theo điều kiện trên.
#### Sample Input
```
6
170 65
167 58
167 55
185 72
152 55
170 65
```
#### Sample Output
```
5 3 2 1 6 4
```
### 2.3. Ý tưởng
- Chúng ta sẽ có 3 giá trị cần được lưu đối với mỗi học sinh, đó là $h$, $w$, và **mã số** của từng học sinh, vì cần lưu đồng thời cả 3 giá trị với mỗi em, chúng ta sẽ sử dụng `struct` để lưu chúng.
- Gọi `hs` là mảng chứa `struct` lưu thông tin của từng học sinh, ta cần sắp xếp mảng `hs` này theo một thứ tự hợp lí, cuối cùng ta in ra từng mã số của từng học sinh sau khi đã sắp xếp.
- Để sắp xếp mảng trên, ta sẽ xây dựng hàm `compare` để xác định thứ tự trước sau của các phần tử như sau:
- Hàm `compare` sẽ được truyền vào hai `struct` lưu ba thông tin trên của từng học sinh.
- Tiếp theo ta sẽ viết hàm so sánh để xác định thứ tự trước sau của từng học sinh, ta sẽ làm như sau:
1. Nếu hai em học sinh có chiều cao **khác nhau**, em có chiều cao **bé hơn** sẽ **đứng trước** em có chiều cao **lớn hơn**.
2. Nếu không ta sẽ so sánh cân nặng của hai em, nếu hai em có cân nặng **khác nhau** thì em có cân nặng **bé hơn** sẽ đứng trước.
3. Nếu không thì ta sẽ xếp em có mã số **bé hơn** đứng trước em có mã số **lớn hơn**. Vì mã số của mỗi học sinh là **độc nhất** nên ta không cần kiểm tra chúng có bằng nhau hay không.
### 2.4. Cài đặt
**Cách 1**:
```cpp=
#include <bits/stdc++.h>
using namespace std;
struct hocsinh
{
int h, w, maso; //lưu chiều cao, cân nặng và mã số từng học sinh
};
bool compare(hocsinh x, hocsinh y)
{
if (x.h != y.h) return x.h < y.h;
if (x.w != y.w) return x.w < y.w;
return x.maso < y.maso;
}
int main()
{
int n;
cin >> n;
hocsinh hs[n + 1];
for (int i = 1; i <= n; i++)
{
cin >> hs[i].h >> hs[i].w;
hs[i].maso = i;
}
sort(hs+ 1, hs + n + 1, compare);
//in ra danh sách sau khi đã sắp xếp
for (int i = 1; i <= n; i++) cout << hs[i].maso << ' ';
return 0;
}
```
**Cách 2**:
- Nếu không dùng `struct`, các bạn cũng có thể cài đặt như sau:
```cpp=
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int h[N], w[N];
bool compare(int x, int x)
{
if (h[x] != h[y]) return h[x] < h[y];
if (w[x] != w[y]) return w[x] < w[y];
return x < y;
}
int main()
{
int n;
cin >> n;
int ans[n + 1];
for (int i = 1; i <= n; i++)
{
cin >> h[i] >> w[i];
ans[i] = i;
}
sort(ans + 1, ans + n + 1, compare);
for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
return 0;
}
```
## 3. Quy tắc sắp xếp của hàm `sort()` trong C++
- **Sắp xếp có tham số so sánh**: Như đã nói ở trên, nếu có tham số so sánh là một hàm `compare`, hàm `sort()` sẽ sắp xếp dãy dữ liệu theo quy tắc ta tự đặt ra trong hàm `compare`. **Ngoại trừ** những trường hợp sau thì **bắt buộc** hàm `sort()` phải có tham số so sánh:
- **Sắp xếp dãy số:** Nếu không có tham số so sánh, dãy số được sắp xếp theo thứ tự **không giảm**.
- **Sắp xếp dãy kí tự: (string hoặc mảng kí tự)** Quy tắc tương tự dãy số, tuy nhiên giá trị của kí tự là vị trí của kí tự đó trong [bảng mã ASCII](https://vi.wikipedia.org/wiki/ASCII#K%C3%BD_t%E1%BB%B1_ASCII_in_%C4%91%C6%B0%E1%BB%A3c).
- **Sắp xếp dãy `pair`, `string`, `vector`**: Các cấu trúc dữ liệu trong dãy sẽ được sắp xếp theo [thứ tự từ điển](https://vi.wikipedia.org/wiki/To%C3%A1n_h%E1%BB%8Dc_t%E1%BB%95_h%E1%BB%A3p#Th%E1%BB%A9_t%E1%BB%B1_t%E1%BB%AB_%C4%91i%E1%BB%83n).
- **Sắp xếp với tham số `greater<data_type>()`**: Hàm sẽ sắp xếp theo thứ tự **không tăng** (Tương tự như sắp xếp không truyền tham số so sánh sau đó `reverse` cả mảng).
- Ta **chỉ có thể** dùng tham số `greater<data_type>()` khi tham số so sánh **có thể bỏ trống**. Nói cách khác, đó là việc sắp xếp những kiểu dữ liệu sau: số, kí tự, `pair`, `string`, `vector`, ...
# Bài tập
- Những bài tập dưới đây được tụi mình tổng hợp từ nhiều nguồn.
- Các bạn hãy cố giải các bài dưới đây với độ phức tạp thời gian là $1.0$s và độ phức tạp bộ nhớ là $512$MB.
## Bài 1: [VDCoder - SUMFIVE - Tổng 5 phần tử](https://vinhdinhcoder.net/Problem/Details/4666)
#### Đề Bài
- Cho dãy số nguyên gồm $n$ phần tử $B_1, B_2, ..., B_n$ $(n ≤ 5000, |B_i| ≤ 10^9)$. Bạn được quyền chọn ra $5$ phần tử bất kỳ sao cho tổng của chúng lớn nhất có thể. Hỏi tổng lớn nhất mà bạn nhận được là bao nhiêu?
#### Input
- Dòng $1$ là số nguyên $n$.
- Dòng $2$ là các phần tử trong dãy $B$.
#### Output
- In ra một số nguyên duy nhất là tổng thu được.
#### Sample Input
```
6
6 93 37 81 63 61
```
#### Sample Output
```
335
```
#### Giải thích
- Tổng thu được khi ta chọn $5$ số $93,37,81,63,61$ là: $93+37+81+63+61=335$
## Bài 2: [CSES - Distinct Number](https://cses.fi/problemset/task/1621)
#### Đề Bài
- Bạn được cho một dãy số gồm $n$ số nguyên, nhiệm vụ của bạn là tính số giá trị **khác nhau** có trong dãy này.
#### Input
- Dòng đầu gồm 1 số nguyên $n$: số phần tử của dãy.
- Dòng thứ hai gồm $n$ số nguyên $x_1, x_2, ..., x_n$.
#### Output
- In một số nguyên: Số giá trị khác nhau.
#### Giới hạn
- $1 \le n \le 2\cdot10^5$
- $1 \le x_i \le 10^9$
#### Sample Input
```
5
2 3 2 2 3
```
#### Sample Output
```
2
```
#### Giải thích
- Có $2$ giá trị riêng biệt là $2$ và $3$.
## Bài 3: HSGTP9 - TP.HCM - 2022 - Làm việc nhà
#### Đề Bài
- Bình hay giúp đỡ ba mẹ làm việc nhà. Để đảm bảo việc học, Bình chỉ có thể sắp xếp được một lượng thời gian $T$ để làm việc nhà. Bình lên danh sách những việc nhà mình có thể làm, đi kèm với thời gian cần đẻ thực hiện xong việc đó. Các việc nhà trên có thể thực hiện theo thứ tự bất kỳ, nhưng tại một thời điểm chỉ có thể thực hiện một việc nhất định. Bình đang tìm cách làm sao dể có thể thực hiện xong nhiều nhất các việc nhà trong danh sách của mình.
- **Yêu cầu:** Cho các việc nhà và thời gian cần để hoàn thành công việc đó. Bạn hãy viết chương trình cho biết số lượng việc nhà nhiều nhất có thể hoàn thành trong giới hạn thời gian $T$.
#### Input
- Dòng đầu tiên chứa một số nguyên $T (0 \le T \le 10^9)$ là giới hạn thời gian.
- Dòng thứ hai chứa một số nguyên $C (0 \le C \le 100)$ là số lượng việc nhà.
- $C$ dòng tiếp theo, mỗi dòng chứa một số nguyên dương cho biết thời gian cần để thực hiện xong một việc nhà trong danh sách. Giả sử thời gian tối đa để thực hiện một việc nhà là $10^9$.
#### Output
- Ghi ra một số nguyên cho biết số lượng việc nhà nhiều nhất có thể hoàn thành trong giới hạn thời gian $T$.
#### Sample Input
```
6
3
3
6
3
```
#### Sample Output
```
2
```
#### Giải thích
- Ta chọn được $2$ công việc là công việc thứ $1$ và công việc thứ $3$, tổng thời gian thực hiện là: $3+3=6\le T$.
## Bài 4: [Bedao Regular Contest 10 - Admissions](https://oj.vnoi.info/problem/bedao_r10_admissions)
#### Đề Bài
- Ở trường học Bedao nọ, hiệu trưởng **illya** có kế hoạch nâng cao thành tích môn Tin học của nhà trường nên đã quyết định mở lớp Chuyên tin dành cho những học sinh đạt kết quả cao trong kì thi đầu vào. Kì thi đầu vào ghi nhận có $N$ học sinh tham gia, học sinh thứ $i$ có số điểm môn Toán là $a_i$ và có số điểm môn Tin là $b_i$. Để đảm bảo lớp học chất lượng nhất có thể, hiệu trưởng **illya** đã các bước sàng lọc như sau:
- $A$ học sinh có số điểm Toán cao nhất sẽ được nhận vào lớp.
- Đối với các học sinh chưa được nhận vào lớp, thì $B$ học sinh có số điểm Tin cao nhất sẽ được nhận vào lớp.
- Đối với các học sinh chưa được nhận vào lớp, thì $C$ học sinh có tổng số điểm Toán và Tin cao nhất sẽ được nhận vào lớp.
- Đối với các học sinh chưa được nhận vào lớp lúc này sẽ không được nhận vào lớp nữa.
- Tuy vậy, hiệu trưởng **illya** lại rất đặc cách những bạn học sinh có số thứ tự nhỏ, cụ thể nếu hai học sinh có số điểm bằng nhau thì học sinh có số thứ tự nhỏ hơn sẽ được nhận. Là một nhân viên IT xuất sắc của nhà trường, bạn hãy giúp **illya** lập danh sách các học sinh được nhận vào lớp Chuyên tin nhé!
#### Input
- Dòng đầu tiên gồm $4$ số nguyên $N (N \le 1000)$, $A$, $B$, $C$ $(0 \le A, B, C \le N$ và $1 \le A + B + C \le N)$.
- Dòng thứ hai gồm $N$ số nguyên $a_1, a_2, ..., a_N$ lần lượt là số điểm toán của học sinh thứ $1, 2, ..., N$ $(0 \le a_i \le 100)$.
- Dòng thứ ba gồm $N$ số nguyên $b_1, b_2, ..., b_N$ lần lượt là số điểm Tin của học sinh thứ $1, 2, ..., N$ $(0 \le b_i \le 100)$.
#### Output
- Gồm danh sách các học sinh được nhận vào sắp xếp theo số thứ tự của các học sinh, mỗi dòng là một số thứ tự của một học sinh.
#### Sample Input
```
7 0 0 3
40 70 80 60 50 30 45
84 35 90 77 56 78 20
```
#### Sample Output
```
2
```
#### Giải thích
- Ở kì thi đầu vào lần này, ta sẽ lấy $C = 3$ người có tổng điểm môn Toán và Tin cao nhất, từ đó ta sẽ có danh sách tổng điểm như sau: $[124,105,170,137,106,108,65]$.
- Từ danh sách này ta sẽ chọn ra được $3$ tổng điểm cao nhất là $[124,170,137]$ tương ứng với học sinh thứ $1$, $3$, và $4$.
# Thông tin mở rộng và chia sẻ
- Thuật toán sắp xếp **lâu đời** nhất đã được phát minh ra là [Sắp xếp theo cơ số - Radix sort](https://www.geeksforgeeks.org/radix-sort/). Nó được phát minh vào năm 1887. Đến năm 1923 thì được sử dụng rộng rãi để sắp xếp thẻ đục lỗ. Thuật toán này **rất hiệu quả** khi dùng cho **số nguyên** (có thể **nhanh hơn** hàm `std::sort()` của C++). Tuy nhiên **không khuyến khích** tự cài đặt trong phòng thi gây mất thời gian và không chính xác, dễ mất điểm đáng tiếc.
- Một số thuật toán sắp xếp thông dụng được trình bày rất trực quan và dễ hiểu trên web [VisualGo](https://visualgo.net/en/sorting), phù hợp cho người mới. Những thuật toán đã giới thiệu trong bài viết này đều có trên VisualGo.
- Trong thực tế, có rất nhiều thuật toán sắp xếp khác nhau. Trong đó, bên cạnh những thuật toán mạnh mẽ, vẫn có một số [thuật toán sắp xếp rất "dị"](https://codoholicconfessions.wordpress.com/2017/05/21/strangest-sorting-algorithms/) điển hình là Bogo Sort, chỉ nên tìm hiểu cho mục đích giải trí.
- Những thuật toán sắp xếp có thể biểu diễn dưới rất nhiều hình thức khác nhau, một trong số đó là [nhạc lofi chill để học tập](https://www.youtube.com/watch?v=vr5dCRHAgb0&ab_channel=Musicombo).
# Tài liệu Tham khảo
::: info
[Geeksforgeeks - Sorting Algorithms](https://www.geeksforgeeks.org/sorting-algorithms/)
[VisualGo](https://visualgo.net/en/sorting)
[UsacoGuide - Introduction to Sorting](https://usaco.guide/bronze/intro-sorting)
[Wikipedia - Sorting algorithms](https://en.wikipedia.org/wiki/Sorting_algorithm)
:::
Google Drive
Gist
Clipboard
Sign in with Wallet
