Ordenar Arrays

En este artículo vamos a explicar los métodos para ordenar Arrays más comunes y utilizados en programación. Como hablamos de métodos, pueden ser implementados en cualquier lenguaje de programación pero en este artículo vamos a escribirlos en lenguaje PHP.

Hay varios métodos para ordenar Arrays, cada uno con sus ventajas y desventajas, estos son algunos de los más conocidos:

• Burbuja (Bubble Sort): Compara elementos adyacentes y los intercambia si están en el orden incorrecto. Repite el proceso hasta que no se necesitan más intercambios.
• Inserción (Insertion Sort): Construye una lista ordenada de elementos a partir del primer elemento, insertando cada nuevo elemento en su lugar correcto.
• Selección (Selection Sort): Divide el array en dos partes: una sublista desordenada y una sublista ordenada. Encuentra el elemento más pequeño en la sublista desordenada y lo intercambia con el primer elemento de la sublista ordenada, haciendo crecer la lista ordenada.
• Fusión (Merge Sort): Divide recursivamente el array en mitades más pequeñas, las ordena y luego las fusiona para producir un único array ordenado.
• Rápido (Quick Sort): Elige un elemento pivote y divide el array en dos subarrays según si son menores o mayores que el pivote. Luego, aplica recursivamente el mismo proceso a los subarrays.
• Heap Sort: Convierte el array en un heap binario y luego extrae repetidamente el elemento máximo (para ordenación ascendente) del heap, dejando el heap más pequeño para el siguiente paso.

Estos son los métodos para ordenar Arrays más comunes, cada uno con sus propias características y eficiencia en términos de tiempo y espacio. La elección de un algoritmo u otro depende de varios factores, y para ello vamos a realizar una comparativa al final del artículo, para que sea más fácil elegir uno u otro, según las necesidades.

Ordenar Arrays con burbuja (Bubble Sort)

Dentro de los métodos para ordenar Arrays, el ordenamiento burbuja, también conocido como bubble sort en inglés, es uno de los algoritmos más simples y básicos. Funciona comparando repetidamente pares de elementos adyacentes en el array y los intercambia si están en el orden incorrecto. Este proceso se repite hasta que no se necesitan más intercambios, lo que significa que el array está completamente ordenado. El nombre «burbuja» viene de la forma en que los elementos más grandes «burbujean» gradualmente hacia la parte superior del array, como las burbujas en un vaso de refresco.

La explicación paso a paso del algoritmo de ordenamiento burbuja es la siguiente:

• Compara los elementos adyacentes: Comienza desde el primer elemento (índice 0) y compara cada elemento con su sucesor adyacente.
• Intercambia si están en el orden incorrecto: Si el elemento actual es mayor que su sucesor, los intercambia. Esto coloca el elemento más grande más cerca del final del array.
• Repite hasta que esté completamente ordenado: Este proceso se repite para cada par de elementos adyacentes en el array. Después de cada pasada, el elemento más grande se mueve hacia el final del array. El proceso se repite hasta que no se necesiten más intercambios, lo que significa que el array está ordenado.

Algoritmo de ordenación burbuja

