Алгоритъм за сортиране на кофата

В този урок ще научите как работи сортирането на сегменти. Също така ще намерите работещи примери за сортиране на сегменти в C, C ++, Java и Python.

Bucket Sort е техника за сортиране, която сортира елементите, като първо разделя елементите на няколко групи, наречени сегменти . Елементите във всяка кофа се сортират с помощта на някоя от подходящи алгоритми за сортиране или рекурсивно извикване на същия алгоритъм.

Създават се няколко кофи. Всяка кофа се пълни с определен набор от елементи. Елементите вътре в кофата се сортират с помощта на всеки друг алгоритъм. И накрая, елементите на групата се събират, за да се получи сортираният масив.

Процесът на сортиране на кофа може да се разбере като подход за разпръскване . Елементите първо се разпръскват в кофи, след което елементите на кофите се сортират. Накрая елементите се събират по ред.

Работа по кофа сортиране

Как работи сортирането на кофата?

Да предположим, че входният масив е: Входен масив
Създайте масив с размер 10. Всеки слот от този масив се използва като група за съхранение на елементи. Масив, в който всяка позиция е кофа
Поставете елементи в кофите от масива. Елементите се вмъкват според обхвата на кофата.
В нашия примерен код имаме групи от всеки от диапазони от 0 до 1, 1 до 2, 2 до 3, … (n-1) до n.
Да предположим, че .23е взет входен елемент . Умножава се по size = 10(т.е. .23*10=2.3). След това се преобразува в цяло число (т.е. 2.3≈2). Накрая .23 се вмъква в кофа-2 . Вмъкване на елементи в кофите от масива
По същия начин .25 също се вмъква в същата кофа. Всеки път се взема минималната стойност на числото с плаваща запетая.
Ако вземем цели числа като вход, трябва да го разделим на интервала (10 тук), за да получим минималната стойност.
По същия начин други елементи се вмъкват в съответните им кофи. Вмъкнете всички елементи в кофите от масива
Елементите на всяка група се сортират с помощта на някой от стабилните алгоритми за сортиране. Тук използвахме бърза сортировка (вградена функция). Сортирайте елементите във всяка кофа
Елементите от всяка кофа се събират.
Това се прави чрез итерация през кофата и вмъкване на отделен елемент в оригиналния масив във всеки цикъл. Елементът от кофата се изтрива, след като бъде копиран в оригиналния масив. Съберете елементи от всяка кофа

Алгоритъм за сортиране на кофата

 bucketSort () създава N кофи, всяка от които може да съдържа диапазон от стойности за всички кофи, инициализира всяка кофа с 0 стойности за всички кофи, поставя елементи в кофи, съответстващи на обхвата за всички кофи, сортира елементи във всяка кофа, събира елементи от всяка кофа край кофа Сортирай

Примери за Python, Java и 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); )

Сложност

Най-лошата сложност: Когато в масива има елементи от близък обхват, те вероятно ще бъдат поставени в една и съща група. Това може да доведе до това, че някои групи имат по-голям брой елементи от други. Това прави сложността зависи от алгоритъма за сортиране, използван за сортиране на елементите на групата. Сложността става още по-лоша, когато елементите са в обратен ред. Ако сортирането на вмъкването се използва за сортиране на елементи от групата, тогава сложността на времето става .O(n²)

O(n²)
Най-добрата сложност: O(n+k)
Това се случва, когато елементите са равномерно разпределени в групите с почти равен брой елементи във всяка група.
Сложността става още по-добра, ако елементите вътре в кофите вече са сортирани.
Ако сортирането на вмъкване се използва за сортиране на елементи от група, тогава общата сложност в най-добрия случай ще бъде линейна, т.е. O(n+k). O(n)е сложността за направа на групите и O(k)е сложността за сортиране на елементите на групата с помощта на алгоритми с линейна времева сложност в най-добрия случай.
Средна сложност на случая: O(n)
Това се случва, когато елементите се разпределят произволно в масива. Дори ако елементите не са разпределени равномерно, сортирането на сегменти работи в линейно време. То е вярно, докато сумата от квадратите на размерите на кофата не е линейна в общия брой елементи.