Алгоритм сортування відра

У цьому підручнику ви дізнаєтесь, як працює сортування сегментів. Крім того, ви знайдете робочі приклади сортування сегментів у C, C ++, Java та Python.

Сортування сегмента - це техніка сортування, яка сортує елементи, попередньо розділивши елементи на кілька груп, які називаються сегментами . Елементи всередині кожного сегмента сортуються за допомогою будь-якого з відповідних алгоритмів сортування або рекурсивно викликають той самий алгоритм.

Створюється кілька відер. Кожне відро наповнене певним асортиментом елементів. Елементи всередині сегмента сортуються за допомогою будь-якого іншого алгоритму. Нарешті, елементи сегмента збираються, щоб отримати відсортований масив.

Процес сортування у відрі можна розуміти як підхід розсіяння . Спочатку елементи розсіюються по відрах, потім сортуються елементи відрів. Нарешті, елементи зібрані по порядку.

Працює сортування ковша

Як працює сортування відра?

Припустимо, вхідний масив: Вхідний масив
Створіть масив розміром 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 для всіх сегментів, вкласти елементи в сегменти, що відповідають діапазону для всіх сегментів, елементи сортування в кожному сегменті збирають елементи з кожного сегмента end 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(n²)

O(n²)
Складність найкращого випадку: O(n+k)
Це відбувається, коли елементи рівномірно розподіляються в сегментах з майже рівною кількістю елементів у кожному сегменті.
Складність стає ще кращою, якщо елементи всередині відрів вже відсортовані.
Якщо для сортування елементів сегмента використовується вставка сортування, то в кращому випадку загальна складність буде лінійною, тобто. O(n+k). O(n)- це складність виготовлення сегментів і O(k)є складність сортування елементів сегмента з використанням алгоритмів, що мають лінійну часову складність у найкращому випадку.
Середня складність справи: O(n)
Це відбувається, коли елементи розподіляються хаотично в масиві. Навіть якщо елементи розподілені не рівномірно, сортування в сегменті виконується за лінійний час. Це справедливо до тих пір, поки сума квадратів розмірів відра не буде лінійною у загальній кількості елементів.