Tìm hiểu thuật toán sắp xếp nổi bọt (Bubble Sort)

• Như vậy không còn cặp phần tử nào cần so sánh. Ta kết luận mảng đã được sắp xếp hoàn toàn với thứ tự mong muốn.

#include <stdio.h>

// Hàm xuất mảng
void printArr(int arr[], int arrLength)
{
    for (int i = 0; i < arrLength; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Hàm sắp xếp
void bubbleSort(int arr[], int arrLength)
{
    // Lặp qua mảng arr, i cũng đại diện cho số phần tử đã được đưa về vị trí đúng
    for (int i = 0; i < arrLength; i++)
    {
        // Vòng lặp for lồng để so sánh các cặp phần tử, bỏ qua i phần tử đã được sắp xếp
        for (int j = 0; j < arrLength - 1 - i; j++)
        {
            // Nếu phần tử tại vị trí j lớn hơn phần tử tại vị trí kề phải thì hoán đổi hai phần tử cho nhau
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main(int argc, char const *argv[])
{
    int arr[] = {16, 22, 20, 24, 12, 6};
    int arrLength = sizeof(arr) / sizeof(arr[0]);
    
    printf("Mang ban dau: ");
    printArr(arr, arrLength);

    bubbleSort(arr, arrLength);

    printf("Mang da duoc sap xep: ");
    printArr(arr, arrLength);

    return 0;
}

#include <iostream>

using namespace std;

// Hàm xuất mảng
void printArr(int arr[], int arrLength)
{
    for (int i = 0; i < arrLength; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Hàm sắp xếp
void bubbleSort(int arr[], int arrLength)
{
    // Lặp qua mảng arr, i cũng đại diện cho số phần tử đã được đưa về vị trí đúng
    for (int i = 0; i < arrLength; i++)
    {
        // Vòng lặp for lồng để so sánh các cặp phần tử, bỏ qua i phần tử đã được sắp xếp
        for (int j = 0; j < arrLength - 1 - i; j++)
        {
            // Nếu phần tử tại vị trí j lớn hơn phần tử tại vị trí kề phải thì hoán đổi hai phần tử cho nhau
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main(int argc, char const *argv[])
{
    int arr[] = {16, 22, 20, 24, 12, 6};
    int arrLength = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Mang ban dau: ";
    printArr(arr, arrLength);

    bubbleSort(arr, arrLength);

    cout << "Mang da duoc sap xep: ";
    printArr(arr, arrLength);

    return 0;
}

using System;

namespace Main
{
    class Program
    {
        // Phương thức xuất mảng
        static void printArr(int[] arr)
        {
            foreach (int i in arr)
            {
                Console.Write($"{i} ");
            }
            Console.WriteLine();
        }
        
        // Phương thức sắp xếp
        static void bubbleSort(int[] arr)
        {
            // Lặp qua mảng arr, i cũng đại diện cho số phần tử đã được đưa về vị trí đúng
            for (int i = 0; i < arr.Length; i++)
            {
                // Vòng lặp for lồng để so sánh các cặp phần tử, bỏ qua i phần tử đã được sắp xếp
                for (int j = 0; j < arr.Length - 1 - i; j++)
                {
                    // Nếu phần tử tại vị trí j lớn hơn phần tử tại vị trí kề phải thì hoán đổi hai phần tử cho nhau
                    if (arr[j] > arr[j + 1])
                    {
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
        }
        
        static void Main()
        {
            int[] arr = {16, 22, 20, 24, 12, 6};
            
            Console.Write("Mang ban dau: ");
            printArr(arr);
            
            bubbleSort(arr);
            
            Console.Write("Mang da duoc sap xep: ");
            printArr(arr);
        }
    }
}

import java.util.Arrays;

public class Main {
    // Phương thức sắp xếp
    public static void bubbleSort(int[] arr) {
        // Lặp qua mảng arr, i cũng đại diện cho số phần tử đã được đưa về vị trí đúng
        for (int i = 0; i < arr.length; i++) {
            // Vòng lặp for lồng để so sánh các cặp phần tử, bỏ qua i phần tử đã được sắp xếp
            for (int j = 0; j < arr.length - 1 - i; j++) {
                // Nếu phần tử tại vị trí j lớn hơn phần tử tại vị trí kề phải thì hoán đổi hai phần tử cho nhau
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {16, 22, 20, 24, 12, 6};

        System.out.println("Mang ban dau: " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("Mang da duoc sap xep: " + Arrays.toString(arr));
    }
}

# Hàm sắp xếp
def bubbleSort(lst):
    # Lặp qua danh sách lst, i cũng đại diện cho số phần tử đã được đưa về vị trí đúng
    for i in range(len(lst)):
        # Vòng lặp for lồng để so sánh các cặp phần tử, bỏ qua i phần tử đã được sắp xếp
        for j in range(len(lst) - 1 - i):
            # Nếu phần tử tại vị trí j lớn hơn phần tử tại vị trí kề phải thì hoán đổi hai phần tử cho nhau
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]

lst = [16, 22, 20, 24, 12, 6]

print(f"Danh sách ban đầu: {lst}")
bubbleSort(lst)
print(f"Danh sách đã được sắp xếp: {lst}")

// Hàm sắp xếp
function bubbleSort(arr) {
    // Lặp qua mảng arr, i cũng đại diện cho số phần tử đã được đưa về vị trí đúng
    for (let i = 0; i < arr.length; i++) {
        // Vòng lặp for lồng để so sánh các cặp phần tử, bỏ qua i phần tử đã được sắp xếp
        for (let j = 0; j < arr.length - 1 - i; j++) {
            // Nếu phần tử tại vị trí j lớn hơn phần tử tại vị trí kề phải thì hoán đổi hai phần tử cho nhau
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

let arr = [16, 22, 20, 24, 12, 6];

window.alert("Mảng ban đầu: " + arr);
bubbleSort(arr);
window.alert("Mảng đã được sắp xếp: " + arr);

• Dễ hiểu và cài đặt: Thuật toán sắp xếp nổi bọt là một thuật toán đơn giản và dễ hiểu, không đòi hỏi kiến thức toán học phức tạp. Việc cài đặt thuật toán cũng rất đơn giản và không tốn nhiều công sức.
• Ổn định: Thuật toán sắp xếp nổi bọt có tính ổn định vì nó luôn đảm bảo được thứ tự của các phần tử cùng giá trị trong danh sách cần sắp xếp
• Không yêu cầu thêm bộ nhớ phụ: Như đã phân tích độ phức tạp về bộ nhớ ở trên, thuật toán sắp xếp nổi bọt chỉ sử dụng một lượng bộ nhớ hằng số là O(1), không tạo thêm gánh nặng cho hệ thống.

Hạn chế