Ejemplos de Algoritmos de Ordenación Implementados en JavaScript

El ordenamiento de datos es una de las operaciones fundamentales en la ciencia de la computación y, por ende, en el desarrollo de software. JavaScript, siendo uno de los lenguajes de programación más utilizados, cuenta con una serie de algoritmos de ordenación que pueden implementarse para resolver diversas problemáticas. A lo largo de este artículo, exploraremos algunas de las técnicas de ordenación más conocidas y cómo se pueden llevar a cabo utilizando JavaScript.

Ordenación Burbuja (Bubble Sort)

El algoritmo de ordenación burbuja es uno de los más simples, pero menos eficientes, métodos de ordenamiento. La técnica consiste en comparar cada par de elementos adyacentes y, en caso de que el orden sea incorrecto, se intercambian sus posiciones. Este proceso se repite hasta que no se requieren más intercambios, lo que significa que la lista está ordenada.

A continuación, se muestra una implementación básica del ordenamiento burbuja en JavaScript:

function bubbleSort(arr) {
    var len = arr.length;
    var swapped;
    do {
        swapped = false;
        for (var i = 0; i < len; i++) {
            if (arr[i] > arr[i + 1]) {
                var temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                swapped = true;
            }
        }
    } while (swapped);
    return arr;
}

La función ‘bubbleSort’ toma como argumento un arreglo ‘arr’ y procede a ordenarlo. Declaramos una variable ‘len’ para almacenar la longitud del arreglo y una variable booleana ‘swapped’ que nos ayuda a determinar si hubo un intercambio en la pasada actual. Dentro de un bucle do-while, iteramos sobre el arreglo y comparamos cada elemento con su sucesor; si están en el orden incorrecto, los intercambiamos y marcamos ‘swapped’ como true. Si después de una pasada completa no se han realizado intercambios, se asume que la lista está ordenada y el bucle termina.

Ordenación por Selección (Selection Sort)

El algoritmo de ordenación por selección mejora ligeramente el rendimiento del ordenamiento burbuja. Funciona encontrando el elemento mínimo en el arreglo y colocándolo al principio. Luego, el proceso se repite para el subarreglo restante hasta que todos los elementos están ordenados.

Veamos cómo implementar el algoritmo de selección en JavaScript:

function selectionSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        var min = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        if (min !== i) {
            var temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
    return arr;
}

Dentro de la función ‘selectionSort’, empezamos definiendo la longitud del arreglo con ‘len’. Luego, usamos dos bucles anidados: el externo recorre cada elemento del arreglo, mientras que el interno busca el menor elemento en el subarreglo que comienza en ‘i + 1’. Cuando encontramos el mínimo, comprobamos si su índice ‘min’ difiere de ‘i’, y de ser así, intercambiamos los valores para mover el mínimo al inicio del subarreglo.

Ordenación por Inserción (Insertion Sort)

El algoritmo de ordenación por inserción es particularmente útil para listas pequeñas y casi ordenadas. Consiste en tomar un elemento del arreglo e insertarlo en la posición correcta en la parte ya ordenada del arreglo, movimiento que emula la manera en que se ordenarían las cartas en una mano.

Veamos la implementación paso a paso de este algoritmo en JavaScript:

function insertionSort(arr) {
    var len = arr.length;
    for (var i = 1; i < len; i++) {
        var key = arr[i];
        var j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
    return arr;
}

La función comienza asignando a la variable ‘key’ el valor del elemento a insertar y a ‘j’ el índice del último elemento de la sublista ordenada. Se utiliza un bucle while que recorre esta sublista hacia atrás, comprobando si cada elemento es mayor que ‘key’. Si es así, desplaza el elemento una posición y finalmente inserta ‘key’ en la ubicación correcta. Este proceso se repite para cada elemento del arreglo, y el resultante es una secuencia ordenada.

Ordenación Rápida (Quick Sort)

Quick sort, o ordenación rápida, es uno de los algoritmos de ordenación más rápidos y eficientes, basado en la técnica de divide y vencerás. Consiste en seleccionar un elemento como pivote y particionar el arreglo de tal manera que elementos menores al pivote queden a su izquierda y los mayores, a su derecha. Luego, se ordenan las particiones de manera recursiva.

A continuación se detalla una implementación típica del quick sort en JavaScript:

function quickSort(arr, left, right) {
    var pivot,
    partitionIndex;

    if (left < right) {
        pivot = right;
        partitionIndex = partition(arr, pivot, left, right);

        //sort left and right
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
    return arr;
}

function partition(arr, pivot, left, right) {
    var pivotValue = arr[pivot],
    partitionIndex = left;

    for (var i = left; i < right; i++) {
        if (arr[i] < pivotValue) {
            swap(arr, i, partitionIndex);
            partitionIndex++;
        }
    }
    swap(arr, right, partitionIndex);
    return partitionIndex;
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

En esta implementación, la función ‘quickSort’ recibe tres parámetros: el arreglo ‘arr’ y dos índices, ‘left’ y ‘right’, que definen el segmento a ordenar. Seleccionamos el elemento ubicado en ‘right’ como nuestro pivote y llamamos a la función ‘partition’, que reorganizará los elementos y devolverá el índice de partición. Seguidamente, aplicamos de manera recursiva ‘quickSort’ a las subpartes a la izquierda y la derecha de este índice. La función auxiliar ‘swap’ se encarga de intercambiar los elementos dentro del arreglo.

Estos algoritmos representan solamente una pequeña muestra de las técnicas de ordenación disponibles para los programadores en JavaScript. Cada uno ofrece distintos beneficios y eficiencias, dependiendo del tipo y tamaño de los datos que requieran ser ordenados. Es crucial como desarrollador, entender estas diferencias para escoger el algoritmo más adecuado para cada situación.

Te puede interesar

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *