HomeLập trìnhPythonSắp xếp bong...

Sắp xếp bong bóng – Thuật toán trong Java, C++, Python với mã ví dụ


Sắp xếp bong bóng là một loại thuật toán sắp xếp mà bạn có thể sử dụng để sắp xếp một tập hợp các giá trị theo thứ tự tăng dần. Nếu muốn, bạn cũng có thể triển khai sắp xếp bong bóng để sắp xếp các giá trị theo thứ tự giảm dần.

Một ví dụ thực tế về thuật toán sắp xếp bong bóng là cách danh sách liên hệ trên điện thoại của bạn được sắp xếp theo thứ tự bảng chữ cái. Hoặc việc sắp xếp các tệp trên điện thoại của bạn theo thời gian chúng được thêm vào.

Trong bài viết này, tôi sẽ giải thích tất cả những gì bạn cần biết về thuật toán sắp xếp bong bóng bằng một số đồ họa thông tin mà tôi đã chuẩn bị. Sau đó, tôi sẽ chỉ cho bạn mã ví dụ về thuật toán sắp xếp bong bóng trong Python, Java và C++.

Mục lục

Cách thuật toán sắp xếp bong bóng hoạt động

Để triển khai thuật toán sắp xếp bong bóng, các nhà phát triển thường viết một hàm, sau đó viết một vòng lặp trong một vòng lặp – vòng lặp bên trong và vòng lặp bên ngoài. Bạn sẽ thấy nó hoạt động khi tôi chỉ cho bạn mã bằng Python, C++ và Java.

Giả sử chúng ta muốn sắp xếp một dãy số 5, 3, 4, 1 và 2 sao cho chúng được sắp xếp theo thứ tự tăng dần…

Việc sắp xếp bắt đầu lần lặp đầu tiên bằng cách so sánh hai giá trị đầu tiên. Nếu giá trị đầu tiên lớn hơn giá trị thứ hai, thuật toán sẽ đẩy giá trị đầu tiên vào chỉ mục của giá trị thứ hai.

Lần lặp đầu tiên của Sắp xếp

Bước 1: Trong trường hợp 5, 3, 4, 1 và 2, 5 lớn hơn 3. Vì vậy, 5 chiếm vị trí của 3 và các số trở thành 3, 5, 4, 1 và 2.

bong bóng1

Bước 2: Thuật toán hiện có 3, 5, 4, 1 và 2 để so sánh, lần này, nó so sánh hai giá trị tiếp theo là 5 và 4. 5 lớn hơn 4, vì vậy 5 lấy chỉ số của 4 và các giá trị bây giờ trở thành 3, 4, 5, 1 và 2.

Đọc thêm  Từ điển Python – Cách thực hiện các thao tác CRUD trên dicts trong Python

bong bóng2

Bước 3: Thuật toán hiện có 3, 4, 5, 1 và 2 để so sánh. Nó so sánh hai giá trị tiếp theo là 5 và 1. 5 lớn hơn 1, vì vậy 5 lấy chỉ số của 1 và các số trở thành 3, 4, 1, 5 và 2.

bong bóng3

Bước 4: Thuật toán hiện có 3, 4, 1, 5 và 2 để so sánh. Nó so sánh hai giá trị tiếp theo là 5 và 2. 5 lớn hơn 2, vì vậy 5 lấy chỉ số của 2 và các số trở thành 3, 4, 1, 2 và 5.

bong bóng4

Đó là lần lặp đầu tiên. Và các số hiện được sắp xếp thành 3, 4, 1, 2 và 5 – từ 5, 3, 4, 1 và 2 ban đầu. Như bạn có thể nhận ra, 5 sẽ là số cuối cùng nếu các số được sắp xếp tăng dần trật tự. Điều này có nghĩa là lần lặp đầu tiên đã thực sự hoàn thành.

Lần lặp lại thứ hai của Sắp xếp và phần còn lại

Thuật toán bắt đầu lần lặp thứ hai với kết quả cuối cùng là 3, 4, 1, 2 và 5. Lần này, 3 nhỏ hơn 4 nên không xảy ra hoán đổi. Điều này có nghĩa là các con số sẽ vẫn giữ nguyên.

bong bóngb1

Thuật toán tiến hành so sánh 4 và 1. 4 lớn hơn 1, vì vậy 4 được đổi chỗ cho 1 và các số trở thành 3, 1, 4, 2 và 5.

bong bóngb2

Bây giờ thuật toán tiến hành so sánh 4 và 2. 4 lớn hơn 2, vì vậy 4 được đổi chỗ cho 2 và các số trở thành 3, 1, 2, 4 và 5.

bong bóngb4

4 hiện ở đúng vị trí, vì vậy không xảy ra hoán đổi giữa 4 và 5 vì 4 nhỏ hơn 5.

bong bóngb5

Đó là cách thuật toán tiếp tục so sánh các số cho đến khi chúng được sắp xếp theo thứ tự tăng dần là 1, 2, 3, 4 và 5.

bong bóngbFinal

Mã Python Ví dụ về thuật toán sắp xếp bong bóng

Đây là một ví dụ mã cho thấy việc triển khai thuật toán sắp xếp bong bóng trong Python:

def bubble_sort(arr):
    arr_len = len(arr)
    for i in range(arr_len-1):
        flag = 0
        for j in range(0, arr_len-i-1):
            if arr[j] > arr[j+1]:
                arr[j+1], arr[j] = arr[j], arr[j+1]
                flag = 1
                if flag == 0:
                    break
    return arr

arr = [5, 3, 4, 1, 2]
print("List sorted with bubble sort in ascending order: ", bubble_sort(arr))

# Output: List sorted with bubble sort in ascending order:  [1, 2, 3, 4, 5]

