Thuật toán sắp xếp nhóm (Java, Python, C/C++ Code Ví dụ)

Sắp xếp nhóm là gì?

Thuật toán sắp xếp theo nhóm (Bucket Sort), thường được gọi là sắp xếp theo thùng (bin sort), là một phương pháp sắp xếp phân phối dựa trên so sánh, nhận đầu vào là một mảng chưa được sắp xếp và tạo ra đầu ra là một mảng đã được sắp xếp. Kỹ thuật này phân phối các phần tử vào nhiều nhóm (bucket) và sắp xếp từng nhóm riêng lẻ bằng một thuật toán sắp xếp khác, chẳng hạn như sắp xếp chèn (insertion sort). Sau đó, tất cả các nhóm được hợp nhất lại với nhau để tạo thành mảng đã được sắp xếp cuối cùng.

Thuật toán sắp xếp theo nhóm (Bucket Sort) thường được sử dụng khi các phần tử:

1. Giá trị dấu phẩy động
2. Phân bố đồng đều trên một phạm vi đã biết.

Độ phức tạp về thời gian của thuật toán Bucket Sort phụ thuộc vào số lượng thùng chứa được sử dụng và tính đồng nhất của phân bố dữ liệu đầu vào. Trong khi các thuật toán sắp xếp khác như... sắp xếp vỏ, sắp xếp hợp nhất, heapsort và sắp xếp nhanh chóng Để đạt được độ phức tạp thời gian tốt nhất là O(n*logn), thuật toán Bucket Sort có thể đạt được độ phức tạp thời gian tuyến tính O(n) trong điều kiện thuận lợi.

Thuật toán Bucket Sort tuân theo phương pháp phân tán-thu thập. Các phần tử được phân tán vào các nhóm tương ứng, được sắp xếp bên trong mỗi nhóm, và được thu thập để tạo thành một mảng đã được sắp xếp ở bước cuối cùng. Phương pháp phân tán-thu thập này sẽ được thảo luận trong phần tiếp theo.

Phương pháp phân tán-thu thập

Các vấn đề phức tạp, quy mô lớn đôi khi rất khó giải quyết trực tiếp. Phương pháp phân tán-tập hợp giải quyết những vấn đề như vậy bằng cách chia toàn bộ tập dữ liệu thành các cụm. Mỗi cụm được xử lý riêng biệt, và kết quả được kết hợp lại để đưa ra câu trả lời cuối cùng.

Đây là cách thuật toán Bucket Sort triển khai phương pháp phân tán-tập hợp:

Cách sắp xếp nhóm hoạt động

Nguyên tắc hoạt động cơ bản của thuật toán phân loại theo nhóm (Bucket Sort) như sau:

1. Một tập hợp các thùng chứa trống được tạo ra. Tùy thuộc vào chính sách đã chọn, số lượng thùng chứa có thể thay đổi.
2. Từ mảng đầu vào, mỗi phần tử được đặt vào ô tương ứng của nó.
3. Mỗi thùng chứa được phân loại riêng lẻ bằng thuật toán phân loại thứ cấp.
4. Các nhóm dữ liệu đã được sắp xếp sẽ được nối lại với nhau để tạo ra một mảng đầu ra duy nhất.

Biệt danh Code

Start
Create N empty buckets
For each array element:
    Calculate bucket index
    Put that element into the corresponding bucket
For each bucket:
    Sort elements within each bucket
Merge all the elements from each bucket
Output the sorted array
End

Phương pháp 1: Thuật toán sắp xếp nhóm cho dấu phẩy động Numbers

Thuật toán sắp xếp theo nhóm (Bucket Sort) cho các số thực trong phạm vi [0.0, 1.0]:

Bước 1) Tạo mười (10) thùng rỗng. Thùng đầu tiên chứa các số trong khoảng [0.0, 0.1). Thùng thứ hai chứa [0.1, 0.2), và cứ thế tiếp tục.

