Thuật toán sắp xếp theo nhóm

Trong hướng dẫn này, bạn sẽ tìm hiểu cách sắp xếp theo nhóm hoạt động. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc về sắp xếp nhóm trong C, C ++, Java và Python.

Bucket Sort là một kỹ thuật sắp xếp sắp xếp các phần tử bằng cách đầu tiên chia các phần tử thành nhiều nhóm được gọi là nhóm . Các phần tử bên trong mỗi nhóm được sắp xếp bằng cách sử dụng bất kỳ thuật toán sắp xếp phù hợp nào hoặc gọi đệ quy cùng một thuật toán.

Một số nhóm được tạo. Mỗi nhóm chứa đầy một loạt các phần tử cụ thể. Các phần tử bên trong nhóm được sắp xếp bằng bất kỳ thuật toán nào khác. Cuối cùng, các phần tử của thùng được tập hợp để có được mảng đã sắp xếp.

Quá trình sắp xếp theo nhóm có thể được hiểu là một cách tiếp cận tập hợp phân tán . Đầu tiên các phần tử được phân tán thành các nhóm sau đó các phần tử của các nhóm được sắp xếp. Cuối cùng, các yếu tố được tập hợp theo thứ tự.

Hoạt động của phân loại nhóm

Cách phân loại nhóm hoạt động?

Giả sử, mảng đầu vào là: Mảng đầu vào
Tạo một mảng có kích thước 10. Mỗi vị trí của mảng này được sử dụng như một thùng để chứa các phần tử. Mảng trong đó mỗi vị trí là một nhóm
Chèn các phần tử vào nhóm từ mảng. Các phần tử được chèn theo phạm vi của nhóm.
Trong mã ví dụ của chúng tôi, chúng tôi có các nhóm mỗi phạm vi từ 0 đến 1, 1 đến 2, 2 đến 3,… (n-1) đến n.
Giả sử, một phần tử đầu vào .23được lấy. Nó được nhân với size = 10(tức là. .23*10=2.3). Sau đó, nó được chuyển đổi thành một số nguyên (tức là. 2.3≈2). Cuối cùng, .23 được chèn vào bucket-2 . Chèn các phần tử vào các nhóm từ mảng
Tương tự, .25 cũng được chèn vào cùng một nhóm. Mọi lúc, giá trị sàn của số dấu phẩy động được lấy.
Nếu chúng ta lấy số nguyên làm đầu vào, chúng ta phải chia nó cho khoảng (10 ở đây) để nhận được giá trị sàn.
Tương tự, các phần tử khác được chèn vào các nhóm tương ứng của chúng. Chèn tất cả các phần tử vào nhóm từ mảng
Các phần tử của mỗi nhóm được sắp xếp bằng cách sử dụng bất kỳ thuật toán sắp xếp ổn định nào. Ở đây, chúng ta đã sử dụng quicksort (hàm sẵn có). Sắp xếp các phần tử trong mỗi nhóm
Các phần tử từ mỗi nhóm được tập hợp.
Nó được thực hiện bằng cách lặp qua nhóm và chèn một phần tử riêng lẻ vào mảng ban đầu trong mỗi chu kỳ. Phần tử từ nhóm sẽ bị xóa khi nó được sao chép vào mảng ban đầu. Thu thập các yếu tố từ mỗi nhóm

Thuật toán sắp xếp theo nhóm

 bucketSort () tạo N nhóm, mỗi nhóm có thể chứa một phạm vi giá trị cho tất cả các nhóm khởi tạo mỗi nhóm bằng 0 giá trị cho tất cả các nhóm đặt các phần tử vào các nhóm phù hợp với phạm vi cho tất cả các nhóm sắp xếp các phần tử trong mỗi nhóm tập hợp các phần tử từ mỗi nhóm cuối thùng

Ví dụ về Python, Java và C / C ++

