Алгоритм сортировки ведра

В этом руководстве вы узнаете, как работает сортировка по сегментам. Также вы найдете рабочие примеры сортировки по корзинам на C, C ++, Java и Python.

Сортировка по сегментам - это метод сортировки, который сортирует элементы, сначала разделяя элементы на несколько групп, называемых сегментами . Элементы внутри каждой корзины сортируются с использованием любого подходящего алгоритма сортировки или рекурсивного вызова одного и того же алгоритма.

Создается несколько ведер. Каждое ведро заполнено определенным набором элементов. Элементы внутри корзины сортируются с использованием любого другого алгоритма. Наконец, элементы корзины собираются, чтобы получить отсортированный массив.

Процесс сортировки ведром можно понять как метод разброса-сбора . Элементы сначала раскладываются по ведрам, затем элементы ведер сортируются. Наконец, элементы собраны по порядку.

Работа ковшей сортировки

Как работает Bucket Sort?

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

Алгоритм сортировки ведра

 ведро конец bucketSort

Примеры 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(n2)

    O(n2)
  • Наилучшая сложность случая: O(n+k)
    это происходит, когда элементы равномерно распределены в сегментах с примерно равным количеством элементов в каждом сегменте.
    Сложность становится еще лучше, если элементы внутри ведер уже отсортированы.
    Если сортировка вставкой используется для сортировки элементов корзины, то общая сложность в лучшем случае будет линейной, т.е. O(n+k). O(n)- сложность создания корзин и O(k)сложность сортировки элементов корзины с использованием алгоритмов, имеющих линейную временную сложность в лучшем случае.
  • Средняя сложность кейса: O(n)
    это происходит, когда элементы случайным образом распределяются в массиве. Даже если элементы распределены неравномерно, сортировка ведра выполняется за линейное время. Это верно до тех пор, пока сумма квадратов размеров ведра не станет линейной по общему количеству элементов.

Приложения для сортировки по сегменту

Сортировка по ведру используется, когда:

  • ввод равномерно распределяется по диапазону.
  • есть значения с плавающей запятой

Интересные статьи...