Bước 2) Đối với mỗi phần tử mảng:

• a. Tính chỉ số nhóm bằng công thức:
  bucket_index = no_of_buckets * array_element
• b. Chèn phần tử vào bucket[bucket_index]

Bước 3) Sắp xếp từng nhóm riêng lẻ bằng cách sử dụng phương pháp sắp xếp chèn.

Bước 4) Ghép tất cả các nhóm lại thành một mảng duy nhất đã được sắp xếp.

Chúng ta hãy cùng xem xét một ví dụ về Sắp xếp theo nhóm (Bucket Sort). Trong ví dụ này, chúng ta sẽ sắp xếp mảng sau:

Bước 1) Đầu tiên, chúng ta tạo 10 thùng rỗng. Thùng thứ nhất chứa các số trong khoảng [0.0, 0.1). Thùng thứ hai chứa [0.1, 0.2), và cứ thế tiếp tục.

Bước 2) Với mỗi phần tử trong mảng, hãy tính chỉ số nhóm (bucket index) và đặt phần tử đó vào nhóm tương ứng.

Chỉ số nhóm được tính bằng công thức:
        bucket_index = no_of_buckets * array_element

Tính toán chỉ số nhóm:
a) XUẤT KHẨU
      bucket_index = no_of_buckets * array_element
              = 10 * 0.78
              = 7.8
Do đó, phần tử 0.78 được lưu trữ trong bucket[floor(7.8)] hoặc bucket[7].

b) NHẬP KHẨU
      bucket_index = no_of_buckets * array_element
              = 10 * 0.17
              = 1.7

Phần tử mảng 0.17 được lưu trữ trong bucket[floor(1.7)] hoặc bucket[1].

c) 0.39
      bucket_index = no_of_buckets * array_element
              = 10 * 0.39
              = 3.9
0.39 được lưu trữ trong xô[floor(3.9)] hoặc xô[3].

Sau khi duyệt qua tất cả các phần tử của mảng, các nhóm (bucket) sẽ trông như sau:

Bước 3) Mỗi nhóm dữ liệu sau đó được sắp xếp bằng thuật toán sắp xếp chèn. Sau khi thực hiện thao tác sắp xếp, kết quả đầu ra là:

Bước 4) Ở bước cuối cùng, các nhóm dữ liệu được ghép lại thành một mảng duy nhất. Mảng đó chính là kết quả đã được sắp xếp của dữ liệu đầu vào.

Mỗi nhóm (bucket) được nối vào mảng đầu ra. Ví dụ, sự nối các phần tử của nhóm thứ hai như sau:

Sự kết hợp của các phần tử cuối cùng trong nhóm được thể hiện bên dưới:

Sau khi nối chuỗi, mảng kết quả là mảng đã được sắp xếp như mong muốn.

Chương trình sắp xếp nhóm trong C/C++

Đầu vào:

//Bucket Sort Program in C/C++
//For values without integer parts
#include <bits/stdc++.h>
#define BUCKET_SIZE 10
using namespace std;
void bucketSort(float input[], int array_size)
{
  vector <float>bucket[BUCKET_SIZE];
  for (int i = 0; i < array_size; i++) {
    int index = BUCKET_SIZE*input[i];
    bucket[index].push_back(input[i]);
  }
  for (int i = 0; i < BUCKET_SIZE; i++)
    sort(bucket[i].begin(), bucket[i].end());
  int out_index = 0;
  for (int i = 0; i < BUCKET_SIZE; i++)
    for (int j = 0; j < bucket[i].size(); j++)
      input[out_index++] = bucket[i][j];
}
int main()
{
  float input[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.69};
  int array_size = sizeof(input)/sizeof(input[0]);

  bucketSort(input, array_size);
  cout <<"Sorted Output: 
";
  for (int i = 0; i< array_size; i++)
    cout<<input[i]<<" ";
  return 0;
}

Đầu ra:

Sorted Output:
0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94