Python Java C C ++

 # Bucket Sort in Python def bucketSort(array): bucket = () # Create empty buckets for i in range(len(array)): bucket.append(()) # Insert elements into their respective buckets for j in array: index_b = int(10 * j) bucket(index_b).append(j) # Sort the elements of each bucket for i in range(len(array)): bucket(i) = sorted(bucket(i)) # Get the sorted elements k = 0 for i in range(len(array)): for j in range(len(bucket(i))): array(k) = bucket(i)(j) k += 1 return array array = (.42, .32, .33, .52, .37, .47, .51) print("Sorted Array in descending order is") print(bucketSort(array))

 // Bucket sort in Java import java.util.ArrayList; import java.util.Collections; public class BucketSort ( public void bucketSort(float() arr, int n) ( if (n <= 0) return; @SuppressWarnings("unchecked") ArrayList() bucket = new ArrayList(n); // Create empty buckets for (int i = 0; i < n; i++) bucket(i) = new ArrayList(); // Add elements into the buckets for (int i = 0; i < n; i++) ( int bucketIndex = (int) arr(i) * n; bucket(bucketIndex).add(arr(i)); ) // Sort the elements of each bucket for (int i = 0; i < n; i++) ( Collections.sort((bucket(i))); ) // Get the sorted array int index = 0; for (int i = 0; i < n; i++) ( for (int j = 0, size = bucket(i).size(); j < size; j++) ( arr(index++) = bucket(i).get(j); ) ) ) // Driver code public static void main(String() args) ( BucketSort b = new BucketSort(); float() arr = ( (float) 0.42, (float) 0.32, (float) 0.33, (float) 0.52, (float) 0.37, (float) 0.47, (float) 0.51 ); b.bucketSort(arr, 7); for (float i : arr) System.out.print(i + " "); ) )

 // Bucket sort in C #include #include #define NARRAY 7 // Array size #define NBUCKET 6 // Number of buckets #define INTERVAL 10 // Each bucket capacity struct Node ( int data; struct Node *next; ); void BucketSort(int arr()); struct Node *InsertionSort(struct Node *list); void print(int arr()); void printBuckets(struct Node *list); int getBucketIndex(int value); // Sorting function void BucketSort(int arr()) ( int i, j; struct Node **buckets; // Create buckets and allocate memory size buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET); // Initialize empty buckets for (i = 0; i < NBUCKET; ++i) ( buckets(i) = NULL; ) // Fill the buckets with respective elements for (i = 0; i data = arr(i); current->next = buckets(pos); buckets(pos) = current; ) // Print the buckets along with their elements for (i = 0; i < NBUCKET; i++) ( printf("Bucket(%d): ", i); printBuckets(buckets(i)); printf(""); ) // Sort the elements of each bucket for (i = 0; i < NBUCKET; ++i) ( buckets(i) = InsertionSort(buckets(i)); ) printf("-------------"); printf("Bucktets after sorting"); for (i = 0; i < NBUCKET; i++) ( printf("Bucket(%d): ", i); printBuckets(buckets(i)); printf(""); ) // Put sorted elements on arr for (j = 0, i = 0; i data; node = node->next; ) ) return; ) // Function to sort the elements of each bucket struct Node *InsertionSort(struct Node *list) ( struct Node *k, *nodeList; if (list == 0 || list->next == 0) ( return list; ) nodeList = list; k = list->next; nodeList->next = 0; while (k != 0) ( struct Node *ptr; if (nodeList->data> k->data) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = nodeList; nodeList = tmp; continue; ) for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) ( if (ptr->next->data> k->data) break; ) if (ptr->next != 0) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = ptr->next; ptr->next = tmp; continue; ) else ( ptr->next = k; k = k->next; ptr->next->next = 0; continue; ) ) return nodeList; ) int getBucketIndex(int value) ( return value / INTERVAL; ) void print(int ar()) ( int i; for (i = 0; i data); cur = cur->next; ) ) // Driver code int main(void) ( int array(NARRAY) = (42, 32, 33, 52, 37, 47, 51); printf("Initial array: "); print(array); printf("-------------"); BucketSort(array); printf("-------------"); printf("Sorted array: "); print(array); return 0; )

 // Bucket sort in C++ #include #include using namespace std; #define NARRAY 7 // Array size #define NBUCKET 6 // Number of buckets #define INTERVAL 10 // Each bucket capacity struct Node ( int data; struct Node *next; ); void BucketSort(int arr()); struct Node *InsertionSort(struct Node *list); void print(int arr()); void printBuckets(struct Node *list); int getBucketIndex(int value); // Sorting function void BucketSort(int arr()) ( int i, j; struct Node **buckets; // Create buckets and allocate memory size buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET); // Initialize empty buckets for (i = 0; i < NBUCKET; ++i) ( buckets(i) = NULL; ) // Fill the buckets with respective elements for (i = 0; i data = arr(i); current->next = buckets(pos); buckets(pos) = current; ) // Print the buckets along with their elements for (i = 0; i < NBUCKET; i++) ( cout << "Bucket(" << i << ") : "; printBuckets(buckets(i)); cout << endl; ) // Sort the elements of each bucket for (i = 0; i < NBUCKET; ++i) ( buckets(i) = InsertionSort(buckets(i)); ) cout << "-------------" << endl; cout << "Bucktets after sorted" << endl; for (i = 0; i < NBUCKET; i++) ( cout << "Bucket(" << i << ") : "; printBuckets(buckets(i)); cout << endl; ) // Put sorted elements on arr for (j = 0, i = 0; i data; node = node->next; ) ) for (i = 0; i next; free(tmp); ) ) free(buckets); return; ) // Function to sort the elements of each bucket struct Node *InsertionSort(struct Node *list) ( struct Node *k, *nodeList; if (list == 0 || list->next == 0) ( return list; ) nodeList = list; k = list->next; nodeList->next = 0; while (k != 0) ( struct Node *ptr; if (nodeList->data> k->data) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = nodeList; nodeList = tmp; continue; ) for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) ( if (ptr->next->data> k->data) break; ) if (ptr->next != 0) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = ptr->next; ptr->next = tmp; continue; ) else ( ptr->next = k; k = k->next; ptr->next->next = 0; continue; ) ) return nodeList; ) int getBucketIndex(int value) ( return value / INTERVAL; ) // Print buckets void print(int ar()) ( int i; for (i = 0; i < NARRAY; ++i) ( cout << setw(3) << ar(i); ) cout << endl; ) void printBuckets(struct Node *list) ( struct Node *cur = list; while (cur) ( cout << setw(3)  next; ) ) // Driver code int main(void) ( int array(NARRAY) = (42, 32, 33, 52, 37, 47, 51); cout << "Initial array: " << endl; print(array); cout << "-------------" << endl; BucketSort(array); cout << "-------------" << endl; cout << "Sorted array: " << endl; print(array); )