<?php
function bubbleSort($arr) {
    $n = count($arr);
    // Iterar sobre todos los elementos del array
    for ($i = 0; $i < $n - 1; $i++) {
        // Últimos $i elementos ya están en su lugar correcto
        // Iterar de 0 a $n-$i-1
        for ($j = 0; $j < $n - $i - 1; $j++) {
            // Comparar elementos adyacentes
            if ($arr[$j] > $arr[$j + 1]) {
                // Intercambiar si están en el orden incorrecto
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

// Ejemplo de uso
$arr = [64, 34, 0, 25, -12, 22, 11, 90, 3];
echo "Array original: ";
print_r($arr);
echo "Array ordenado usando Bubble Sort: ";
print_r(bubbleSort($arr));
?>

En este ejemplo, definimos una función llamada bubbleSort que toma un array como entrada y devuelve el array ordenado utilizando el algoritmo de ordenamiento burbuja. La función utiliza dos bucles for anidados para comparar y intercambiar elementos adyacentes según sea necesario. Una vez que se completa el algoritmo, se devuelve el array ordenado.

Al ejecutar este código, obtendrás el array original y el array ordenado utilizando el método de ordenamiento burbuja.

Ordenar Arrays con inserción (Insertion Sort)

Otro de los métodos para ordenar Arrays más conocido, es el método de ordenamiento por inserción, también conocido como insertion sort en inglés, es un algoritmo de ordenación eficiente y simple. Funciona de manera similar a cómo muchas personas ordenan cartas de juego en sus manos: uno a la vez. Comienza con un subarray ordenado de tamaño 1 y, a medida que avanza, inserta cada elemento restante en su posición correcta dentro del subarray ordenado.

La explicación detallada del algoritmo de ordenamiento por inserción es la siguiente:

• Subarray inicialmente ordenado: Comienza considerando el primer elemento del array como un subarray ordenado de tamaño 1.
• Iteración a través del array: A partir del segundo elemento del array, itera sobre cada elemento restante.
• Inserción en el subarray ordenado: Para cada elemento restante lo compara con los elementos del subarray ordenado.
• Si el elemento es menor que el elemento actual del subarray, desplaza el elemento actual hacia la derecha.
• Repite este proceso hasta encontrar la posición correcta para insertar el elemento.
• Elemento insertado en su posición correcta: Una vez que se encuentra la posición correcta, inserta el elemento en esa posición en el subarray ordenado.
• Repetición hasta que esté completamente ordenado: Repite este proceso para cada elemento restante en el array original. Después de completar todas las iteraciones, el array estará completamente ordenado.

Algoritmo de ordenación por inserción

<?php
function insertionSort($arr) {
    $n = count($arr);
    // Iterar sobre todos los elementos del array
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        // Mover los elementos del array que son mayores que $key
        // a una posición adelante de su posición actual
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j = $j - 1;
        }
        $arr[$j + 1] = $key;
    }
    return $arr;
}

// Ejemplo de uso
$arr = [64, 34, 0, 25, -12, 22, 11, 90, 3];
echo "Array original: ";
print_r($arr);
echo "Array ordenado usando Insertion Sort: ";
print_r(insertionSort($arr));
?>

En este ejemplo, definimos una función llamada insertionSort que toma un array como entrada y devuelve el array ordenado utilizando el algoritmo de ordenamiento por inserción. La función utiliza un bucle for para iterar sobre todos los elementos del array, comenzando desde el segundo elemento. Dentro del bucle, se compara cada elemento con los elementos anteriores en el subarray ordenado y se inserta en la posición correcta. Una vez que se completa el algoritmo, se devuelve el array ordenado.

Al ejecutar este código, obtendrás el array original y el array ordenado utilizando el método de ordenamiento por inserción.

Ordenar Arrays con selección (Selection Sort)

El método de ordenación por selección, también conocido como selection sort en inglés, es un algoritmo simple de ordenamiento que divide la lista en dos partes: una sublista ordenada y una sublista desordenada. En cada iteración, el algoritmo busca el elemento más pequeño de la sublista desordenada y lo intercambia con el primer elemento de la sublista ordenada. De esta manera, la sublista ordenada crece en una unidad con cada iteración.

La explicación detallada del algoritmo de ordenamiento por selección es la siguiente:

• Sublista ordenada y sublista desordenada: Inicialmente, el algoritmo considera todo el array como una sublista desordenada. A medida que avanza, divide el array en una sublista ordenada y una sublista desordenada.
• Búsqueda del elemento más pequeño: En cada iteración, el algoritmo busca el elemento más pequeño en la sublista desordenada.
• Intercambio con el primer elemento de la sublista desordenada: Una vez que se encuentra el elemento más pequeño, se intercambia con el primer elemento de la sublista ordenada.
• Expansión de la sublista ordenada: Después del intercambio, el primer elemento de la sublista desordenada se convierte en el último elemento de la sublista ordenada.
• Repetición hasta que esté completamente ordenado: Este proceso se repite hasta que la sublista desordenada se vacíe por completo, lo que significa que todo el array está ordenado.

Algoritmo de ordenación por selección

<?php
function selectionSort($arr) {
    $n = count($arr);
    // Iterar sobre todos los elementos del array
    for ($i = 0; $i < $n - 1; $i++) {
        // Encontrar el índice del elemento más pequeño en la sublista desordenada
        $min_index = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$j] < $arr[$min_index]) {
                $min_index = $j;
            }
        }
        // Intercambiar el elemento más pequeño con el primer elemento de la sublista ordenada
        $temp = $arr[$min_index];
        $arr[$min_index] = $arr[$i];
        $arr[$i] = $temp;
    }
    return $arr;
}

