Sắp xếp là một khái niệm cơ bản nhưng khá quan trọng đối với mỗi lập trình viên. Việc sắp xếp sẽ giúp chúng ta dễ dàng hơn trong việc giải quyết các vấn đề khác như tìm kiếm một phần tử, tìm phần tử lớn nhất, nhỏ nhất,… Có nhiều thuật toán sắp xếp khác nhau, mỗi thuật toán đều có đặc điểm và ưu điểm riêng của nó nhưng đều có một điểm chung là đều so sánh các phần tử rồi hoán đổi vị trí của nó qua hàm Swap như sau:
void Swap(float *x, float *y)
{ float temp;
temp=*x;
*x=*y;
*y=temp;
}
Trong bài viết này, hãy cùng Isinhvien đi tìm hiểu kĩ hơn về các thuật toán này nhé!
Tóm Tắt
Sắp xếp chọn (Selection sort)
Ý tưởng của thuật toán chọn trực tiếp mô phỏng một trong những cách sắp xếp tự nhiên nhất trong thực tế: chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu dãy hiện hành; sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử, bắt đầu từ vị trí thứ 2; lặp lại quá trình trên cho dãy hiện hành… đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.
Hàm sắp xếp chọn
void Selection_Sort(int a[], int n){
for(int i = 1; i < n; i++){
int min=i,j;
for(int j = i+1; j <= n; j++){
if(a[j]<a[min]) min=j; //tìm vị trí phần tử nhỏ nhất
}
Swap(&a[i],&a[min]); // hoán đổi a[min] với a[i]
}
}
Giả sử ta có mảng số nguyên a gồm n=6 phần tử có giá trị cụ thể là: a[1] =9 ; a[2] =8 ; a[3] =5 ; a[4]=6 ; a[5]=4 ; a[6]=7; Khi đó dữ liệu được thay đổi ở từng bước thực hiện là:
imina[1]a[2]a[3]a[4]a[5]a[6]9856471448569722458697334568974545679855456789Dữ liệu ở từng bươc thực hiện
Sắp xếp nổi bọt (Bubble sort)
Ý tưởng chính của giải thuật này là xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đúng đầu dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i . Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.
Hàm sắp xếp nổi bọt
Bubble_Sort (int a[], int n){
int i, j;
for (i=1; i < n; i++) {
for (j=n; j>=i+1; j--) {
if (a[j-1]>a[j]) Swap (&a[j-1], &a[j]);
}
}
Giả sử ta có mảng số nguyên a gồm n=6 phần tử có giá trị cụ thể là: a[1] =9, a[2] =8, a[3] =5, a[4]=6, a[5]=4, a[6]=7;
Khi đó dữ liệu được thay đổi ở từng bước thực hiện là:
ia[1]a[2]a[3]a[4]a[5]a[6]98564714985672459867345698744567985456789Dữ liệu ở từng bước thực hiện
Sắp xếp chèn (Insertion sort)
Ý tưởng chính của giải thuật sắp xếp bằng phương pháp chèn trực tiếp là tìm cách chèn phần tử a[i] vào vị trí thích hợp của đoạn đã được sắp. Cho dãy ban đầu a[1], a[2], … , a[n] .Ta có thể xem như đã có đoạn gồm một phần tử a[1] đã được sắp. Sau đó thêm a[2] vào đoạn a[1] sẽ có đoạn gồm (a[1], a[2]) được sắp thứ tự. Tiếp tục thêm a[3] vào đoạn (a[1], a[2]) để có đoạn (a[1], a[2], a[3]) được sắp thứ tự. Tiếp tục cho đến khi thêm xong a[n] vào đoạn (a[1], a[2], … , a[n-1]) sẽ có dãy a[1], a[2], … , a[n] được sắp thứ tự.
Hàm sắp xếp chèn
void Insert_Sort ( int a[], int n) {
int i,j;
for (i=2; i<=n; i++) {
j=i-1;
while ( (j >=1 ) && (a[i] < a[j]) ) {
a[j+1]=a[j]; j--;
}
a[j+1]=a[i];
}
}
Giả sử ta có mảng số nguyên a gồm n=6 phần tử có giá trị cụ thể là: a[1] =9, a[2] =8, a[3] =5, a[4]=6, a[5]=4, a[6]=7;
Khi đó dữ liệu được thay đổi ở từng bước thực hiện là:
ia[1]a[2]a[3]a[4]a[5]a[6]98564728956473589647456894754568976456789Dữ liệu ở tùng bươc thực hiện
Sắp xếp nhanh (Quick sort)
Ðể sắp xếp dãy a[1] , a[2] , … , a [n] giải thuật QuickSort dựa trên việc phân hoạch dãy ban đầu thành hai phần :
- Dãy con 1: Gồm các phần tử a[1] … a[i] có giá trị nhỏ hơn hoặc bằng x
- Dãy con 2: Gồm các phần tử a[i] … a[n] có giá trị lớn hơn hoặc bằng x
Với x là giá trị của một phần tử tùy ý trong dãy ban đầu. Sau khi thực hiện phân hoạch, dãy ban đầu đƣợc phân thành 3 phần:
- a[k] < x , với k = 1 … i
- a[k] = x , với k = i … j
- a[k] > x , với k = j … n
Trong đó dãy con thứ 2 đã có thứ tự, nếu các dãy con 1 và dãy con 3 chỉ có 1 phần tử thì dãy con đó đã có thứ tự, khi đó dãy ban đầu đã được sắp. Ngược lại, nếu các dãy con 1 và 3 có nhiều hơn 1 phần tử thì dãy ban đầu chỉ có thứ tự khi các dãy con 1, 3 được sắp xếp. Ðể sắp xếp dãy con 1 và 3, ta lần lượt tiến hành việc phân hoạch từng dãy con theo cùng phương pháp phân hoạch dãy ban đầu đã trình bày.
Hàm sắp xếp nhanh
void Quicksort(float a[], int t, int p) {
if (t < p) {
int i=t,j=p;
float chot = a[(t+p)/2]; //chọn phần tử ở giữa làm chốt
while(i<j){
while(a[i]<chot) i++;
while(a[j]>chot) j--;
if (i <= j) {
hoan_vi(&a[i], &a[j]);
i++ ;
j--;
}
}
Quicksort(a,t,j);
Quicksort(a,i,p);
}
}
Đây là một giải thuật khá nhanh, tiết kiệm thời gian chạy chương trình hơn các giải thuật trên khá nhiều. Tuy nhiên, nếu rơi vào trường hợp xấu nhất thì thời gian chạy sẽ tăng lên rất nhiều.
Trường hợpĐộ phức tạpTốt nhất
n*log_2(n)
Xấu nhất
n^2
Độ phức tạp của thuạt toán Quicksort
Trên đây là tất tần tật về 4 thuật toán sắp xếp trong C/C++ mà Isinhvien muốn chia sẻ với các bạn. Nếu các bạn thầy bài viết này của Isinhvien hay và bổ ích thì hãy chia sẽ nó cho bạn bè và đừng quên theo dõi Isinhvien ỗi ngày để có thêm nhiều kiến thức hay mỗi ngày nhé! Chúc các bạn thành công!
