---
# System prepended metadata

title: Sắp xếp và Tìm kiếm

---

# Sắp xếp và Tìm kiếm
## Sắp xếp
### Sắp xếp nổi bọt
Sau mỗi một lần lặp, phần tử lớn nhất sẽ ở vị trí đúng. Cứ tiếp tục như vậy, ta sẽ có một mảng đã được sắp xếp.
```cpp 
for (int i=0;i<n;i++){
    for (int j=0; j<n-1;j++){
        if (a[j]>a[j+1]){
            swap(a[j],a[j+1]);
        }
    }
}
```
Độ phức tạp: $O(N^2)$
## Tìm kiếm
### Tìm kiếm tuần tự
Duyệt qua tất cả các phần tử.
```cpp 
for (int i=0;i<n;i++){
    if (a[i]==k){
        return true;
    }
}
```
Độ phức tạp: $O(N)$.
### Tìm kiếm nhị phân
Sử dụng trên dãy đã được sắp xếp. Lần lượt chia nhỏ mảng để tìm kiếm.
```cpp    
int l=0,r=n-1;
while (l<=r){
    int mid=(l+r)/2;
    if (mid==k){
        return true;
    }
    if (a[mid]>k){
        r=mid-1;
    }
    else{
        l=mid+1;
    }
}
```
Độ phức tạp: $O(log N)$.