Ý tưởng: Liên tục hoán đổi các phần tử liền kề nhau nếu chúng sai thứ tự cho đến khi dãy được sắp xếp.
- Ví dụ minh họa
- Mã code:
void swap[int *a,int *b]{
int temp=*a;
*a=*b;
*b=temp;
}
void bubblesort[int arr[],int n]{
for[int i=0; i [3 5 2 7] , so sánh 5 và 3 thấy 3 nhỏ hơn 5 -> đổi chỗ 3 và 5.
[3 5 2 7] -> [3 2 5 7] , so sánh 5 và 2 thấy 2 nhỏ hơn 5 -> đổi chỗ 2 và 5.
[ 3 2 5 7] -> [3 2 5 7], 5 < 7 đúng -> không có gì thay đổi
-> kết thúc vòng lặp 1 ta được [3 2 5 7]
vòng lặp 2:
[3 2 5 7] ->[2 3 5 7] , so sánh 3 và 2 thấy 2 nhỏ hơn 3 -> đổi chỗ 2 và 3.
[2 3 5 7] ->[2 3 5 7]], 3 < 5 đúng -> không có gì thay đổi.
[2 3 5 7] -> [2 3 5 7] , 5 < 7 đúng -> không có gì thay đổi.
Đến đây ta thu được dãy đã sắp xếp nhưng thuật toán chưa dừng ở đó mà nó tiếp tục lặp.
vòng lặp 3:
[2 3 5 7] -> [2 3 5 7]
[2 3 5 7] -> [2 3 5 7]
[2 3 5 7] -> [2 3 5 7]Độ phức tạp thuật toán:
Trường hợp tốt nhất: O[n]
Trường hợp xấu nhất: O[n*n]
2. Thuật toán sắp xếp chọn [Selection Sort]
- Ý tưởng: Chọn phần từ nhỏ nhất [hoặc lớn nhất] trong dãy gồm n phần từ, đưa phần từ này về vị trí đầu tiên của dãy và không quan tâm đến phần tử này nữa. Tiếp tục tìm phần tử nhỏ nhất[hoặc lớn nhất] từ vị trí thứ 2 đến vị trí thứ n trong dãy n-1, đưa phần từ này về vị trí thứ 2. Lặp lại cho đến khi dẫy chỉ còn 1 phần tử.
- Ví dụ minh họa
- Mã code:
void swap[int *a,int *b]{
int temp=*a;
*a=*b;
*b=temp;
}
void selectionsort[int arr[],int n]{
int min_idx;
for[int i=0; i [2 3 7 5], tìm được 3 là số nhỏ nhất trong dãy từ 2-n ta đổi chỗ 3 cho 7
-> kết thúc vòng lặp 2 ta được [2 3 7 5]
Vòng lặp 3:
[2 3 7 5] -> [2 3 5 7], tìm được 5 là số nhỏ nhất trong dãy từ 3-n ta đổi chỗ 5 cho 7
-> kết thúc vòng lặp 3 ta được [2 3 5 7]
Vòng lặp 3 cũng là vòng lặp cuối cùng vì dãy chỉ còn 1 phần tử thì n chắc chắn là lớn nhất, vậy ta đã thu được một dãy tăng dần với thuật toán sắp xếp chọn.Độ phức tạp thuật toán:
Trường hợp tốt nhất: O[n*n]
Trường hợp xấu nhất: O[n*n]
3. Thuật toán sắp xếp nhanh [Quick Sort]
- Ý tưởng: Quick sort là một thuật toán chia để trị nó chọn một phần tử trong mảng để làm điểm đánh dấu. Thuật toán sẽ thực hiện chia mảng thành các mảng con theo điểm mà mình đã chọn. Có nhiều cách chọn điểm khác nhau:
` - Luôn chọn phần tử đầu tiên
- Luôn chọn phần tử cuối cùng
- Chọn phần tử ngẫu nhiên
- Chọn phần tử ở giữa
`
- Ví dụ minh họa
- Mã code:
void swap[int *a,int *b]{
int temp=*a;
*a=*b;
*b=temp;
}
int partition[int arr[],int l,int h]{
int x=arr[h];
int i=l-1;
for[int j=l; j 70 => biến i và mảng không đổi
j = 4: arr[j] [40]