Implementando Ordenar por conteo usando el mapa en C++

Counting Sort es uno de los mejores algoritmos de clasificación que puede clasificar en complejidad de tiempo O(n), pero la desventaja de la clasificación de conteo es su complejidad de espacio, para una pequeña colección de valores, también requerirá una gran cantidad de espacio no utilizado. Entonces, necesitamos dos cosas para superar esto:

1. Una estructura de datos que ocupa el espacio solo para elementos de entrada y no para todos los elementos que no sean entradas.
2. Los elementos almacenados deben estar ordenados porque si no está ordenado, almacenarlos no servirá de nada.

Entonces, Map en C++ satisface ambas condiciones. Por lo tanto, podemos lograr esto a través de un mapa. Ejemplos:

Entrada: arr[] = {1, 4, 3, 5, 1} Salida: 1 1 3 4 5 Entrada: arr[] = {1, -1, -3, 8, -3} Salida: -3 -3 -1 1 8

A continuación se muestra la implementación de Counting Sort usando map en C++: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to sort the array using counting sort
void countingSort(vector<int> arr, int n)
{
 
    // Map to store the frequency
    // of the array elements
    map<int, int> freqMap;
    for (auto i = arr.begin(); i != arr.end(); i++) {
        freqMap[*i]++;
    }
 
    int i = 0;
 
    // For every element of the map
    for (auto it : freqMap) {
 
        // Value of the element
        int val = it.first;
 
        // Its frequency
        int freq = it.second;
        for (int j = 0; j < freq; j++)
            arr[i++] = val;
    }
 
    // Print the sorted array
    for (auto i = arr.begin(); i != arr.end(); i++) {
        cout << *i << " ";
    }
}
 
// Driver code
int main()
{
    vector<int> arr = { 1, 4, 3, 5, 1 };
    int n = arr.size();
 
    countingSort(arr, n);
 
    return 0;
}

1 1 3 4 5

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(n)