Comparación de algoritmos de ordenamiento de datos en Python, Java y Rust

Claude Paugh
17 oct
6 Min. de lectura

Los algoritmos de ordenamiento son esenciales en informática y programación. Permiten organizar los datos en un orden específico, mejorando la eficiencia y la usabilidad. En esta publicación, compararemos varios algoritmos de ordenamiento implementados en Python, Java y Rust. No incluimos C++, ya que suele ser el lenguaje con mejor rendimiento, pero se utiliza para la manipulación y el procesamiento de datos en ingeniería de datos. Nos centraremos en la complejidad de su código y la notación Big O. Verás ejemplos de código para cada lenguaje y recomendaciones para las mejores combinaciones según el rendimiento y la facilidad de uso.

Comprensión de los algoritmos de ordenamiento

Los algoritmos de ordenación son métodos para organizar los elementos de una lista o matriz en un orden específico, generalmente ascendente o descendente. Existen muchos algoritmos de ordenación, cada uno con sus ventajas y desventajas. A continuación, se presentan algunos ejemplos comunes:

Ordenamiento de burbuja: simple pero ineficiente para conjuntos de datos grandes.
Ordenamiento por selección: también simple, pero tiene ineficiencias similares.
Ordenación por inserción: eficiente para conjuntos de datos pequeños o datos mayormente ordenados.
Ordenamiento por combinación: una estrategia de dividir y vencer que es eficiente con conjuntos de datos más grandes.
Ordenación rápida: altamente eficiente para una amplia gama de conjuntos de datos.

Cada algoritmo clasifica los datos de forma diferente, lo que afecta su eficiencia y rendimiento.

Notación O grande

La notación Big O describe el rendimiento y la complejidad de un algoritmo. Establece un límite superior para la complejidad temporal o espacial en función del tamaño de los datos de entrada. Dominar la notación Big O es crucial para evaluar la eficiencia de los algoritmos de ordenamiento.

Notaciones comunes de Big O para algoritmos de ordenamiento

O(n^2): complejidad temporal cuadrática, típica de algoritmos como ordenamiento de burbuja, ordenamiento por selección y ordenamiento por inserción.
O(n log n): complejidad temporal log-lineal, que se encuentra en algoritmos más eficientes como Merge Sort y Quick Sort.
O(n): Complejidad temporal lineal, vista en casos específicos como Counting Sort.

Algoritmos de ordenamiento en Python

Ordenamiento de burbujas

El ordenamiento de burbuja es uno de los métodos de ordenamiento más sencillos. Recorre la lista repetidamente, compara elementos adyacentes y los intercambia si están en el orden incorrecto.

--> pitón

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

Ejemplo de uso

arr = [64, 34, 25, 12, 22, 11, 90]
print("Sorted array:", bubble_sort(arr))

El método de ordenamiento de burbuja tiene una complejidad temporal de O(n^2), lo que lo hace ineficiente para conjuntos de datos grandes.

Ordenación por combinación

Merge Sort es un algoritmo de divide y vencerás. Divide la matriz de entrada en dos mitades, las ordena y luego las vuelve a fusionar.