Chương trình sắp xếp nhóm trong Python

Đầu vào:

# Bucket Sort Program in Python
# For values without integer parts
def bucketSort(input):
    output = []
    bucket_size = 10
    for bucket in range(bucket_size):
        output.append([])
    for element in input:
        index = int(bucket_size * element)
        output[index].append(element)
    for bucket in range(bucket_size):
        output[bucket] = sorted(output[bucket])
    out_index = 0
    for bucket in range(bucket_size):
        for element in range(len(output[bucket])):
            input[out_index] = output[bucket][element]
            out_index += 1
    return input

input = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.69]
print("Sorted Output:")
print(bucketSort(input))

Đầu ra:

Sorted Output:
[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]

Nhóm Sắp xếp theo Java

Đầu vào:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
    private static final int BUCKET_SIZE = 10;
    public static void bucketSort(float[] input, int arraySize) {
        List<Float>[] bucket = new ArrayList[BUCKET_SIZE];
        for (int i = 0; i < arraySize; i++) {
            int index = (int)(BUCKET_SIZE * input[i]);
            if (bucket[index] == null) {
                bucket[index] = new ArrayList<>();
            }
            bucket[index].add(input[i]);
        }
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (bucket[i] != null) {
                Collections.sort(bucket[i]);
            }
        }
        int outIndex = 0;
        for (int i = 0; i < BUCKET_SIZE; i++) {
            if (bucket[i] != null) {
                for (float value: bucket[i]) {
                    input[outIndex++] = value;
                }
            }
        }
    }
    public static void main(String[] args) {
        float[] input = {0.78f,0.17f,0.39f,0.26f,0.72f,0.94f,0.21f,0.12f,0.23f,0.69f};
        int arraySize = input.length;
        bucketSort(input, arraySize);
        System.out.println("Sorted Output:");
        for (int i = 0; i < arraySize; i++) {
            System.out.print(input[i]+" ");
        }
    }
}

Đầu ra:

Sorted Output:
0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94

Phương pháp 2: Thuật toán sắp xếp nhóm cho các phần tử số nguyên

Thuật toán Bucket Sort dành cho dữ liệu đầu vào chứa các số nằm ngoài phạm vi [0.0, 1.0] hơi khác so với thuật toán trước đó. thuật toánCác bước cần thực hiện trong trường hợp này như sau:

Bước 1) Tìm phần tử lớn nhất và nhỏ nhất trong mảng.

Bước 2) Chọn số lượng thùng, n, và khởi tạo chúng ở trạng thái trống.

Bước 3) Tính toán phạm vi hoặc khoảng của từng nhóm bằng công thức:
        span = (maximum - minimum) / n

Bước 4) Đối với mỗi phần tử mảng:

• 1. Tính chỉ số nhóm:
          bucket_index = (element - minimum) / span
• 2. Chèn phần tử vào bucket[bucket_index]

Bước 5) Sắp xếp từng nhóm bằng cách sử dụng phương pháp sắp xếp chèn.

Bước 6) Ghép tất cả các nhóm thành một mảng duy nhất.

Chúng ta hãy cùng xem xét một ví dụ về thuật toán Sắp xếp theo nhóm (Bucket Sort). Trong ví dụ này, chúng ta sẽ sắp xếp mảng sau:

Bước 1) Bước đầu tiên, chúng ta tìm phần tử lớn nhất và nhỏ nhất của mảng đã cho. Trong ví dụ này, phần tử lớn nhất là 24 và phần tử nhỏ nhất là 1.

Bước 2) Tiếp theo, chúng ta chọn số lượng thùng rỗng, n. Trong ví dụ này, chúng ta sử dụng 5 thùng và khởi tạo chúng ở trạng thái rỗng.

Bước 3) Khoảng cách giữa mỗi nhóm được tính bằng công thức:
        span = (maximum - minimum) / n = (24 - 1) / 5 = 4

