Algoritmos de ordenamiento

Algoritmos de ordenamiento

Este post es complemento de mi artículo de algoritmos de ordenamiento en Linkedin, si aún no lo has visto clic aquí.

Aquí haremos una prueba sencilla de tiempo de ejecución al ordenar 1000000 de números y compararemos los resultados.

Burbuja: Complejidad O(n^2)

       public static int[]? burbuja(int[]? array)
        {
            int temp;
            for(int x = 0; x< array.Length -1; x++)
            {
                for(int y = 0; y < array.Length -1; y++)
                {
                    if (array[y] > array[y + 1])
                    {
                        temp = array[y];
                        array[y] = array[y + 1];
                        array[y + 1] = temp;
                    }
                }
            }

            return array;
         }

Tiempo de ejecución: 56.6 minutos

Conteo: Complejidad O(n+k)

public static int[]? conteo(int[]? arrayInput)
        {
            int valor;
            int valorEntrada;
            int valorAcumulado;
            int[]? arrayOutput = new int[arrayInput.Length];
            int[]? arrayAppearances = new int[arrayInput.Max()];
            int[]? arrayAccumulator = new int[arrayInput.Max()];

            for (int x = 0; x< arrayInput.Length; x++)
            {
                valor = arrayInput[x];
                arrayAppearances[valor -1] = arrayAppearances[valor - 1] + 1;
            }

            for(int x = 0; x< arrayAppearances.Length; x++)
            {
                if (x == 0)
                    arrayAccumulator[x] = arrayAppearances[x];
                else
                    arrayAccumulator[x] = arrayAppearances[x] + arrayAccumulator[x - 1];
            }


            for(int x = 0; x< arrayInput.Length; x++)
            {
                valorEntrada = arrayInput[x];
                valorAcumulado = arrayAccumulator[valorEntrada - 1];

                arrayOutput[valorAcumulado -1] = arrayInput[x];
                arrayAccumulator[valorEntrada -1] = valorAcumulado - 1;
            }

            return arrayOutput;
}

Tiempo de ejecución: 0.5 minutos

Rápido: Complejidad O(n log n)

public static int[]? rapido(int[]? array)
        {
            if (array.Length < 1)
                return array;
            if (array.Length <= 3)
                completado = true;

            int[]? left =  new int[0];
            int[]? right = new int[0];
            int[]? pivote = new int[1];
            int[]? result;
            pivote[0] = array[0];
            int contLeft = 1;
            int contRight = 1;
            for (int x = 1; x < array.Length; x++)
            {
                if (array[x] < pivote[0])
                {
                  
                    Array.Resize(ref left, left.Length + 1);
                    left[left.Length - 1] = array[x];
                    contLeft++;
                }

                else
                {
                    Array.Resize(ref right, right.Length + 1);
                    right[right.Length - 1] = array[x];
                    contRight++;
                }
            }

            return result = rapido(left).Concat(pivote).Concat(rapido(right)).ToArray();
        }

Tiempo de ejecución: 16 minutos

Como era de esperarse burbuja fue el tiempo más elevado, lo que me pareció raro fue que conteo tuviera un tiempo tan bajo incluso mejor que el del algoritmo rápido, por lo que estuve revisando paso a paso pero efectivamente el algoritmo regresaba el arreglo completamente ordenado así que su eficiencia es indiscutible.

Deja un comentario