` -->python

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

Ejemplo de uso

arr = [38, 27, 43, 3, 9, 82, 10]
print("Sorted array:", merge_sort(arr))

Con una complejidad temporal de O(n log n), el método de combinación es más eficiente para conjuntos de datos más grandes en comparación con el método de clasificación de burbuja.

Algoritmos de ordenamiento en Java

Ordenamiento por selección

La ordenación por selección divide la lista de entrada en una parte ordenada y otra desordenada. Selecciona repetidamente el elemento más pequeño (o más grande) de la parte desordenada y lo mueve a la parte ordenada.

-->java

import java.util.Arrays;

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Al igual que el ordenamiento de burbuja, el ordenamiento por selección también tiene una complejidad temporal de O(n^2).

Ordenación rápida

Quick Sort es un algoritmo de ordenamiento eficiente que utiliza una estrategia de divide y vencerás. Selecciona un elemento pivote y divide la matriz en dos mitades, ordenándolas recursivamente.

-->java

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Quick Sort tiene una complejidad temporal promedio de O(n log n), lo que lo convierte en uno de los algoritmos de clasificación más rápidos.

Algoritmos de ordenamiento en Rust

Ordenación por inserción

El ordenamiento por inserción genera una matriz ordenada de forma incremental. Puede ser más eficiente con listas pequeñas o datos mayormente ordenados.

--> óxido

fn insertion_sort(arr: &mut Vec<i32>) {
    let n = arr.len();
    for i in 1..n {
        let key = arr[i];
        let mut j = i as isize - 1;
        while j >= 0 && arr[j as usize] > key {
            arr[j as usize + 1] = arr[j as usize];
            j -= 1;
        }

        arr[j as usize + 1] = key;
    }
}

fn main() {
    let mut arr = vec![12, 11, 13, 5, 6];
    insertion_sort(&mut arr);
    println!("Sorted array: {:?}", arr);
}

La ordenación por inserción tiene una complejidad temporal de O(n^2), por lo que no es ideal para conjuntos de datos grandes.

Ordenamiento por montón

El ordenamiento por montículos utiliza una estructura de montículo binario. Es un algoritmo basado en comparaciones con una complejidad temporal de O(n log n).

--> óxido

fn heapify(arr: &mut Vec<i32>, n: usize, i: usize) {
    let mut largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;

    if left < n && arr[left] > arr[largest] {
        largest = left;
    }

    if right < n && arr[right] > arr[largest] {
        largest = right;
    }

    if largest != i {
        arr.swap(i, largest);
        heapify(arr, n, largest);
    }
}

fn heap_sort(arr: &mut Vec<i32>) {
    let n = arr.len();
    for i in (0..n / 2).rev() {
        heapify(arr, n, i);
    }

    for i in (0..n).rev() {
        arr.swap(0, i);
        heapify(arr, i, 0);
    }
}

fn main() {
    let mut arr = vec![12, 11, 13, 5, 6];
    heap_sort(&mut arr);
    println!("Sorted array: {:?}", arr);
}

El ordenamiento por montículos es eficiente, lo que lo hace adecuado para conjuntos de datos más grandes, con una complejidad temporal de O(n log n).

Comparación de la complejidad y el rendimiento del código

Al comparar algoritmos de clasificación en Python, Java y Rust, varios factores son importantes:

Facilidad de implementación : La sintaxis sencilla de Python suele permitir implementaciones más rápidas y sencillas. En cambio, Java y Rust requieren código más repetitivo.
Rendimiento : Rust generalmente supera a los demás gracias a su eficiente gestión de memoria y sus capacidades a nivel de sistema. Java también ofrece un buen rendimiento, pero Python es más lento al ser un lenguaje interpretado. Por ejemplo, Quick Sort puede ejecutarse en menos de la mitad del tiempo en Rust que en Python para el mismo conjunto de datos.
Notación Big O : las complejidades temporales de los algoritmos siguen siendo consistentes en todos los lenguajes, pero el rendimiento real varía según el modelo de ejecución y las optimizaciones de cada lenguaje.

Maridajes recomendados

Python con ordenamiento por combinación : útil por su legibilidad y simplicidad, especialmente para conjuntos de datos grandes.
Java con Quick Sort : conocido por su alta eficiencia, lo que lo hace ideal para aplicaciones orientadas al rendimiento.
Rust con Heap Sort : excelente opción para lograr velocidad y un uso eficiente de la memoria.

Reflexiones finales

Los algoritmos de ordenamiento son herramientas vitales en programación. Comprender sus complejidades e implementaciones en diversos lenguajes puede influir significativamente en el rendimiento. Mientras que Python ofrece facilidad de uso, Java equilibra rendimiento y legibilidad. Rust destaca por su velocidad, lo que lo hace perfecto para aplicaciones de alta eficiencia.

La elección del algoritmo y lenguaje de ordenación adecuados depende, en última instancia, de las necesidades de su proyecto y de las características de cada lenguaje. Al comprender las opciones, podrá tomar una decisión informada que mejore el rendimiento de su aplicación.