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

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

Sắp xếp nhóm, thường được gọi là sắp xếp bin, là một phương pháp sắp xếp so sánh chấp nhận một mảng chưa được sắp xếp làm đầu vào và kết quả là tạo ra một mảng được sắp xếp. Phương pháp này hoạt động bằng cách phân phối các phần tử thành nhiều nhóm và sắp xếp từng nhóm riêng lẻ bằng bất kỳ thuật toán sắp xếp nào, chẳng hạn như sắp xếp chèn. Sau đó, tất cả các nhóm được hợp nhất với nhau để tạo thành một mảng được sắp xếp.

Sắp xếp nhóm thường được sử dụng khi các phần tử-

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

Độ phức tạp thời gian của Bucket Sort phụ thuộc vào số lượng bucket được sử dụng và tính đồng nhất của phân phối đầu vào. Trong khi các thuật toán sắp xếp khác nhau như sắp xếp vỏ, sắp xếp hợp nhất, heapsort và sắp xếp nhanh chóng có thể đạt được độ phức tạp thời gian tốt nhất là O(n*logn), thuật toán sắp xếp theo nhóm có thể đạt được độ phức tạp thời gian tuyến tính tương tự hoặc O(n).

Bucket sort tuân theo phương pháp phân tán-tập hợp. Áp dụng phương pháp này, các phần tử được phân tán vào các bucket tương ứng, được sắp xếp trong các bucket và được tập hợp lại để tạo thành một mảng được sắp xếp như bước cuối cùng. Phương pháp phân tán-tập hợp này được thảo luận trong phần sau

Phương pháp phân tán-tập hợp

Các vấn đề phức tạp, quy mô lớn đôi khi có thể khó giải quyết. Phương pháp phân tán-tập hợp cố gắng giải quyết các vấn đề như vậy bằng cách chia toàn bộ tập dữ liệu thành các cụm. Sau đó, mỗi cụm được giải quyết riêng biệt và đưa mọi thứ trở lại với nhau để có được câu trả lời cuối cùng.

Đây là cách thuật toán sắp xếp nhóm triển khai phương pháp thu thập phân tán:

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 lý làm việc cơ bản của sắp xếp nhóm như sau:

  1. Một tập hợp các thùng trống được tạo. Dựa trên các chính sách khác nhau, số lượng nhóm có thể khác nhau.
  2. Từ mảng đầu vào, đặt từng phần tử vào nhóm tương ứng.
  3. Sắp xếp các nhóm đó riêng lẻ.
  4. Ghép nối các nhóm đã sắp xếp để tạo một mảng đầu ra duy nhất.

Các bước thực hiện chi tiết được cung cấp ở các phần sau.

Mã giả

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 nhóm cho các số dấu phẩy động trong phạm vi từ 0.0 đến 1.0:

Bước 1) Tạo mười (10) nhóm trống sao cho nhóm đầu tiên sẽ chứa các số trong phạm vi [0.0, 0.1). Sau đó, nhóm thứ hai sẽ chứa trong [0.1, 0.2), v.v.

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

      Một. Tính chỉ số nhóm bằng công thức:
      chỉ số nhóm = no_of_buckets *mảng_element
      b. Chèn phần tử vào nhóm [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 nối tất cả các nhóm thành một mảng duy nhất.

Chúng ta hãy xem một ví dụ về bucket sort. Đối với ví dụ này, chúng ta sẽ sắp xếp mảng sau bằng thuật toán bucket sort-

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

Bước 1) Đầu tiên, chúng ta sẽ tạo 10 thùng trống. Nhóm đầu tiên sẽ chứa các số trong khoảng [0.0, 0.1). Sau đó, nhóm thứ hai sẽ chứa các số trong khoảng [0.1, 0.2), v.v.

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

Bước 2) Với mỗi phần tử mảng, chúng ta sẽ tính chỉ số nhóm và đặt phần tử đó vào nhóm đó.

Chỉ số nhóm có thể được tính bằng công thức:
              xô_index= no_of_buckets*mảng_element

Tính toán chỉ số nhóm:
a) XUẤT KHẨU
      xô_index = no_of_buckets*mảng_element
                   = 10 * 0.78
                   = 7.8
Do đó, phần tử 0.78 sẽ được lưu trữ trên nhóm [sàn(7.8)] hoặc nhóm [7].

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

b) NHẬP KHẨU
      xô_index = no_of_buckets * phần tử mảng
                   = 10 * 0.17
                   = 1.7

Phần tử mảng 0.17 sẽ được lưu trữ trên xô[sàn(1.7)] hoặc xô[1].

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

c) 0.39
      xô_index = no_of_buckets * phần tử mảng
                   = 10 * 0.39
                   = 3.9
   0.39 sẽ được lưu trữ trên xô[sàn(3.9)] hoặc xô[3].

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