Do đó, nhóm đầu tiên chứa các số trong khoảng [0, 5). Nhóm thứ hai chứa các số trong khoảng [5, 10), và cứ thế tiếp tục.

Bước 4) Với mỗi phần tử trong mảng, hãy tính chỉ số nhóm (bucket index) và đặt phần tử đó vào nhóm tương ứng. Chỉ số nhóm được tính bằng công thức:
        bucket_index = (element - minimum) / span

Tính toán chỉ số nhóm:

a) XUẤT KHẨU
chỉ số nhóm = (phần tử – giá trị nhỏ nhất) / khoảng
        = (11 - 1) / 4
        = 2

Do đó, phần tử 11 được lưu trữ trong thùng[2].

b) NHẬP KHẨU
chỉ số nhóm = (phần tử – giá trị nhỏ nhất) / khoảng
        = (9 - 1) / 4
        = 2

Lưu ý: Vì 9 là phần tử ranh giới cho bucket[1] nên nó được thêm vào bucket[1] thay vì được đặt trong cùng bucket với phần tử trước đó.

Sau khi thực hiện các thao tác cho từng phần tử, các nhóm sẽ trông như sau:

Bước 5) Bây giờ, mỗi nhóm dữ liệu được sắp xếp bằng thuật toán sắp xếp chèn. Các nhóm dữ liệu sau khi sắp xếp:

Bước 6) Ở bước cuối cùng, các nhóm dữ liệu được ghép nối thành một mảng duy nhất. mảng Đây là kết quả đã được sắp xếp của dữ liệu đầu vào.

Chương trình sắp xếp nhóm trong C/C++

Đầu vào:

#include<bits/stdc++.h>
using namespace std;
void bucketSort(vector < double > & input, int No_Of_Buckets)
{
  double max_value = * max_element(input.begin(), input.end());
  double min_value = * min_element(input.begin(), input.end());
  double span = (max_value - min_value) / No_Of_Buckets;
  vector<vector <double>> output;
  for (int i = 0; i < No_Of_Buckets; i++)
    output.push_back(vector <double>());
  for (int i = 0; i < input.size(); i++)
  {
    double difference = (input[i] - min_value) / span
     - int((input[i] - min_value) / span);
    if (difference == 0 && input[i] != min_value)
      output[int((input[i] - min_value) / span) - 1].push_back(input[i]);
    else
      output[int((input[i] - min_value) / span)].push_back(input[i]);
  }
  for (int i = 0; i < output.size(); i++)
  {
    if (!output[i].empty())
      sort(output[i].begin(), output[i].end());
  }
  int index = 0;
  for (vector <double> & bucket: output)
  {
    if (!bucket.empty())
    {
      for (double i: bucket)
      {
        input[index] = i;
        index++;
      }
    }
  }
}
int main()
{
  vector <double> input ={11,9,21,8,17,19,13,1,24,12};
  int No_Of_Buckets = 5;
  bucketSort(input, No_Of_Buckets);
  cout<<"Sorted Output:";
  for (int i=0; i < input.size(); i++)
    cout <<input[i]<<" ";
  return 0;
}

Đầu ra:

Sorted Output:1 8 9 11 12 13 17 19 21 24

Chương trình sắp xếp nhóm trong Python

Đầu vào:

def bucketSort(input, No_Of_Buckets):
    max_element = max(input)
    min_element = min(input)
    span = (max_element - min_element) / No_Of_Buckets
    output = []
    for bucket in range(No_Of_Buckets):
        output.append([])
    for element in range(len(input)):
        diff = (input[element] - min_element) / span - int(
            (input[element] - min_element) / span
        )
        if diff == 0 and input[element] != min_element:
            output[int((input[element] - min_element) / span) - 1].append(
                input[element]
            )
        else:
            output[int((input[element] - min_element) / span)].append(input[element])
    for bucket in range(len(output)):
        if len(output[bucket]) != 0:
            output[bucket].sort()
    index = 0
    for bucket in output:
        if bucket:
            for element in bucket:
                input[index] = element
                index = index + 1
