[toc level=2]
## Tìm kiếm tuyến tính (Linear Search)
### Ý tưởng
Tìm kiếm một phần tử $A_i$ trong mảng $A$ hoặc một giá trị $x$ nào đó để thoả mãn điều kiện cần tìm bằng cách thử từng trường hợp $x$ trong đoạn liên tiếp $[a,b]$.
### Độ phức tạp
- Trường hợp tốt nhất: $O(1)$
- Trường hợp trung bình: $O(N)$
- Trường hợp tệ nhất: $O(N)$
### Cài đặt
**Tìm kiếm phần tử trong mảng**
```cpp=
int linearSearch(int a[], int n, int x){
for(int i = 0; i < n; i++){
if(a[i] == x)
return i;
}
return -1;
}
```
**Tìm kiếm giá trị thoả mãn điều kiện**
Kiểm tra $n$ có phải số nguyên tố hay không
```cpp=
bool isPrime(int n){
if(n < 2)
return false;
for(int i = 2; i < n; i++){
if(n % i == 0)
return false;
}
return true;
}
```
## Tìm kiếm tuyến tính (cải tiến) ¯\\_(ツ)_/¯
Ờm... thì nó không hề cải tiến một chút nào cả nên là cũng không biết ghi như thế nào.
## Tìm kiếm nhị phân
### Ý tưởng
Tìm kiếm phần tử $A_i$ trong mảng $A$ có **thứ tự tuyến tính** hoặc tìm giá trị $x$ lớn nhất/nhỏ nhất nào đó trong đoạn $[a, b]$ liên tiếp sao cho các giá trị nhỏ hơn/lớn hơn $x$ cũng thoả điều kiện.
Cách tìm kiếm là chọn phần tử/giá trị trung vị, kiểm tra điều kiện với phần tử/giá trị đó. Nếu thoả điều kiện, ta sẽ giới hạn phạm vi tìm kiếm lại với một đầu là phần tử/giá trị trung vị đó và đầu còn lại. Nếu không thoả, ta sẽ giới hạn phạm vi tìm kiếm trong phần còn lại, tiếp tục tới khi phạm vị tìm kiếm chỉ còn 1 phần tử/giá trị thoả.
### Demo
### Độ phức tạp
- Trường hợp tốt nhất: $O(1)$
- Trường hợp trung bình: $O(\log{N})$
- Trường hợp tệ nhất: $O(\log{N})$
### Cài đặt
**Tìm kiếm phần tử trong mảng**
```cpp=
int binarySearch(int a[], int n, int x){
int l = 0, r = n - 1;
int ans = -1;
while(l <= r){
int mid = (l + r) / 2;
if(a[mid] <= x){
ans = mid;
l = mid + 1;
}else
r = mid - 1;
}
return ans;
}
```
**Tìm kiếm giá trị thoả mãn điều kiện**
```cpp=
int binarySearch(int n, int x){
int l = 0, r = n - 1;
int ans = -1;
while(l <= r){
int mid = (l + r) / 2;
if(mid <= x){
ans = mid;
l = mid + 1;
}else
r = mid - 1;
}
return ans;
}
```
## Sắp xếp chọn (Selection sort)
### Ý tưởng
Duyệt qua mảng, tìm phần tử nhỏ nhất chưa được sắp xếp và đưa lên vị trí đầu tiên chưa được sắp xếp.
### Demo
[VisualAlgo](https://visualgo.net/en/sorting)
### Độ phức tạp và đánh giá
- Trường hợp tốt nhất: $O(N^2)$
- Trường hợp trung bình: $O(N^2)$
- Trường hợp tệ nhất: $O(N^2)$
- Không ổn định (có thể 2 phần tử không sắp xếp theo vị trí ban đầu nếu như 2 phần tử bằng nhau)
- In-place sort (Không tạo thêm mảng phụ)
### Cài đặt
```cpp=
void selectionSort(int a[], int n){
for(int i = 0; i < n; i++){
int indexMin = std::min_element(a + i, a + n) - a;
std::swap(a[i], a[indexMin]);
}
}
```
## Sắp xếp chèn (Insertion sort)
### Ý tưởng
Với mỗi phần tử $A_i$, ta sẽ chèn nó vào đúng vị trí đã sắp xếp bằng cách dời chỗ những phần tử khác.
### Demo
[VisualAlgo](https://visualgo.net/en/sorting)
### Độ phức tạp và đánh giá
- Trường hợp tốt nhất: $O(N)$
- Trường hợp trung bình: $O(N^2)$
- Trường hợp tệ nhất: $O(N^2)$
- Ổn định
- In-place sort
### Cài đặt
```cpp=
void insertionSort(int a[], int n){
for(int i = 1;i < n; i++){
int x = a[i];
int pos = i - 1;
while(pos >= 0 && a[pos] > x){
a[pos + 1] = a[pos]; // dời chỗ
pos--;
}
a[pos + 1] = x;
}
}
```
## Sắp xếp vun đống (Heap sort)
### Ý tưởng
Ta sẽ xây dựng mảng cần sắp xếp thành cấu trúc [Heap](https://vnoi.info/wiki/translate/wcipeg/Binary-Heap.md#0-ki%E1%BA%BFn-th%E1%BB%A9c-c%E1%BA%A7n-bi%E1%BA%BFt-tr%C6%B0%E1%BB%9Bc).
Heap là một cấu trúc dữ liệu dạng cây nhị phân đầy đủ sao cho mỗi node trên cây đều lớn hơn hoặc bằng hai node con và nhỏ hơn hoặc bằng node cha.
Node gốc có giá trị lớn nhất.
Có 2 loại heap:
- Max heap (như trên).
- Min heap (ngược lại, cha nhỏ con).
Giả sử: Ta sử dụng một mảng $B$ để lưu Max heap:
- $B_0$ là node cha, có giá trị lớn nhất.
- $B_{2 \times i + 1}$ và $B_{2 \times i + 2}$ là 2 node con của $B_i$ và nhỏ hơn hoặc bằng $B_i$.
- Hoán đổi vị trí $B_0$ và phần tử cuối mảng, số phần tử của heap giảm đi 1.
- Xây dựng lại heap từ $B_0$ đến cuối mảng sau khi đã giảm phần tử.
- Lặp lại bước 3 cho đến khi heap còn 1 hoặc 0 phần tử.
Ta có cấu trúc [Priority queue](https://en.wikipedia.org/wiki/Priority_queue) trong C++ sử dụng một biến thể heap.
### Độ phức tạp và đánh giá
- Trường hợp tốt nhất: $O(N\log{N})$
- Trường hợp trung bình: $O(N\log{N})$
- Trường hợp tệ nhất: $O(N\log{N})$
- Không ổn định
- In-place sort (Nếu không dùng priority queue)
### Cài đặt
**Không dùng priority_queue**
```cpp=
//hàm xây dựng heap
void heapify(int B[], int i, int n){
int mx = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if(l < n && a[l] > a[mx])
mx = l;
if(r < n && a[r] > a[mx])
mx = r;
//nếu node cha không phải lớn nhất, xây dựng lại cây con
if(mx != i){
std::swap(a[mx], a[i]);
heapify(B, mx, n);
}
}
void heapSort(int B, int n){
for(int i = n / 2 - 1; i >= 0; i--)
heapify(B, i, n);
for(int i = n - 1; i > 0; i--){
swap(B[0], B[i]);
heapify(B, 0, i);
}
}
```
**Dùng priority_queue**
```cpp=
std::priority_queue<int> mx; //max heap
std::priority_queue<int, std::vector<int>, std::greater<int> > mn;// min heap
for(int i = 0; i < n; i++){
mn.push(a[i]);
}
while(!mn.empty()){
int x = pq.top();
pq.pop();
//làm gì với x thì tuỳ, mảng đã được sắp xếp
}
```
## Sắp xếp nhanh (Quick sort)
### Ý tưởng
- Chọn một phần tử làm `pivot`
- Chia mảng thành 2 phần: Phần nhỏ hơn `pivot` nằm bên trái `pivot` và phần lớn hơn `pivot` nằm bên phải `pivot`
- Duyệt qua mảng, tìm phần tử nàm bên trái nhưng lớn hơn `pivot` thì chuyển qua bên phải `pivot` và ngược lại.
- Tiếp tục đệ quy để sắp xếp 2 phần nhỏ hơn.
### Độ phức tạp và đánh giá
- Trường hợp tốt nhất: $O(N\log{N})$
- Trường hợp trung bình: $O(N\log{N})$
- Trường hợp tệ nhất: $O(N^2)$
- Không ổn định
- In-place sort
### Cài đặt
```cpp=
void quickSort(int a[], int left, int right){
int i = left, j = right;
int pivot = a[left + std::rand() % (right - left)]
while(i <= j){
while(a[i] < pivot)
i++;
while(a[j] > pivot)
j--;
if(i <= j){
std::swap(a[i], a[j]);
i++;
--j;
}
}
if(left < j)
quickSort(a, left, j);
if(i < right)
quickSort(a, i, right);
}
```
## Sắp xếp trộn
### Ý tưởng
Sắp xếp trộn hoạt động kiểu đệ quy:
- Đầu tiên chia dữ liệu thành 2 phần, và sắp xếp từng phần.
- Sau đó gộp 2 phần lại với nhau. Để gộp 2 phần, ta làm như sau:
- Tạo một dãy $A$ mới để chứa các phần tử đã sắp xếp.
- So sánh 2 phần tử đầu tiên của 2 phần. Phần tử nhỏ hơn ta cho vào $A$ và xóa khỏi phần tương ứng.
- Tiếp tục như vậy đến khi ta cho hết các phần tử vào dãy $A$.
### Độ phức tạp và đánh giá
- Trường hợp tốt nhất: $O(N\log{N})$
- Trường hợp trung bình: $O(N\log{N})$
- Trường hợp tệ nhất: $O(N\log{N})$
- Ổn định
- Non In-place sort (tạo thêm mảng phụ)
### Cài đặt
Nguồn: [VNOI](https://vnoi.info/wiki/algo/basic/sorting.md)
```cpp=
int a[MAXN]; // mảng trung gian cho việc sắp xếp
// Sắp xếp các phần tử có chỉ số từ left đến right của mảng data.
void mergeSort(int data[MAXN], int left, int right) {
if (data.length == 1) {
// Dãy chỉ gồm 1 phần tử, ta không cần sắp xếp.
return ;
}
int mid = (left + right) / 2;
// Sắp xếp 2 phần
mergeSort(data, left, mid);
mergeSort(data, mid+1, right);
// Trộn 2 phần đã sắp xếp lại
int i = left, j = mid + 1; // phần tử đang xét của mỗi nửa
int cur = 0; // chỉ số trên mảng a
while (i <= mid || j <= right) {
// chừng nào còn 1 phần chưa hết phần tử.
if (i > mid) {
// bên trái không còn phần tử nào
a[cur++] = data[j++];
} else if (j > right) {
// bên phải không còn phần tử nào
a[cur++] = data[i++];
} else if (data[i] < data[j]) {
// phần tử bên trái nhỏ hơn
a[cur++] = data[i++];
} else {
a[cur++] = data[j++];
}
}
// copy mảng a về mảng data
for (int i = 0; i < cur; i++)
data[left + i] = a[i];
}
```
Sign in with Wallet
Connect another wallet