🔥CHỌN LỌC TOP NHỮNG KHOÁ HỌC LẬP TRÌNH ONLINE NHIỀU NGƯỜI THEO HOC TẠI ĐÂY🔥

Chào ace, bài này chúng ta sẽ tìm hiểu về một trong các thuật toán sắp xếp được sử dụng nhiều trong lập trình và thực tế nhất đó là Bucket Sort, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, ứng dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về Bucket Sort thông qua các phần sau.

1. Giới thiệu

Sắp xếp nhóm(Bucket sort) chủ yếu hữu ích khi đầu vào được phân phối đồng đều trên một phạm vi. Ví dụ, hãy xem xét vấn đề sau đây.

Sắp xếp một tập hợp lớn các số dấu phẩy động nằm trong khoảng từ 0,0 đến 1,0 và được phân phối đồng đều trên phạm vi. Làm thế nào để chúng tôi sắp xếp các con số một cách hiệu quả?

Một cách đơn giản là áp dụng thuật toán sắp xếp dựa trên so sánh. Giới hạn dưới cho thuật toán sắp xếp dựa trên so sánh (Sắp xếp hợp nhất, Sắp xếp theo đống, Sắp xếp nhanh, v.v.) là Ω (n Log n), tức là chúng không thể làm tốt hơn nLogn.

Chúng ta có thể sắp xếp mảng theo thời gian tuyến tính không? Sắp xếp đếm không thể được áp dụng ở đây vì chúng tôi sử dụng các khóa làm chỉ mục trong sắp xếp đếm. Các phím ở đây là số dấu phẩy động.

Ý tưởng là sử dụng phân loại theo nhóm. 

Sau đây là thuật toán nhóm.

bucketSort (arr [], n)

1) Tạo n nhóm trống (Hoặc danh sách).

2) Thực hiện theo sau cho mọi phần tử mảng arr [i].

……. a) Chèn arr [i] vào bucket [n * array [i]]

3) Sắp xếp các nhóm riêng lẻ bằng cách sử dụng sắp xếp chèn.

4) Ghép tất cả các thùng đã phân loại.

2. Code ví dụ với nhiều ngôn ngữ

C/C++


// C++ program to sort an array using bucket sort 
#include <algorithm> 
#include <iostream> 
#include <vector> 
using namespace std; 
  
// Function to sort arr[] of size n using bucket sort 
void bucketSort(float arr[], int n) 
{ 
    // 1) Create n empty buckets 
    vector<float> b[n]; 
  
    // 2) Put array elements in different buckets 
    for (int i = 0; i < n; i++) { 
        int bi = n * arr[i]; // Index in bucket 
        b[bi].push_back(arr[i]); 
    } 
  
    // 3) Sort individual buckets 
    for (int i = 0; i < n; i++) 
        sort(b[i].begin(), b[i].end()); 
  
    // 4) Concatenate all buckets into arr[] 
    int index = 0; 
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < b[i].size(); j++) 
            arr[index++] = b[i][j]; 
} 
  
/* Driver program to test above function */
int main() 
{ 
    float arr[] = { 0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    bucketSort(arr, n); 
  
    cout << "Sorted array is \n"; 
    for (int i = 0; i < n; i++) 
        cout << arr[i] << " "; 
    return 0; 
}

Java

// Java program to sort an array 
// using bucket sort 
import java.util.*; 
import java.util.Collections; 
  
class GFG { 
  
    // Function to sort arr[] of size n 
    // using bucket sort 
    static void bucketSort(float arr[], int n) 
    { 
        if (n <= 0) 
            return; 
  
        // 1) Create n empty buckets 
        @SuppressWarnings("unchecked") 
        Vector<Float>[] buckets = new Vector[n]; 
  
        for (int i = 0; i < n; i++) { 
            buckets[i] = new Vector<Float>(); 
        } 
  
        // 2) Put array elements in different buckets 
        for (int i = 0; i < n; i++) { 
            float idx = arr[i] * n; 
            buckets[(int)idx].add(arr[i]); 
        } 
  
        // 3) Sort individual buckets 
        for (int i = 0; i < n; i++) { 
            Collections.sort(buckets[i]); 
        } 
  
        // 4) Concatenate all buckets into arr[] 
        int index = 0; 
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < buckets[i].size(); j++) { 
                arr[index++] = buckets[i].get(j); 
            } 
        } 
    } 
  
    // Driver code 
    public static void main(String args[]) 
    { 
        float arr[] = { (float)0.897, (float)0.565, 
                        (float)0.656, (float)0.1234, 
                        (float)0.665, (float)0.3434 }; 
  
        int n = arr.length; 
        bucketSort(arr, n); 
  
        System.out.println("Sorted array is "); 
        for (float el : arr) { 
            System.out.print(el + " "); 
        } 
    } 
}

Python

# Python3 program to sort an array  
# using bucket sort  
def insertionSort(b): 
    for i in range(1, len(b)): 
        up = b[i] 
        j = i - 1
        while j >= 0 and b[j] > up:  
            b[j + 1] = b[j] 
            j -= 1
        b[j + 1] = up      
    return b      
              
def bucketSort(x): 
    arr = [] 
    slot_num = 10 # 10 means 10 slots, each 
                  # slot's size is 0.1 
    for i in range(slot_num): 
        arr.append([]) 
          
    # Put array elements in different buckets  
    for j in x: 
        index_b = int(slot_num * j)  
        arr[index_b].append(j) 
      
    # Sort individual buckets  
    for i in range(slot_num): 
        arr[i] = insertionSort(arr[i]) 
          
    # concatenate the result 
    k = 0
    for i in range(slot_num): 
        for j in range(len(arr[i])): 
            x[k] = arr[i][j] 
            k += 1
    return x 
  
# Driver Code 
x = [0.897, 0.565, 0.656, 
     0.1234, 0.665, 0.3434]  
print("Sorted Array is") 
print(bucketSort(x))

Kết quả

Sorted array is
0.1234 0.3434 0.565 0.656 0.665 0.897

3. Độ phức tạp

Độ phức tạp về thời gian: Nếu chúng ta giả sử rằng việc chèn vào một nhóm mất O (1) thời gian thì bước 1 và 2 của thuật toán trên rõ ràng sẽ mất O (n) thời gian. O (1) có thể dễ dàng nếu chúng ta sử dụng một danh sách liên kết để biểu diễn một nhóm (Trong đoạn mã sau, vectơ C ++ được sử dụng để đơn giản hóa). Bước 4 cũng mất O (n) thời gian vì sẽ có n mục trong tất cả các nhóm.

Bước chính để phân tích là bước 3. Bước này trung bình cũng mất O (n) thời gian nếu tất cả các số được phân bố đồng đều (vui lòng tham khảo sách CLRS để biết thêm chi tiết)

Nguồn và Tài liệu tiếng anh tham khảo:

Tài liệu từ cafedev:

Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:

Chào thân ái và quyết thắng!

Đăng ký kênh youtube để ủng hộ Cafedev nha các bạn, Thanks you!

BÀI VIẾT LIÊN QUANXEM THÊM