input = [11, 9, 21, 8, 17, 19, 13, 1, 24, 12]
No_Of_Buckets = 5
bucketSort(input, No_Of_Buckets)
print("Sorted Output:
", input)

Đầu ra:

Sorted Output:
[1, 8, 9, 11, 12, 13, 17, 19, 21, 24]

Nhóm Sắp xếp theo Java

Đầu vào:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class BucketSort {
    public static void bucketSort(List < Double > input, int No_Of_Buckets) {
        double max_value = Collections.max(input);
        double min_value = Collections.min(input);
        double span =(max_value - min_value) / No_Of_Buckets;
        List<List<Double>> output = new ArrayList<>();
        for (int i = 0; i < No_Of_Buckets; i++) {
            output.add(new ArrayList<>());
        }
        for (Double value: input) {
            double difference = (value - min_value) / span - ((value - min_value) / span);
            if (difference == 0 && value != min_value) {
                output.get((int)((value - min_value) / span) - 1).add(value);
            } else {
                output.get((int)((value - min_value) / span)).add(value);
            }
        }
        for (List <Double> bucket: output) {
            if (!bucket.isEmpty()) {
                Collections.sort(bucket);
            }
        }
        int index = 0;
        for (List <Double> bucket: output) {
            if (!bucket.isEmpty()) {
                for (Double value: bucket) {
                    input.set(index,value);
                    index++;
                }
            }
        }
    }
    public static void main(String[] args) {
        List <Double> input = new ArrayList<>();
        input.add(11.0);
        input.add(9.0);
        input.add(21.0);
        input.add(8.0);
        input.add(17.0);
        input.add(19.0);
        input.add(13.0);
        input.add(1.0);
        input.add(24.0);
        input.add(12.0);
        int No_Of_Buckets = 5;
        bucketSort(input, No_Of_Buckets);
        System.out.println("Sorted Output:");
        for (Double value: input) {
            System.out.print(value + " ");
        }
    }
}

Đầu ra:

Sorted Output:
1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0

Ưu điểm và nhược điểm của phương pháp phân loại theo nhóm

Phân tích độ phức tạp của Bucket Sort

Độ phức tạp của thời gian sắp xếp nhóm

• Độ phức tạp trường hợp tốt nhất: Nếu tất cả các phần tử mảng được phân bố đồng đều và được sắp xếp trước trong mỗi nhóm, thì cần thời gian O(n) để phân tán các phần tử vào các nhóm tương ứng. Sau đó, sắp xếp từng nhóm bằng cách sử dụng sắp xếp chèn chi phí O(k). Do đó, độ phức tạp tổng thể là O(n+k).
• Độ phức tạp trường hợp trung bình: Trong các trường hợp trung bình, chúng ta giả định các đầu vào được phân bố đồng đều. Do đó, thuật toán Sắp xếp theo nhóm đạt được độ phức tạp thời gian tuyến tính là O(n+k). Ở đây, cần thời gian O(n) để phân tán các phần tử và cần thời gian O(k) để sắp xếp chúng bằng thuật toán sắp xếp chèn.
• Độ phức tạp trường hợp xấu nhất: Trong trường hợp xấu nhất, các phần tử không được phân bố đồng đều và tập trung vào một hoặc hai nhóm. Trong trường hợp đó, thuật toán Bucket Sort sẽ hoạt động tương tự như một thuật toán khác. thuật toán sắp xếp nổi bọtDo đó, trong trường hợp xấu nhất, độ phức tạp thời gian của thuật toán Sắp xếp theo nhóm là O(n²).

Độ phức tạp không gian của Bucket Sort

Độ phức tạp không gian của thuật toán Sắp xếp theo nhóm (Bucket Sort) là O(n*k). Ở đây, n là số phần tử và k là số nhóm cần thiết để chứa chúng trong quá trình sắp xếp.

Câu Hỏi Thường Gặp