// Ejemplo de uso
$arr = [64, 34, 0, 25, -12, 22, 11, 90, 3];
echo "Array original: ";
print_r($arr);
echo "Array ordenado usando Selection Sort: ";
print_r(selectionSort($arr));
?>

En este ejemplo, definimos una función llamada selectionSort que toma un array como entrada y devuelve el array ordenado utilizando el algoritmo de ordenamiento por selección. La función utiliza dos bucles for: uno para iterar sobre todos los elementos del array y otro para encontrar el elemento más pequeño en la sublista desordenada. Después de encontrar el elemento más pequeño, se intercambia con el primer elemento de la sublista ordenada. Este proceso se repite hasta que todo el array esté ordenado.

Al ejecutar este código, obtendrás el array original y el array ordenado utilizando el método de ordenamiento por selección.

Ordenar Arrays con fusión (Merge Sort)

El método de ordenación por fusión, también conocido como merge sort en inglés, es un algoritmo de ordenamiento eficiente que utiliza la técnica de dividir para ordenar una lista de elementos. Funciona dividiendo repetidamente la lista en mitades más pequeñas, ordenando cada mitad de forma recursiva y luego fusionando las mitades ordenadas para obtener la lista final ordenada.

La explicación detallada del algoritmo de ordenamiento por fusión es la siguiente:

• Dividir la lista en mitades: El algoritmo comienza dividiendo la lista original en mitades más pequeñas hasta que cada sublista contenga un solo elemento. Esto se logra dividiendo la lista por la mitad de manera recursiva.
• Ordenar las mitades de manera recursiva: Una vez que se han creado todas las sublistas individuales, el algoritmo comienza a fusionarlas en orden. Para esto, las sublistas se ordenan de manera recursiva utilizando el mismo algoritmo de fusión.
• Fusionar las sublistas ordenadas: Finalmente, las sublistas ordenadas se fusionan para formar una única lista ordenada. Durante la fusión, se compara el primer elemento de cada sublista y se coloca el elemento más pequeño en la posición correcta en la lista resultante. Este proceso se repite hasta que se hayan fusionado todas las sublistas.

El algoritmo de fusión es eficiente y tiene un tiempo de ejecución de O(n log n), lo que lo hace adecuado para ordenar grandes conjuntos de datos.

Algoritmo de ordenación por fusión

<?php
function mergeSort($arr) {
    $n = count($arr);
    if ($n <= 1) {
        return $arr;
    }
    // Dividir la lista en dos mitades
    $middle = (int) ($n / 2);
    $left = array_slice($arr, 0, $middle);
    $right = array_slice($arr, $middle);
    // Ordenar recursivamente las mitades
    $left = mergeSort($left);
    $right = mergeSort($right);
    // Fusionar las sublistas ordenadas
    return merge($left, $right);
}

function merge($left, $right) {
    $result = [];
    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }
    // Agregar los elementos restantes de las sublistas
    while (count($left) > 0) {
        $result[] = array_shift($left);
    }
    while (count($right) > 0) {
        $result[] = array_shift($right);
    }
    return $result;
}

// Ejemplo de uso
$arr = [64, 34, 0, 25, -12, 22, 11, 90, 3];
echo "Array original: ";
print_r($arr);
echo "Array ordenado usando Merge Sort: ";
print_r(mergeSort($arr));
?>

