Thuật toán sắp xếp chèn (Insertion Sort) trong C / C++

Trong bài viết này, codehow sẽ giới thiệu đến các bạn thuật toán sắp xếp chèn (Insertion Sort) trong C / C++. Về cơ bản thì thuật toán này sắp xếp nhanh hơn và tối ưu hơn thuật toán sắp xếp nổi bọt (Bubble Sort).

Mình sẽ giải thích khái niệm sắp xếp chèn là gì? Cách nó hoạt động ra sao? Sau đó sẽ đưa ra giải thuật kèm theo ví dụ cụ thể để các bạn tham khảo nhé.

Sắp xếp chèn là gì? Hoạt động như thế nào

Nói một cách dễ hiểu, thuật toán sẽ duyệt từng phần tử trong mảng, sau đó so sánh và chèn vào mảng còn sao cho đúng thứ tự.

Như các bạn thấy ở hình trên, đầu tiên nó so sánh cặp 4 và 3, bởi vì 3 nhỏ hơn 4 nên nó chèn vào trước số 4. Tiếp tục cặp 4 và 2, vì 2 nhỏ hơn 4 và 3 nên nó chèn vào trước 3, cứ như vậy cho đến khi hết mảng.

Về cơ bản thì nó sẽ nhanh hơn thuật toán sắp xếp nổi bọt, tuy nhiên vẫn chưa được tối ưu vì phải duyệt hết tất cả các phần tử trong mảng.

Nếu các bạn mới bắt đầu học lập trình thì nên tìm hiểu qua thuật toán này, bởi nó cơ bản và độ phức tạp không cao. Các bạn có thể tìm hiểu thêm các thuật toán sắp xếp khác tối ưu hơn ở các bài viết sau của mình nhé.

Thuật toán sắp xếp chèn (Insertion Sort) trong C / C++

Đối với thuật toán sắp xếp chèn (Insertion Sort) trong C / C++, chúng ta không cần sử dụng hàm Swap() để hoán đổi vị trí giữa hai phần tử. Hãy xem thuật toán sắp xếp chèn dưới đây, sau đó mình sẽ giải thích ngay bên dưới nhé.

void insertionSort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i-1;
  
       /* Di chuyển các phần tử có giá trị lớn hơn giá trị 
       key về sau một vị trí so với vị trí ban đầu
       của nó */
       while (j >= 0 && arr[j] > key)
       {
           arr[j+1] = arr[j];
           j = j-1;
       }
       arr[j+1] = key;
   }
}

Giải thích thuật toán:

1. Đầu tiên chúng ta sẽ kiểm tra phần tử đầu tiên đã sắp xếp hay chưa, nếu rồi thì trả về 1.
2. Lấy phần tử tiếp theo để so sánh với các phần tử trong mảng con đã sắp xếp.
3. Di chuyển các phần tử trong mảng con nếu nó lớn hơn giá trị đó.
4. Sau khi di chuyển thì chèn phần tử đó vào đúng vị trí.
5. Tiếp tục lặp lại cho đến hết mảng.

Bây giờ mình sẽ thực hiện một ví dụ sử dụng thuật toán sắp xếp chèn (Insertion Sort) trong C / C++.

Đề bài: Viết chương trình sắp xếp các phần tử trong mảng được nhập bởi người dùng. Số lương phần tử trong mảng không được nhỏ hơn 0, nếu nhỏ hơn thì yêu cầu nhập lại. Sử dụng thuật toán sắp xếp chèn để sắp xếp các phần tử.

Gợi ý:

• Đầu tiên chúng ta sẽ viết hàm insertionSort() để sắp xếp các phần tử với mảng truyền vào.
• Tạo hàm printArray() để xuất các phần tử trong mảng được truyền vào.
• Sau đó yêu cầu người dùng nhập vào các phần tử trong mảng, rồi gọi hàm insertionSort() để sắp xếp.
• Cuối cùng gọi hàm printArray() để xuất các phần tử trong mảng sau khi sắp xếp.

Dưới đây là hai chương trình mình đã viết bằng ngôn ngữ C và C++, các bạn có thể tham khảo nhé.

Chương trình C:

#include <stdio.h>
#include <stdbool.h>

void insertionSort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i-1;
  
       /* Di chuyển các phần tử có giá trị lớn hơn giá trị 
       key về sau một vị trí so với vị trí ban đầu
       của nó */
       while (j >= 0 && arr[j] > key)
       {
           arr[j+1] = arr[j];
           j = j-1;
       }
       arr[j+1] = key;
   }
}

void printArr(int arr[], int N)
{
   int i;
   for (i = 0; i < N; i++)
   {
       printf("%d\t", arr[i]);
   }
}

int main(void) {
  int n;
    do{
        printf("\nNhập vào số lượng phần tử có trong mảng: ");
        scanf("%d", &n);
    }while(n <= 0);
     
    int a[n];
     
    for(int i = 0;i < n;i++){
        printf("a[%d] = ",i);
       scanf("%d",&a[i]);
    };
 
    insertionSort(a, n);
 
    printf("Mảng sau khi được sắp xếp: \n");
    printArr(a, n);
 
    printf("\n---------------------------------------\n");
    printf("Chương trình này được đăng tại codehow.net");
}

Kết quả:

Chương trình C++:

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i-1;
  
       /* Di chuyển các phần tử có giá trị lớn hơn giá trị 
       key về sau một vị trí so với vị trí ban đầu
       của nó */
       while (j >= 0 && arr[j] > key)
       {
           arr[j+1] = arr[j];
           j = j-1;
       }
       arr[j+1] = key;
   }
}

void printArr(int arr[], int N)
{
   int i;
   for (i = 0; i < N; i++)
   {
       cout<<arr[i]<<"\t";
   }
}

int main(void) {
  int n;
    do{
        cout<<"\nNhập vào số lượng phần tử có trong mảng: ";
        cin>>n;
    }while(n <= 0);
     
    int a[n];
     
    for(int i = 0;i < n;i++){
        cout<<"a["<<i<<"] = ";
       cin>>a[i];
    };
 
    insertionSort(a, n);
 
    cout<<"Mảng sau khi được sắp xếp: \n";
    printArr(a, n);
 
    cout<<"\n---------------------------------------\n";
    cout<<"Chương trình này được đăng tại codehow.net";
}

Kết quả:

Như vậy là chúng ta đã cùng nhau tìm hiểu về thuật toán sắp xếp chèn (Insertion Sort) trong C / C++. Ở bài tiếp theo mình sẽ giới thiệu đến các bạn thuật toán sắp xếp chọn (Selection Sort) trong C / C++, các bạn chú ý theo dõi nhé !!!