Clasificación sin comparación de elementos

Dada una array con elementos enteros en un rango pequeño, ordene la array. Necesitamos escribir un algoritmo de clasificación no basado en comparación con las siguientes suposiciones sobre la entrada. 

1. Todas las entradas de la array son números enteros.
2. La diferencia entre el valor máximo y el valor mínimo en la array es menor o igual a 10^6.

Input : arr[] = {10, 30, 20, 4}
Output : 4 10 20 30

Input : arr[] = {10, 30, 1, 20, 4}
Output : 1 4 10 20 30

No se nos permite usar algoritmos de clasificación basados ​​en comparación como QuickSort , MergeSort , etc.
Dado que los elementos son pequeños, usamos elementos de array como índice. Almacenamos recuentos de elementos en una array de recuento. Una vez que tenemos la array de conteo, recorremos la array de conteo e imprimimos cada elemento presente sus tiempos de conteo.  

// C++ program to sort an array without comparison
// operator.
#include <bits/stdc++.h>
using namespace std;
 
int sortArr(int arr[], int n, int min, int max)
{
    // Count of elements in given range
    int m = max - min + 1;
     
    // Count frequencies of all elements
    vector<int> c(m, 0);
    for (int i=0; i<n; i++)
       c[arr[i] - min]++;
 
    // Traverse through range. For every
    // element, print it its count times.
    for (int i=0; i<m; i++)
        for  (int j=0; j < c[i]; j++)
          cout << (i + min) << " ";
}
 
// Driver Code
int main()
{
    int arr[] =  {10, 10, 1, 4, 4, 100, 0};
    int min = 0, max = 100;
    int n = sizeof(arr)/sizeof(arr[0]);
    sortArr(arr, n, min, max);
    return 0;
}

// Java program to sort an array without comparison
// operator.
import java.util.*;
 
// Represents node of a doubly linked list
class Node
{
 
    static void sortArr(int arr[], int n, int min, int max)
    {
        // Count of elements in given range
        int m = max - min + 1;
 
        // Count frequencies of all elements
        int[] c = new int[m];
        for (int i = 0; i < n; i++)
        {
            c[arr[i] - min]++;
        }
 
        // Traverse through range. For every
        // element, print it its count times.
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < c[i]; j++)
            {
                System.out.print((i + min) + " ");
            }
        }
    }
   
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = {10, 10, 1, 4, 4, 100, 0};
        int min = 0, max = 100;
        int n = arr.length;
        sortArr(arr, n, min, max);
    }
}
 
// This code is contributed by Princi Singh

# Python3 program to sort an array without comparison
# operator.
 
def sortArr(arr, n, min_no, max_no):
    # Count of elements in given range
    m = max_no - min_no + 1
     
    # Count frequencies of all elements
    c = [0] * m
    for i in range(n):
        c[arr[i] - min_no] += 1
 
    # Traverse through range. For every
    # element, print it its count times.
    for i in range(m):
        for j in range((c[i])):
            print((i + min_no), end=" ")
 
# Driver Code
arr = [10, 10, 1, 4, 4, 100, 0]
min_no,max_no = 0,100
n = len(arr)
sortArr(arr, n, min_no, max_no)
 
# This code is contributed by Rajput-Ji
# Improved by Rutvik J

// C# program to sort an array
// without comparison operator.
using System;
 
class GFG
{
     
    // Represents node of a doubly linked list
    static void sortArr(int []arr, int n,
                        int min, int max)
    {
        // Count of elements in given range
        int m = max - min + 1;
 
        // Count frequencies of all elements
        int[] c = new int[m];
        for (int i = 0; i < n; i++)
        {
            c[arr[i] - min]++;
        }
 
        // Traverse through range. For every
        // element, print it its count times.
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < c[i]; j++)
            {
                Console.Write((i + min) + " ");
            }
        }
    }
 
    // Driver Code
    static public void Main ()
    {
        int []arr = {10, 10, 1, 4, 4, 100, 0};
        int min = 0, max = 100;
        int n = arr.Length;
        sortArr(arr, n, min, max);
    }
}
 
// This code is contributed by ajit.

<script>
 
    // Javascript program to sort an array
    // without comparison operator.
     
    // Represents node of a doubly linked list
    function sortArr(arr, n, min, max)
    {
        // Count of elements in given range
        let m = max - min + 1;
  
        // Count frequencies of all elements
        let c = new Array(m);
        c.fill(0);
        for (let i = 0; i < n; i++)
        {
            c[arr[i] - min]++;
        }
  
        // Traverse through range. For every
        // element, print it its count times.
        for (let i = 0; i < m; i++)
        {
            for (let j = 0; j < c[i]; j++)
            {
                document.write((i + min) + " ");
            }
        }
    }
     
    let arr = [10, 10, 1, 4, 4, 100, 0];
    let min = 0, max = 100;
    let n = arr.length;
    sortArr(arr, n, min, max);
     
</script>

0 1 4 4 10 10 100

¿Qué es la complejidad del tiempo?  
La complejidad temporal del algoritmo anterior es O(n + (max-min))

¿Es estable el algoritmo anterior ?  
La implementación anterior no es estable ya que no nos importa el orden de los mismos elementos durante la clasificación.

¿Cómo hacer que el algoritmo anterior sea estable?  
La versión estable del algoritmo anterior se llama Counting Sort . Al ordenar por conteo, almacenamos sumas de todos los valores menores o iguales en c[i] para que c[i] almacene la posición real de i en una array ordenada. Después de llenar c[], recorremos la array de entrada nuevamente, colocamos cada elemento en su posición y decrementamos el conteo.

¿Qué son los algoritmos estándar que no se basan en la comparación?  
Clasificación por conteo , Clasificación por radix y Clasificación por cubetas .