Phức tạp

Độ phức tạp của trường hợp tồi tệ nhất: Khi có các phần tử ở phạm vi gần trong mảng, chúng có khả năng được đặt trong cùng một nhóm. Điều này có thể dẫn đến một số nhóm có nhiều phần tử hơn các nhóm khác. Nó làm cho độ phức tạp phụ thuộc vào thuật toán sắp xếp được sử dụng để sắp xếp các phần tử của nhóm. Sự phức tạp thậm chí còn trở nên tồi tệ hơn khi các phần tử có thứ tự ngược lại. Nếu sắp xếp chèn được sử dụng để sắp xếp các phần tử của nhóm, thì độ phức tạp về thời gian sẽ trở thành .O(n²)

O(n²)
Độ phức tạp của trường hợp tốt nhất: O(n+k)
Nó xảy ra khi các phần tử được phân phối đồng đều trong các nhóm với số phần tử gần bằng nhau trong mỗi nhóm.
Sự phức tạp thậm chí còn trở nên tốt hơn nếu các phần tử bên trong các nhóm đã được sắp xếp.
Nếu sắp xếp chèn được sử dụng để sắp xếp các phần tử của một nhóm thì độ phức tạp tổng thể trong trường hợp tốt nhất sẽ là tuyến tính. O(n+k). O(n)là độ phức tạp để tạo nhóm và O(k)là độ phức tạp để sắp xếp các phần tử của nhóm bằng cách sử dụng các thuật toán có độ phức tạp thời gian tuyến tính ở trường hợp tốt nhất.
Độ phức tạp trường hợp trung bình: O(n)
Nó xảy ra khi các phần tử được phân phối ngẫu nhiên trong mảng. Ngay cả khi các phần tử không được phân phối đồng nhất, sắp xếp nhóm chạy theo thời gian tuyến tính. Nó đúng cho đến khi tổng số bình phương của kích thước nhóm là tuyến tính trong tổng số phần tử.