En este ejemplo, definimos dos funciones: mergeSort y merge. La función mergeSort toma un array como entrada y devuelve el array ordenado utilizando el algoritmo de ordenamiento por fusión. En la función merge, se fusionan dos sublistas ordenadas en una sola lista ordenada. Finalmente, al ejecutar el código, obtenemos el array original y el array ordenado utilizando el método de ordenamiento por fusión.

Ordenar Arrays con método rápido (Quick Sort)

Dentro de los métodos para ordenar Arrays, el método de ordenamiento rápido, también conocido como quicksort en inglés, es un algoritmo de ordenación eficaz que utiliza la técnica de dividir para ordenar una lista de elementos. Funciona seleccionando un elemento como pivote y particionando la lista alrededor del pivote, de modo que los elementos más pequeños que el pivote estén a su izquierda y los elementos más grandes estén a su derecha. Luego, se repite este proceso recursivamente en las sublistas resultantes hasta que toda la lista esté ordenada.

La explicación detallada del algoritmo de ordenamiento rápido es la siguiente:

• Seleccionar un pivote: El algoritmo selecciona un elemento de la lista como pivote. El pivote puede elegirse de varias maneras, como tomar el primer elemento, el último elemento o un elemento aleatorio. En este ejemplo, seleccionaremos el último elemento como pivote.
• Particionar la lista alrededor del pivote: Después de seleccionar el pivote, el algoritmo recorre la lista y reorganiza los elementos de manera que los elementos más pequeños que el pivote estén a su izquierda y los elementos más grandes estén a su derecha. Este proceso se conoce como particionamiento.
• Aplicar el algoritmo recursivamente a las sublistas: Una vez que la lista ha sido particionada, se aplican recursivamente los mismos pasos de selección de pivote y particionamiento a las sublistas izquierda y derecha del pivote.
• Combinar las sublistas ordenadas: Finalmente, se combinan las sublistas ordenadas para formar la lista completa ordenada.

El algoritmo de ordenamiento rápido es altamente eficiente y tiene un tiempo de ejecución promedio de O(n log n). Sin embargo, en el peor de los casos, puede tener un tiempo de ejecución de O(n^2) si el pivote se elige de manera subóptima y la lista está casi ordenada.

Algoritmo de ordenación rápido

