Considere una array grande donde los elementos son de un conjunto pequeño y en cualquier rango, es decir, hay muchas repeticiones. ¿Cómo ordenar eficientemente la array?
Example:
Input: arr[] = {100, 12, 100, 1, 1, 12, 100, 1, 12, 100, 1, 1}
Output: arr[] = {1, 1, 1, 1, 1, 12, 12, 12, 100, 100, 100, 100}
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Un algoritmo de clasificación básico como MergeSort , HeapSort tomaría un tiempo O (nLogn) donde n es el número de elementos, ¿podemos hacerlo mejor?
Una mejor solución es utilizar el árbol de búsqueda binario autoequilibrado como AVL o Red-Black para ordenar en tiempo O(n Log m), donde m es el número de elementos distintos. La idea es extender el Node del árbol para que también tenga un recuento de claves.
struct Node
{
int key;
struct Node *left. *right;
int count; // Added to handle duplicates
// Other tree node info for balancing like height in AVL
}
A continuación se muestra el algoritmo completo utilizando el árbol AVL.
1) Cree un árbol AVL vacío con recuento como campo adicional.
2) Recorra la array de entrada y haga lo siguiente para cada elemento ‘arr[i]’
…..a) Si arr[i] no está presente en el árbol, insértelo e inicialice el conteo como 1
…..b) De lo contrario, incremente su conteo en árbol
3) Realice el recorrido del árbol en orden. Mientras lo hace en orden, ponga cada tecla su conteo de veces en arr[].
El segundo paso toma el tiempo O( n Log m) y el tercer paso toma el tiempo O(n). Entonces, la complejidad de tiempo general es O (n Log m)
A continuación se muestra la implementación en C++ de la idea anterior.
C++
// C++ program to sort an array using AVL tree
#include<iostream>
using namespace std;
// An AVL tree Node
struct Node
{
int key;
struct Node *left, *right;
int height, count;
};
// Function to insert a key in AVL Tree, if key is already present,
// then it increments count in key's node.
struct Node* insert(struct Node* Node, int key);
// This function puts inorder traversal of AVL Tree in arr[]
void inorder(int arr[], struct Node *root, int *index_ptr);
// An AVL tree based sorting function for sorting an array with
// duplicates
void sort(int arr[], int n)
{
// Create an empty AVL Tree
struct Node *root = NULL;
// Insert all nodes one by one in AVL tree. The insert function
// increments count if key is already present
for (int i=0; i<n; i++)
root = insert(root, arr[i]);
// Do inorder traversal to put elements back in sorted order
int index = 0;
inorder(arr, root, &index);
}
// This function puts inorder traversal of AVL Tree in arr[]
void inorder(int arr[], struct Node *root, int *index_ptr)
{
if (root != NULL)
{
// Recur for left child
inorder(arr, root->left, index_ptr);
// Put all occurrences of root's key in arr[]
for (int i=0; i<root->count; i++)
{
arr[*index_ptr] = root->key;
(*index_ptr)++;
}
// Recur for right child
inorder(arr, root->right, index_ptr);
}
}
// A utility function to get height of the tree
int height(struct Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
// Helper function that allocates a new Node
struct Node* newNode(int key)
{
struct Node* node = new Node;
node->key = key;
node->left = node->right = NULL;
node->height = node->count = 1;
return(node);
}
// A utility function to right rotate subtree rooted
// with y.
struct Node *rightRotate(struct Node *y)
{
struct Node *x = y->left;
struct Node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;
// Return new root
return x;
}
// A utility function to left rotate subtree rooted with x
struct Node *leftRotate(struct Node *x)
{
struct Node *y = x->right;
struct Node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
// Return new root
return y;
}
// Get Balance factor of Node N
int getBalance(struct Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
// Function to insert a key in AVL Tree, if key is already
// present, then it increments count in key's node.
struct Node* insert(struct Node* Node, int key)
{
/* 1. Perform the normal BST rotation */
if (Node == NULL)
return (newNode(key));
// If key already exists in BST, increment count and return
if (key == Node->key)
{
(Node->count)++;
return Node;
}
/* Otherwise, recur down the tree */
if (key < Node->key)
Node->left = insert(Node->left, key);
else
Node->right = insert(Node->right, key);
/* 2. Update height of this ancestor Node */
Node->height = max(height(Node->left), height(Node->right)) + 1;
/* 3. Get the balance factor of this ancestor Node to
check whether this Node became unbalanced */
int balance = getBalance(Node);
// If this Node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && key < Node->left->key)
return rightRotate(Node);
// Right Right Case
if (balance < -1 && key > Node->right->key)
return leftRotate(Node);
// Left Right Case
if (balance > 1 && key > Node->left->key)
{
Node->left = leftRotate(Node->left);
return rightRotate(Node);
}
// Right Left Case
if (balance < -1 && key < Node->right->key)
{
Node->right = rightRotate(Node->right);
return leftRotate(Node);
}
/* return the (unchanged) Node pointer */
return Node;
}
// A utility function to print an array
void printArr(int arr[], int n)
{
for (int i=0; i<n; i++)
cout << arr[i] << ", ";
cout << endl;
}
/* Driver program to test above function*/
int main()
{
int arr[] = {100, 12, 100, 1, 1, 12, 100, 1, 12, 100, 1, 1};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Input array is\n";
printArr(arr, n);
sort(arr, n);
cout << "Sorted array is\n";
printArr(arr, n);
}
Java
// Java program for insertion in AVL Tree
public class AvlTree
{
static Node root = null;
static class Node
{
int key, height, count;
Node left, right;
Node(int d)
{
key = d;
height = 1;
count = 1;
left = right = null;
}
}
// A utility function to get the height of the tree
int height(Node N)
{
if (N == null)
return 0;
return N.height;
}
// A utility function to get maximum of two integers
int max(int a, int b)
{
return (a > b) ? a : b;
}
// A utility function to right rotate subtree rooted with y
// See the diagram given above.
Node rightRotate(Node y)
{
Node x = y.left;
Node T2 = x.right;
// Perform rotation
x.right = y;
y.left = T2;
// Update heights
y.height = max(height(y.left), height(y.right)) + 1;
x.height = max(height(x.left), height(x.right)) + 1;
// Return new root
return x;
}
// A utility function to left rotate subtree rooted with x
// See the diagram given above.
Node leftRotate(Node x)
{
Node y = x.right;
Node T2 = y.left;
// Perform rotation
y.left = x;
x.right = T2;
// Update heights
x.height = max(height(x.left), height(x.right)) + 1;
y.height = max(height(y.left), height(y.right)) + 1;
// Return new root
return y;
}
// Get Balance factor of node N
int getBalance(Node N)
{
if (N == null)
return 0;
return height(N.left) - height(N.right);
}
Node insert(Node node, int key)
{
/* 1. Perform the normal BST insertion */
if (node == null)
return (new Node(key));
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
// Duplicate keys not allowed
else
{
node.count++;
return node;
}
/* 2. Update height of this ancestor node */
node.height = 1 + max(height(node.left),
height(node.right));
/* 3. Get the balance factor of this ancestor
node to check whether this node became
unbalanced */
int balance = getBalance(node);
// If this node becomes unbalanced, then there
// are 4 cases Left Left Case
if (balance > 1 && key < node.left.key)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key > node.right.key)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node.left.key)
{
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < node.right.key)
{
node.right = rightRotate(node.right);
return leftRotate(node);
}
/* return the (unchanged) node pointer */
return node;
}
// inorder traversal in BST always give sorted
// order. Put the sorted elements back into the array
int inorder(Node n, int arr[], int i)
{
if (n != null)
{
i = inorder(n.left, arr, i);
for(int j = 0; j < n.count; j++)
{
arr[i] = n.key;
i++;
}
i = inorder(n.right, arr, i);
}
return i;
}
// Driver code
public static void main(String[] args)
{
// TODO Auto-generated method stub
int arr[] = {100, 12, 100, 1, 1, 12, 100, 1, 12, 100, 1, 1};
System.out.println("Input array ");
for (int i = 0; i < arr.length; i++)
System.out.print(" "+ arr[i]);
AvlTree at= new AvlTree();
// insert all element in AVL tree
for (int i = 0; i < arr.length; i++)
root = at.insert(root, arr[i]);
// Do inorder traversal to put
// elements back in sorted order
int index = 0;
at.inorder(root, arr, index);
System.out.println("\nOutput array ");
for (int i = 0; i < arr.length; i++)
System.out.print(" "+ arr[i]);
}
}
// This code is contributed by moonishussain
C#
// C# program for insertion in AVL Tree
using System;
public class AvlTree
{
static Node root = null;
public class Node {
public int key, height, count;
public Node left, right;
public Node(int d) {
key = d;
height = 1;
count = 1;
left = right = null;
}
}
// A utility function to get the height of the tree
int height(Node N) {
if (N == null)
return 0;
return N.height;
}
// A utility function to get maximum of two integers
int max(int a, int b) {
return (a > b) ? a : b;
}
// A utility function to right rotate subtree rooted with y
// See the diagram given above.
Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
// Perform rotation
x.right = y;
y.left = T2;
// Update heights
y.height = max(height(y.left), height(y.right)) + 1;
x.height = max(height(x.left), height(x.right)) + 1;
// Return new root
return x;
}
// A utility function to left rotate subtree rooted with x
// See the diagram given above.
Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;
// Perform rotation
y.left = x;
x.right = T2;
// Update heights
x.height = max(height(x.left), height(x.right)) + 1;
y.height = max(height(y.left), height(y.right)) + 1;
// Return new root
return y;
}
// Get Balance factor of node N
int getBalance(Node N) {
if (N == null)
return 0;
return height(N.left) - height(N.right);
}
Node insert(Node node, int key) {
/* 1. Perform the normal BST insertion */
if (node == null)
return (new Node(key));
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
// Duplicate keys not allowed
else {
node.count++;
return node;
}
/* 2. Update height of this ancestor node */
node.height = 1 + max(height(node.left), height(node.right));
/*
* 3. Get the balance factor of this ancestor node to check whether this node
* became unbalanced
*/
int balance = getBalance(node);
// If this node becomes unbalanced, then there
// are 4 cases Left Left Case
if (balance > 1 && key < node.left.key)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key > node.right.key)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
/* return the (unchanged) node pointer */
return node;
}
// inorder traversal in BST always give sorted
// order. Put the sorted elements back into the array
int inorder(Node n, int []arr, int i) {
if (n != null) {
i = inorder(n.left, arr, i);
for (int j = 0; j < n.count; j++) {
arr[i] = n.key;
i++;
}
i = inorder(n.right, arr, i);
}
return i;
}
// Driver code
public static void Main(String[] args)
{
// TODO Auto-generated method stub
int []arr = { 100, 12, 100, 1, 1, 12, 100, 1, 12, 100, 1, 1 };
Console.WriteLine("Input array ");
for (int i = 0; i < arr.Length; i++)
Console.Write(" " + arr[i]);
AvlTree at = new AvlTree();
// insert all element in AVL tree
for (int i = 0; i < arr.Length; i++)
root = at.insert(root, arr[i]);
// Do inorder traversal to put
// elements back in sorted order
int index = 0;
at.inorder(root, arr, index);
Console.WriteLine("\nOutput array ");
for (int i = 0; i < arr.Length; i++)
Console.Write(" " + arr[i]);
}
}
// This code is contributed by gauravrajput1
Producción:
Input array is 100, 12, 100, 1, 1, 12, 100, 1, 12, 100, 1, 1, Sorted array is 1, 1, 1, 1, 1, 12, 12, 12, 100, 100, 100, 100,
También podemos usar Binary Heap para resolver en tiempo O(n Log m).
También podemos usar Hashing para resolver el problema anterior en tiempo O (n + m Log m) .
1) Crea una tabla hash vacía. Los valores de array de entrada se almacenan como clave y sus recuentos se almacenan como valor en la tabla hash.
2) Para cada elemento ‘x’ de arr[], haga lo siguiente
… a) Si x ix está presente en la tabla hash, incremente su valor
… b) De lo contrario, inserte x con valor igual a 1.
3) Considere todas las claves de la tabla hash y ordenarlos.
4) Recorra todas las claves ordenadas e imprima cada clave por su valor.
Complejidad temporal de 2ºel paso es O (n) bajo el supuesto de que la búsqueda de hash y la inserción toman el tiempo O (1). El paso 3 toma el tiempo O(m Log m) donde m es el número total de claves distintas en la array de entrada. El paso 4 toma el tiempo O(n). Entonces, la complejidad del tiempo total es O (n + m Log m).
Implementación del programa utilizando Hash Table
C
// A C++ program to sort a big array with many repetitions
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
void sort(int arr[], int n)
{
//1. Create an empty hash table.
map<int, int> count;
//2. Input array values are stores as key and their
//counts are stored as value in hash table.
for (int i=0; i<n; i++)
count[arr[i]]++;
map<int, int>::iterator it;
int index = 0;
//3. Consider all keys of hash table and sort them.
//In std::map, keys are already sorted.
//4. Traverse all sorted keys and print every key its value times.
for (it=count.begin(); it!=count.end(); ++it)
{
while(it->second--)
arr[index++]=it->first;
}
}
// Utility function to print an array
void printArray(int arr[], int n)
{
for (int i=0; i<n; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver program to test above function.
int main()
{
int arr[] = {100, 12, 100, 1, 1, 12, 100, 1, 12, 100, 1, 1};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Input array is\n";
printArray(arr, n);
sort(arr, n);
cout << "Sorted array is\n";
printArray(arr, n);
return 0;
}
// Contributed by Aditya Goel
Producción:
Input array is 100 12 100 1 1 12 100 1 12 100 1 1 Sorted array is 1 1 1 1 1 12 12 12 100 100 100 100
Este artículo es una contribución de Ankur. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA