Tổng hợp các thuật toán sắp xếp trong C/C++

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 tìm hiểu kĩ hơn về các thuật toán này nhé!

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à:

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à:

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à:

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.

Nguồn: isinhvien.com