<?php
function quickSort($arr) {
    $n = count($arr);
    if ($n <= 1) {
        return $arr;
    }
    // Seleccionar el último elemento como pivote
    $pivot = $arr[$n - 1];
    $left = $right = [];
    // Particionar la lista alrededor del pivote
    for ($i = 0; $i < $n - 1; $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    // Aplicar recursivamente el algoritmo a las sublistas izquierda y derecha
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

// Ejemplo de uso
$arr = [64, 34, 0, 25, -12, 22, 11, 90, 3];
echo "Array original: ";
print_r($arr);
echo "Array ordenado usando Quick Sort: ";
print_r(quickSort($arr));
?>

En este ejemplo, definimos una función quickSort que toma un array como entrada y devuelve el array ordenado utilizando el algoritmo de ordenamiento rápido. Dentro de la función, seleccionamos el último elemento como pivote y particionamos la lista alrededor del pivote. Luego, aplicamos recursivamente el algoritmo a las sublistas izquierda y derecha del pivote y combinamos las sublistas ordenadas para obtener el array final ordenado. Finalmente, al ejecutar el código, obtenemos el array original y el array ordenado utilizando el método de ordenamiento rápido.

Ordenar Arrays con Heap Sort

Heap Sort es un algoritmo para ordenar Arrays eficiente que utiliza una estructura de datos de heap para organizar los elementos en la lista. Funciona transformando la lista en un heap, que es una forma especial de árbol binario completo donde cada nodo padre es mayor (en el caso de un heap max) o menor (en el caso de un heap min) que sus hijos. Luego, el algoritmo extrae repetidamente el elemento máximo (en el caso de un heap max) o mínimo (en el caso de un heap min) del heap y lo coloca al final de la lista ordenada. Este proceso se repite hasta que todos los elementos hayan sido extraídos y la lista esté completamente ordenada.

La explicación detallada del algoritmo de ordenación Heap Sort es la siguiente:

• Crear un heap inicial: El algoritmo comienza transformando la lista de elementos en un heap. Esto se logra tratando la lista como un árbol binario completo y realizando un ajuste hacia abajo (heapify) en cada nodo interno para garantizar que el árbol cumpla con la propiedad de heap.
• Extraer elementos del heap: Una vez que se ha creado el heap, el algoritmo extrae repetidamente el elemento raíz del heap (que es el máximo o mínimo, dependiendo del tipo de heap) y lo coloca al final de la lista ordenada. Luego, se ajusta el heap para restaurar la propiedad de heap.
• Repetir hasta que el heap esté vacío: Este proceso de extracción se repite hasta que todos los elementos hayan sido extraídos del heap y la lista esté completamente ordenada.

Heap Sort tiene un tiempo de ejecución promedio de O(n log n) en todos los casos y es in-place, lo que significa que no requiere almacenamiento adicional fuera de la lista original.

Algoritmo de ordenación Heap Sort

<?php
function heapSort(&$arr) {
    $n = count($arr);
    // Construir el heap inicial
    for ($i = (int)($n / 2) - 1; $i >= 0; $i--) {
        heapify($arr, $n, $i);
    }
    // Extraer elementos del heap uno por uno
    for ($i = $n - 1; $i > 0; $i--) {
        // Mover el elemento raíz actual al final de la lista
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;
        // Llamar a heapify en la lista reducida
        heapify($arr, $i, 0);
    }
}

// Función para realizar el ajuste hacia abajo en un nodo específico
function heapify(&$arr, $n, $i) {
    $largest = $i; // Inicializar el nodo más grande como raíz
    $left = 2 * $i + 1; // Índice del hijo izquierdo
    $right = 2 * $i + 2; // Índice del hijo derecho
    // Comprobar si el hijo izquierdo es mayor que el nodo raíz
    if ($left < $n && $arr[$left] > $arr[$largest]) {
        $largest = $left;
    }
    // Comprobar si el hijo derecho es mayor que el nodo raíz
    if ($right < $n && $arr[$right] > $arr[$largest]) {
        $largest = $right;
    }
    // Si el nodo más grande no es el nodo raíz, intercambiarlos y realizar heapify en el nodo más grande
    if ($largest != $i) {
        $temp = $arr[$i];
        $arr[$i] = $arr[$largest];
        $arr[$largest] = $temp;
        heapify($arr, $n, $largest);
    }
}

// Ejemplo de uso
$arr = [64, 34, 0, 25, -12, 22, 11, 90, 3];
echo "Array original: ";
print_r($arr);
heapSort($arr);
echo "Array ordenado usando Heap Sort: ";
print_r($arr);
?>

En este ejemplo, definimos una función heapSort que toma un array como referencia y lo ordena utilizando el algoritmo Heap Sort. Dentro de la función heapSort, construimos el heap inicial llamando a la función heapify en cada nodo interno del árbol. Luego, extraemos repetidamente el elemento raíz del heap y lo movemos al final de la lista, llamando a heapify en la lista reducida después de cada extracción. La función heapify realiza un ajuste hacia abajo en un nodo específico para asegurar que el árbol cumpla con la propiedad de heap. Finalmente, al ejecutar el código, obtenemos el array original y el array ordenado utilizando el método de Heap Sort.

Comparativa de técnicas para ordenar de Arrays

Una vez vistos los métodos para ordenar Arrays más comunes, podemos observar que cada método tiene sus propias características y es más adecuado para diferentes situaciones dependiendo del tamaño de los datos, la estabilidad requerida y otros factores específicos del problema.

En términos de rapidez, los métodos de ordenamiento pueden variar significativamente dependiendo del tamaño de los datos y de su distribución. La forma de medir el rendimiento de los algoritmos se realiza mendiante notación Big-O.

Veamos una comparativa entre todos los métodos de ordenación de Arrays explicados con sus ventajas y desventajas:

Ordenación burbuja (Bubble Sort)

• Ventajas:
  • Es simple y fácil de implementar.
  • Es eficiente para listas pequeñas o casi ordenadas.
• Desventajas:
  • Tiene una complejidad temporal alta, O(n^2), lo que lo hace ineficiente para listas grandes.
  • No es adecuado para listas inversamente ordenadas.
• Rendimiento:
  • Es uno de los métodos más lentos, especialmente para listas grandes.
  • Tiene una complejidad temporal de O(n^2) en el peor y mejor caso.

Ordenación por inserción (Insertion Sort)

• Ventajas:
  • Es eficiente para listas pequeñas o casi ordenadas.
  • Es estable y puede ser implementado de forma iterativa o recursiva.
• Desventajas:
  • Tiene una complejidad temporal alta, O(n^2), lo que lo hace ineficiente para listas grandes.
  • No es adecuado para listas inversamente ordenadas.
• Rendimiento:
  • Es más eficiente que el Bubble Sort, pero aún así puede ser lento para listas grandes.
  • Tiene una complejidad temporal de O(n^2) en el peor caso, pero puede ser O(n) en el mejor caso si la lista está casi ordenada.

Ordenación por selección (Selection Sort)

• Ventajas:
  • Es simple y fácil de implementar.
  • Tiene un uso eficiente de la memoria.
• Desventajas:
  • Tiene una complejidad temporal alta, O(n^2), lo que lo hace ineficiente para listas grandes.
  • No es estable y puede cambiar el orden relativo de elementos iguales.
• Rendimiento:
  • Es similar en eficiencia al Bubble Sort e Insertion Sort.
  • Tiene una complejidad temporal de O(n^2) en todos los casos.

Ordenación por fusión (Merge Sort)

• Ventajas:
  • Tiene una complejidad temporal eficiente, O(n log n), en todos los casos.
  • Es estable y garantiza el orden relativo de elementos iguales.
• Desventajas:
  • Requiere memoria adicional para almacenar los elementos temporales durante la fusión.
  • No es un algoritmo in-place, lo que puede ser problemático para grandes conjuntos de datos.
• Rendimiento:
  • Es más eficiente que los métodos anteriores y generalmente más rápido en la práctica.
  • Tiene una complejidad temporal de O(n log n) en todos los casos.

Ordenación rápido (Quick Sort)

• Ventajas:
  • Tiene una complejidad temporal eficiente, O(n log n) en promedio.
  • Es un algoritmo in-place y puede ser más rápido que otros métodos en la práctica.
• Desventajas:
  • Tiene un peor caso de complejidad temporal de O(n^2) si se selecciona un mal pivote.
  • No es estable y puede cambiar el orden relativo de elementos iguales.
• Rendimiento:
  • Es uno de los métodos más rápidos y eficientes en promedio.
  • Tiene una complejidad temporal de O(n log n) en promedio, pero puede degradarse a O(n^2) en el peor caso si se selecciona un mal pivote.

Ordenación Heap Sort

• Ventajas:
  • Tiene una complejidad temporal eficiente, O(n log n) en todos los casos.
  • Es in-place y no requiere memoria adicional.
• Desventajas:
  • No es estable en su forma estándar, lo que puede cambiar el orden relativo de elementos iguales.
  • Requiere más código y es menos intuitivo de implementar que otros métodos.
• Rendimiento:
  • Es eficiente y tiene un rendimiento constante en todos los casos.
  • Tiene una complejidad temporal de O(n log n) en todos los casos.

Resumen sobre ordenar Arrays

Elegir un metodo para ordenar Arrays generalmente tiene mucho que ver con los datos que se quieren ordenar. Mientras que los métodos como Bubble Sort, Insertion Sort y Selection Sort son adecuados para pequeñas cantidades de datos o listas casi ordenadas, métodos como Merge Sort, Quick Sort y Heap Sort son más eficientes para listas más grandes y ofrecen un mejor rendimiento en la mayoría de los casos.

Por este motivo, de entre todos los métodos de ordenación de Arrays vistos, elegir el método de ordenamiento óptimo dependerá de la naturaleza específica de los datos y los requisitos de rendimiento del problema en cuestión.

Si te ha parecido interesante este artículo, también te pueden interesar los artículos sobre qué es una función recursiva o cómo leer un árbol de directorios recursivo con PHP.

¡ Espero que este artículo sea de vuestro interés !