Để sắp xếp xuất hiện theo thứ tự giảm dần, chỉ cần thay thế ký hiệu lớn hơn (>) bằng ký hiệu nhỏ hơn (<):

def bubble_sort(arr):
    arr_len = len(arr)
    for i in range(arr_len-1):
        flag = 0
        for j in range(0, arr_len-i-1):
            if arr[j] < arr[j+1]:
                arr[j+1], arr[j] = arr[j], arr[j+1]
                flag = 1
                if flag == 0:
                    break
    return arr

arr = [5, 3, 4, 1, 2]
print("List sorted with bubble sort in descending order: ", bubble_sort(arr))

# Output: List sorted with bubble sort in descending order:  [5, 4, 3, 2, 1]

Đây là phiên bản mã mà tôi đã thêm nhận xét để bạn có thể biết chuyện gì đang xảy ra:

# Define a function to create the sorting and pass in an array as the parameter
def bubble_sort(arr):
    # Get the length of the array
    arr_len = len(arr)
    # Loop through the array to access the elements in it, including the last one - outer loop
    for i in range(arr_len-1):
        # declare a flag variable to check if a swap has occured - for optimization
        flag = 0
        # create a loop to compare each element of the array till the last one
        for j in range(0, arr_len-i-1):
            # compare 2 adjacent elements and sort them in ascending order
            if arr[j] > arr[j+1]:
                # Swap the elements if they are not in the right order
                arr[j+1], arr[j] = arr[j], arr[j+1]
                flag = 1
                # break out of the loop at 0
                if flag == 0:
                    break
    # return value must be in the outer loop block
    return arr

arr = [5, 3, 4, 1, 2]
print("List sorted with bubble sort in ascending order: ", bubble_sort(arr))

# Output: List sorted with bubble sort in ascending order:  [1, 2, 3, 4, 5]

Ví dụ mã Java về thuật toán sắp xếp bong bóng

Để triển khai thuật toán sắp xếp bong bóng trong Java, bạn phải viết nhiều mã hơn so với Python.

Đọc thêm  Hàm any() và all() của Python – Được giải thích bằng các ví dụ

Đó là lý do tại sao tôi đã thêm nhận xét để cho bạn biết về các bước khi chúng được thực hiện:

import java.util.Arrays;

class Main {
  static void bubbleSort(int array[]) {
    int size = array.length;
    // loop over each element of the array to access them
    for (int i = 0; i < size - 1; i++)
      // compare the elements of the array with a loop
      for (int j = 0; j < size - i - 1; j++)
        // compare two adjacent elements in the array
        if (array[j] > array[j + 1]) {
          // Swap if the elements aren't in the right order
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
  }

  public static void main(String args[]) {
    int[] data = { 5, 3, 4, 1, 2 };
    // call the method using class name
    Main.bubbleSort(data);
    
    System.out.println("Array sorted with bubble sort: ");
    System.out.println(Arrays.toString(data));
  }
}

// Output: Array sorted with bubble sort: [1, 2, 3, 4, 5]

Mã C++ Ví dụ về thuật toán sắp xếp bong bóng

Giống như tôi đã làm với Java, tôi cũng đã thêm nhận xét vào việc triển khai thuật toán sắp xếp bong bóng trong C++ vì nó dài dòng hơn so với Python và Java:

#include <iostream>

using namespace std;

// create a function to execute bubble sort
void bubble_sort(int array[], int size) {
  // loop over each element of the array to access them - outer loop
  for (int step = 0; step < (size-1); ++step) {
    // check if swapping occurs
    int swapped = 0;
    // loop over each element of the array to compare them - inner loop
    for (int i = 0; i < (size-step-1); ++i) {
     // compare 2 adjacent elements and sort them in ascending order
      if (array[i] > array[i + 1]) {

        //Swap the elements if they are not in the right order
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
        
        swapped = 1;
      }
    }

    // break out of the loop if no swapping occurs anymore
    if (swapped == 0)
      break;
  }
}

// print an array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    cout << "  " << array[i];
  }
  cout << "\n";
}

int main() {
  int data[] = {5, 3, 4, 1, 2};
  // find the length of the array
  int size = sizeof(data) / sizeof(data[0]);

  // call the function   
  bubble_sort(data, size);
  
  cout << "Array sorted with bubble sort: \n";
  printArray(data, size);
}

// Output: Array sorted with bubble sort: 1  2  3  4  5

Suy nghĩ cuối cùng

Tôi sẽ không nói việc triển khai thuật toán sắp xếp bong bóng là đơn giản hay khó khăn. Đối với một lập trình viên có kinh nghiệm, điều đó không khó, nhưng đối với người mới bắt đầu, nó có thể đáng sợ lúc đầu.

Đọc thêm  Cách học Python một cách dễ dàng (và không phải theo cách tôi đã làm)

Tuy nhiên, để thực sự hiểu cách thức hoạt động của thuật toán, bạn cần biết rằng:

  • bạn cần viết một hàm để truyền dữ liệu [or array] vào trong
  • bạn cần viết một vòng lặp bên ngoài để truy cập các phần tử
  • bạn cần viết một vòng lặp bên trong để so sánh các phần tử
  • bạn cần gọi hàm và truyền vào dữ liệu (mảng)

Tôi hy vọng bài viết này giúp bạn hiểu thuật toán sắp xếp bong bóng và cách thực hiện nó.

Cảm ơn bạn đã đọc.



Zik.vn – Biên dịch & Biên soạn Lại

spot_img

Create a website from scratch

Just drag and drop elements in a page to get started with Newspaper Theme.

Buy Now ⟶

Bài viết liên quang

DMCA.com Protection Status