Algoritmo de classificação de intervalo

Neste tutorial, você aprenderá como funciona a classificação de intervalos. Além disso, você encontrará exemplos de trabalho de classificação de bucket em C, C ++, Java e Python.

Bucket Sort é uma técnica de classificação que classifica os elementos, primeiro dividindo os elementos em vários grupos chamados buckets . Os elementos dentro de cada intervalo são classificados usando qualquer um dos algoritmos de classificação adequados ou chamando recursivamente o mesmo algoritmo.

Vários depósitos são criados. Cada balde é preenchido com um intervalo específico de elementos. Os elementos dentro do intervalo são classificados usando qualquer outro algoritmo. Finalmente, os elementos do balde são reunidos para obter a matriz classificada.

O processo de classificação do balde pode ser entendido como uma abordagem de coleta dispersa . Os elementos são primeiro espalhados em baldes e, em seguida, os elementos de baldes são classificados. Finalmente, os elementos são reunidos em ordem.

Trabalho de classificação de balde

Como funciona a classificação de intervalos?

Suponha que a matriz de entrada seja: Matriz de entrada
Crie uma matriz de tamanho 10. Cada slot dessa matriz é usado como um balde para armazenar elementos. Matriz em que cada posição é um balde
Insira elementos nos baldes da matriz. Os elementos são inseridos de acordo com o alcance do balde.
Em nosso código de exemplo, temos intervalos de 0 a 1, 1 a 2, 2 a 3, … (n-1) a n.
Suponha que um elemento de entrada .23seja usado. É multiplicado por size = 10(ou seja .23*10=2.3). Em seguida, ele é convertido em um número inteiro (ou seja, 2.3≈2). Finalmente, 0,23 é inserido no balde-2 . Insira elementos nos baldes da matriz
Da mesma forma, 0,25 também é inserido no mesmo balde. Toda vez, o valor mínimo do número de ponto flutuante é obtido.
Se tomarmos números inteiros como entrada, temos que dividi-los pelo intervalo (10 aqui) para obter o valor mínimo.
Da mesma forma, outros elementos são inseridos em seus respectivos baldes. Insira todos os elementos nos baldes da matriz
Os elementos de cada intervalo são classificados usando qualquer um dos algoritmos de classificação estáveis. Aqui, usamos quicksort (função embutida). Classifique os elementos em cada intervalo
Os elementos de cada balde são reunidos.
Isso é feito iterando através do balde e inserindo um elemento individual no array original em cada ciclo. O elemento do balde é apagado assim que é copiado para a matriz original. Reúna os elementos de cada balde

Algoritmo de classificação de intervalo

 bucketSort () cria N buckets, cada um dos quais pode conter um intervalo de valores para todos os buckets inicializar cada bucket com 0 valores para todos os buckets colocar elementos em buckets que correspondem ao intervalo de todos os buckets sort elementos em cada bucket reúnem elementos de cada bucket fim bucketSort

Exemplos de Python, Java e 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); )

Complexidade

Pior caso de complexidade: quando há elementos próximos na matriz, é provável que sejam colocados no mesmo balde. Isso pode resultar em alguns intervalos com mais número de elementos do que outros. Faz com que a complexidade dependa do algoritmo de classificação usado para classificar os elementos do intervalo. A complexidade fica ainda pior quando os elementos estão na ordem inversa. Se a classificação por inserção for usada para classificar os elementos do intervalo, a complexidade do tempo se tornará .O(n²)

O(n²)
Melhor caso de complexidade: O(n+k)
ocorre quando os elementos são uniformemente distribuídos nos segmentos com um número quase igual de elementos em cada segmento.
A complexidade fica ainda melhor se os elementos dentro dos baldes já estiverem classificados.
Se a classificação por inserção for usada para classificar os elementos de um intervalo, a complexidade geral no melhor caso será linear, ou seja. O(n+k). O(n)é a complexidade para fazer os baldes e O(k)é a complexidade para classificar os elementos do balde usando algoritmos com complexidade de tempo linear no melhor caso.
Complexidade média do caso: O(n)
ocorre quando os elementos são distribuídos aleatoriamente no array. Mesmo que os elementos não sejam distribuídos de maneira uniforme, a classificação do intervalo é executada em tempo linear. Isso é válido até que a soma dos quadrados dos tamanhos dos baldes seja linear no número total de elementos.