Sau khi lặp qua tất cả các phần tử mảng, các thùng sẽ như sau:

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

Bước 3) Sau đó, mỗi nhóm sẽ được sắp xếp bằng cách sử dụng phương pháp sắp xếp chèn. Sau khi thực hiện thao tác sắp xếp, kết quả sẽ là:

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

Bước 4) Ở bước cuối cùng, các nhóm sẽ được nối thành một mảng duy nhất. Mảng đó sẽ là kết quả được sắp xếp của đầu vào.

Mỗi nhóm sẽ được nối với mảng đầu ra. Ví dụ: việc ghép các phần tử nhóm thứ hai:

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

Sự nối kết của các phần tử thùng cuối cùng sẽ như sau:

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

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

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

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

Đầu vào:

//Bucket Sort Program in C/C++
//For not having 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: \n";
 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 not having 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 sắp xếp nhóm cho đầu vào chứa các số nằm ngoài phạm vi [0.0, 1.0] hơi khác một chút so với thuật toán trước đó thuật toán. Các bước cần thiết cho trường hợp này như sau-

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

Bước 2) Chọn số lượng nhóm, n và khởi tạo các nhóm đó là 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ố xô:
                   bucket_index = (element - minimum)/span
    2. Chèn phần tử vào nhóm [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 xem một ví dụ về thuật toán bucket sort này. Đối với ví dụ này, chúng ta sẽ sắp xếp mảng sau bằng thuật toán bucket sort-

Thuật toán sắp xếp nhóm cho các phần tử số nguyên

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

Bước 2) Bây giờ, chúng ta phải chọn một số thùng trống, n. Trong ví dụ này, chúng ta sẽ lấy 5 thùng. Sau đó chúng ta sẽ khởi tạo chúng ở trạng thái trống.

Bước 3) Khoảng cách của mỗi thùng cần được tính theo công thức sau:
               span = (maximum-minimum)/n = (24-1)/5 = 4;

Do đó, nhóm đầu tiên sẽ chứa các số trong phạm vi [0, 5). Nhóm thứ hai sẽ chứa các số trong [5, 10), v.v.

Thuật toán sắp xếp nhóm cho các phần tử số nguyên

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

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

    a) 11bucket_index = (phần tử – tối thiểu)/span
                       =(11-1)/4
                       =2

Như vậy, phần tử 11 sẽ được lưu trữ trong nhóm [2].

Thuật toán sắp xếp nhóm cho các phần tử số nguyên

    b) NHẬP KHẨU
    xô_index = (phần tử – tối thiểu)/span
                       =(9-1)/4
                       =2

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

Thuật toán sắp xếp nhóm cho các phần tử số nguyên

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

Thuật toán sắp xếp nhóm cho các phần tử số nguyên

Bước 5) Bây giờ, mỗi nhóm sẽ được sắp xếp bằng cách sắp xếp chèn. Các thùng sau khi phân loại-

Thuật toán sắp xếp nhóm cho các phần tử số nguyên

Bước 6) Ở bước cuối cùng, các nhóm sẽ được nối thành một mảng duy nhất. Cái đó mảng sẽ là kết quả được sắp xếp của đầu vào.

Thuật toán sắp xếp nhóm cho các phần tử số nguyên

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; 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:\n", 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 và nhược điểm

Ưu điểm Nhược điểm
Thực hiện tính toán nhanh hơn Tiêu tốn nhiều không gian hơn so với các thuật toán khác
Nó có thể được sử dụng như một phương pháp sắp xếp bên ngoài Hoạt động kém khi dữ liệu không được phân phối đồng đều
Xô có thể được xử lý độc lập

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

Độ phức tạp thời gian của Bucket Sort

  • Độ 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 phối và sắp xếp đồng đều trước đó, thì sẽ 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 sẽ tốn O(k). Do đó, độ phức tạp tổng thể sẽ là O(n+k).
  • Độ phức tạp trường hợp trung bình:Đối với các trường hợp trung bình, chúng tôi giả định các đầu vào được phân phối đồng đều. Do đó, thuật toán sắp xếp bucket đạt được độ phức tạp thời gian tuyến tính là O(n+k). Ở đây, cần có thời gian O(n) để phân tán các phần tử và cần có thời gian O(k) để sắp xếp các phần tử đó bằng cách sử dụng 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ử sẽ không được phân bố đồng đều và tập trung trên một hoặc hai nhóm cụ thể. Trong trường hợp đó, sắp xếp nhóm sẽ hoạt động như một thuật toán sắp xếp bong bóng. Do đó, 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 sẽ là O(n^2).

Độ 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 nhóm là O(n*k). Trong đó n là số phần tử và k là số nhóm cần thiết.