LATEST

Thuật toán sắp xếp nổi bọt (Bubble Sort) trong C / C++

Trong bài viết này, codehow sẽ giới thiệu các bạn thuật toán sắp xếp nổi bọt (Bubble Sort) trong C / C++. Thuật toán này sắp xếp dựa trên việc so sánh các cặp phần tử, vậy nên rất dễ hiểu và dễ sử dụng cho các lập trình viên mới học.

Trước khi đi vào tìm hiểu thuật toán, các bạn cùng mình tìm hiểu xem sắp xếp nổi bọt là gì và nó hoạt động ra sao đã nhé.

Sắp xếp nổi bọt (Bubble Sort) là gì? Nó hoạt động như thế nào?

Thuật toán sắp xếp nổi bọt (Bubble Sort) thực hiện so sánh các cặp phần tử liền kề nhau sau đó tráo đổi vị trí của chúng cho đúng thứ tự.

Ví dụ: Chúng ta có mảng Number = {2, 6, 5, 8, 10}, nếu chúng ta muốn sắp xếp tăng dần, thuật toán sắp xếp nổi bọt sẽ hoạt động như sau.

  • Đầu tiên, thuật toán so sánh cặp phần tử 2 và 6, khi này thứ tự của nó đã đúng nên sẽ giữ nguyên và chuyển đến cặp tiếp theo.
  • Cặp tiếp theo là 6 và 5, khi này thứ tự nó chưa đúng, nên thực hiện hoán đổi hai vị trí thành 5 và 6.
  • Cứ tiếp tục như vậy ta sẽ được mảng tăng dần.

Kết quả: Number = {2, 5, 6, 8, 10}.

Thuật toán này khá dễ hiểu đúng không ạ, tuy nhiên nó chỉ nên sử dụng trong các tập dữ liệu nhỏ. Đối với các tập dữ liệu lớn chúng ta nên sử dụng phương pháp khác để thực hiện.

Thuật toán sắp xếp nổi bọt (Bubble Sort) trong C / C++

Để có thể sử dụng được thuật toán sắp xếp nổi bọt trong C / C++, ta cần có hàm Swap() dùng để hoán đổi hai vị trí. Hàm này nhận vào hai số bất kì, sau đó hoán đổi hai vị trí đó.

void swap(int &x, int &y)
{
    int temp = x;
    x = y;
    y = temp;
}

Bây giờ hãy cùng xem thuật toán sắp xếp nổi bọt (Bubble Sort) trong C / C++, sau đó mình sẽ giải thích thuật toán ngay bên dưới nhé.

void bubbleSort(int arr[], int n)
{
    int i, j;
    bool haveSwap = false;
    for (i = 0; i < n-1; i++){
    // i phần tử cuối cùng đã được sắp xếp
        haveSwap = false;
        for (j = 0; j < n-i-1; j++){
            if (arr[j] > arr[j+1]){
                swap(arr[j], arr[j+1]);
                haveSwap = true; // Kiểm tra lần lặp này có swap không
            }
        }
        // Nếu không có swap nào được thực hiện => mảng đã sắp xếp. Không cần lặp thêm
        if(haveSwap == false){
            break;
        }
    }
}

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

  • Sử dụng vòng lặp for để lặp qua từng phần tử trong mảng, thực hiện so sánh từng cặp phần tử.
  • Nếu phần tử sau nhỏ hơn phần tử trước, thực hiện gọi hàm Swap() để hoán đổi hai vị trí đó.
  • Nếu hai phần tử đã đúng vị trí, ta bỏ qua rồi tiếp tục vòng lặp tiếp theo.

Bây giờ mình sẽ thực hiện chương trình sắp xếp các phần tử trong mảng sử dụng thuật toán sắp xếp nổi bọt (Bubble Sort) trong C / C++. Chương trình được viết bằng hai ngôn ngữ khác nhau là 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 swap(int* a, int* b)
{
   int temp;
   temp = *a;
   *a = *b;
   *b = temp;
}

void BubbleSort(int arr[], int N)
{
   int i, j;
   for (i = 0; i < N; i++)
   {
       for (j = N-1; j > i; j--)
       {
           if(arr[j] < arr[j-1])
               swap(&arr[j], &arr[j-1]);
       }
   }
}

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]);
    };
 
    BubbleSort(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ả:

bai11 01 PNG

Chương trình C++:

#include <iostream>
using namespace std;

void swap(int* a, int* b)
{
   int temp;
   temp = *a;
   *a = *b;
   *b = temp;
}

void BubbleSort(int arr[], int N)
{
   int i, j;
   for (i = 0; i < N; i++)
   {
       for (j = N-1; j > i; j--)
       {
           if(arr[j] < arr[j-1])
               swap(&arr[j], &arr[j-1]);
       }
   }
}

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];
    };
 
    BubbleSort(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ả:

bai11 02 PNG

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

Cùng chuyên mục:

Xóa node khỏi cây nhị phân tìm kiếm

Xóa node khỏi cây nhị phân tìm kiếm

Tìm node Max và Min trong cây nhị phân tìm kiếm

Tìm node Max và Min trong cây nhị phân tìm kiếm

Xuất node con và node lá trong cây nhị phân tìm kiếm

Xuất node con và node lá trong cây nhị phân tìm kiếm

Tìm kiếm trên cây nhị phân tìm kiếm

Tìm kiếm trên cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Thêm node vào cây nhị phân tìm kiếm

Thêm node vào cây nhị phân tìm kiếm

Cây nhị phân (Binary tree) là gì? Cơ chế hoạt động của nó

Cây nhị phân (Binary tree) là gì? Cơ chế hoạt động của nó

Cách gộp hai danh sách liên kết đôi

Cách gộp hai danh sách liên kết đôi

Tìm kiếm phần tử trong DSLK đôi

Tìm kiếm phần tử trong DSLK đôi

Xóa node trong DSLK đôi

Xóa node trong DSLK đôi

Chèn node (Insert node) vào DSLK đôi

Chèn node (Insert node) vào DSLK đôi

Duyệt danh sách liên kết đôi

Duyệt danh sách liên kết đôi

Tạo node mới trong DSLK đôi

Tạo node mới trong DSLK đôi

DSLK đôi là gì? Cấu trúc dữ liệu của DSLK đôi

DSLK đôi là gì? Cấu trúc dữ liệu của DSLK đôi

Quản lý sinh viên bằng DSLK đơn

Quản lý sinh viên bằng DSLK đơn

Tìm kiếm và sắp xếp trong DSLK đơn

Tìm kiếm và sắp xếp trong DSLK đơn

Xóa node (Delete node) trong DSLK đơn

Xóa node (Delete node) trong DSLK đơn

Chèn node (Insert node) vào DSLK đơn

Chèn node (Insert node) vào DSLK đơn

Tạo node mới trong DSLK đơn

Tạo node mới trong DSLK đơn

Cấu trúc dữ liệu của DSLK đơn

Cấu trúc dữ liệu của DSLK đơn

Top