Los algoritmos de ordenamiento son esenciales en el mundo de la programación, ya que permiten organizar los datos de manera eficiente y lógica.
Estos algoritmos son fundamentales para mejorar el rendimiento de las aplicaciones y facilitar la búsqueda y el análisis de datos.
En este post te quiero enseñar cinco algoritmos de ordenamiento clásicos que debes conocer y nunca faltan en las entrevista de trabajo.
Bubblesort
El algoritmo de Bubblesort, también conocido como Ordenamiento Burbuja, es uno de los métodos de ordenamiento más sencillos y ampliamente utilizado en el mundo de la programación.
Se basa en comparar pares de elementos adyacentes e intercambiarlos si están en el orden incorrecto. Este proceso se repite hasta que no se necesiten más intercambios, lo que indica que la lista está ordenada.
En el siguiente código podrás ver cómo funciona el bubblesort utilizando javascript:
// Esta función implementa el algoritmo de Bubblesort para ordenar un array.
function bubbleSort(arr) {
// Obtiene el número total de elementos en el array.
let n = arr.length;
// Este bucle externo recorre todos los elementos del array.
for (let i = 0; i < n - 1; i++) {
// Este bucle interno recorre el array desde el principio hasta el final de la parte no ordenada.
for (let j = 0; j < n - i - 1; j++) {
// Compara dos elementos adyacentes, arr[j] y arr[j + 1].
if (arr[j] > arr[j + 1]) {
// Si arr[j] es mayor que arr[j + 1], intercambia los elementos.
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
// Devuelve el array ordenado.
return arr;
}
Pero, ¿cómo se aplica este algoritmo en la vida real? Aquí tienes dos ejemplos:
- Organizar los Contactos en tu Teléfono: Imagina que acabas de guardar un nuevo número en tu teléfono. La solución a tus problemas es el algoritmo de Bubblesort para ordenar tu lista de contactos en orden alfabético, asegurando que puedas encontrar fácilmente el contacto que acabas de guardar.
- Ordenar los Archivos en tu Teléfono: Cuando descargas un nuevo archivo en tu teléfono, el algoritmo de Bubblesort puede ser utilizado para ordenar tus archivos según el momento en que fueron añadidos. De esta manera, siempre tendrás acceso rápido a tus archivos más recientes.
El rendimiento de este algoritmo, aplicando análisis asintotico y utilizando Big O en la complejidad temporal, es:
- Mejor caso: O(n)
- Peor caso: O(n^2)
Recuerda que puedes medir el rendimiento de un algoritmo aplicando el análisis asintótico para calcular la complejidad temporal.
Los algoritmos de aqui en adelante se estarán midiendo con la notación Big O y se medirá según su complejidad temporal
Insertion Sort
El algoritmo de Insertion Sort (Ordenamiento por Inserción), construye la lista ordenada elemento por elemento. Funciona de manera similar a cómo las personas ordenan las cartas en sus manos, tomando un elemento y encontrando su lugar adecuado en la lista ordenada.
// Esta función implementa el algoritmo de Insertion Sort para ordenar un array.
function insertionSort(arr) {
// Este bucle recorre todos los elementos del array, comenzando desde el segundo elemento.
for (let i = 1; i < arr.length; i++) {
// La variable 'key' guarda el valor del elemento actual.
let key = arr[i];
// La variable 'j' se utiliza para recorrer los elementos a la izquierda de 'key'.
let j = i - 1;
// Este bucle mueve los elementos de arr[0..i-1] 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--;
}
// Una vez que se ha encontrado la posición correcta para 'key', se inserta en el array.
arr[j + 1] = key;
}
// Devuelve el array ordenado.
return arr;
}
Si buscas ejemplos de la vida real, tenemos:
- Procesamiento de Transacciones en Línea: En escenarios donde se añaden continuamente nuevas transacciones a un conjunto de datos ya ordenado, el Ordenamiento por Inserción resulta eficiente. Por ejemplo, las transacciones con tarjeta de crédito a menudo se añaden a una base de datos ordenada en función de sus marcas de tiempo.
- Ordenación de Camisas en un Armario: Un sastre organiza las camisas en un armario siempre en orden de tamaño, insertando rápidamente las nuevas camisas en la posición correcta moviendo hacia adelante las otras camisas para mantener el lugar correcto para una nueva camisa.
El rendimiento de este algoritmo, aplicando análisis asintotico, es:
- Mejor caso: O(n)
- Peor caso: O(n^2)
Merge Sort
Si conoces la frase «divide y vencerás», tienes una buena referencia para acordarte de este algoritmo.
El Merge Sort, conocido como Ordenamiento por Mezcla, es un método de ordenamiento que sigue el enfoque de división y conquista. Este algoritmo divide la lista en mitades hasta que cada sublista tiene un solo elemento y luego las combina en una lista ordenada. Es especialmente eficiente para listas grandes.
// Esta función implementa el algoritmo de Merge Sort para ordenar un array.
function mergeSort(arr) {
// Si el array tiene 0 o 1 elementos, ya está ordenado.
if (arr.length <= 1) {
return arr;
}
// Encuentra el índice medio del array.
const middle = Math.floor(arr.length / 2);
// Divide el array en dos mitades.
const left = arr.slice(0, middle);
const right = arr.slice(middle);
// Ordena cada mitad y las combina.
return merge(mergeSort(left), mergeSort(right));
}
// Esta función combina dos arrays ordenados en un solo array ordenado.
function merge(left, right) {
let resultArray = [], leftIndex = 0, rightIndex = 0;
// Mientras haya elementos en ambas mitades...
while (leftIndex < left.length && rightIndex < right.length) {
// Si el elemento de la izquierda es menor, lo añade al array resultante.
if (left[leftIndex] < right[rightIndex]) {
resultArray.push(left[leftIndex]);
leftIndex++;
} else {
// Si el elemento de la derecha es menor, lo añade al array resultante.
resultArray.push(right[rightIndex]);
rightIndex++;
}
}
// Añade los elementos restantes de ambas mitades al array resultante.
return resultArray
.concat(left.slice(leftIndex))
.concat(right.slice(rightIndex));
}
Con dos ejemplos de la vida real tenemos:
- Ordenación de Información de Usuarios en Redes Sociales: Las redes sociales manejan grandes conjuntos de datos de usuarios. El algoritmo de Merge Sort puede ser utilizado para ordenar estos datos de manera eficiente.
- Organización de Productos en Plataformas de Comercio Electrónico: En una plataforma de comercio electrónico, los productos pueden ser ordenados en base a sus precios o calificaciones. El algoritmo de Merge Sort es una excelente opción para realizar esta tarea debido a su eficiencia con listas grandes.
El rendimiento de este algoritmo es:
- Mejor caso: O(nlog)
- Peor caso: O(nlog)
Selection Sort
El algoritmo de Ordenamiento por Selección, Selection Sort, mejora el rendimiento de Bubblesort al realizar menos intercambios. Este método funciona encontrando el elemento mínimo en la lista y colocándolo al principio, luego repite el proceso para el resto de la lista.
// Esta función implementa el algoritmo de Selection Sort para ordenar un array.
function selectionSort(arr) {
// Este bucle recorre todos los elementos del array.
for (let i = 0; i < arr.length; i++) {
// Asume que el elemento mínimo es el primer elemento.
let min = i;
// Este bucle recorre los elementos restantes del array.
for (let j = i + 1; j < arr.length; j++) {
// Si encuentra un elemento más pequeño, actualiza 'min'.
if (arr[j] < arr[min]) {
min = j;
}
}
// Si el elemento mínimo no es el primer elemento, intercambia los elementos.
if (min !== i) {
let temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
// Devuelve el array ordenado.
return arr;
}
Si llevamos el algoritmo a la vida real, tenemos dos casos de uso:
- Ordenación de Transacciones Bancarias: Las transacciones bancarias a menudo se añaden a una base de datos ordenada en función de sus marcas de tiempo. El Ordenamiento por Selección puede mantener el ordenado al insertar cada nueva transacción en su posición correcta, asegurando una búsqueda y reporte eficientes.
- Organización de Cartas en un Juego: Imagina que estás jugando un juego de cartas. Este algoritmo puede ser utilizado para ordenar tus cartas de manera eficiente, permitiéndote encontrar rápidamente la carta que necesitas.
El rendimiento de este algoritmo es:
- Mejor caso: O(n^2)
- Peor caso: O(n^2)
Quicksort
El Algoritmo de Ordenamiento Rápido, Quicksort, es otro método de división y conquista, como el Merge Sort. Este algoritmo selecciona un ‘pivote’ y divide la lista en sub-listas que contienen elementos menores y mayores que el pivote, y luego ordena esas sub-listas. Si tienes listas grandes, utilizar este método va a ser la mejor solución por su eficiencia.
// Esta función implementa el algoritmo de Quicksort para ordenar un array.
function quickSort(arr) {
// Si el array tiene 0 o 1 elementos, ya está ordenado.
if (arr.length <= 1) {
return arr;
}
// Elige el último elemento como pivote.
const pivot = arr[arr.length - 1];
// Crea dos arrays para los elementos menores y mayores que el pivote.
const leftArr = [];
const rightArr = [];
// Recorre los elementos del array (excepto el pivote).
for (const el of arr.slice(0, arr.length - 1)) {
// Si el elemento es menor que el pivote, lo añade al array de la izquierda.
// Si el elemento es mayor que el pivote, lo añade al array de la derecha.
el < pivot ? leftArr.push(el) : rightArr.push(el);
}
// Ordena las dos mitades y las combina con el pivote en el medio.
return [...quickSort(leftArr), pivot, ...quickSort(rightArr)];
}
Y unos ejemplos de aplicación en la vida real:
- Sistemas de Gestión de Bases de Datos: Quicksort se utiliza para ordenar grandes conjuntos de datos en bases de datos para optimizar el rendimiento de las consultas1.
- Sitios de Comercio Electrónico: Quicksort puede ser utilizado para ordenar productos por precio, calificación u otros atributos para mejorar la experiencia del usuario2.
El rendimiento de este algoritmo es:
- Mejor caso: O(nlog(n))
- Peor caso: O(n^2)
Conclusión
Estos algoritmos de ordenamiento son herramientas poderosas en el arsenal de cualquier desarrollador. Cada uno tiene sus propias ventajas y situaciones en las que sobresale, y conocerlos es fundamental para elegir la mejor opción a la hora de resolver un problema.
Espero que este post te sea de útilidad y te ayude a mejorar tus habilidades de programación. No olvides compartir si te ha ayudado.
Sigueme en mis redes sociales para más contenido