Implementación de los algoritmos de ordenación bubble sort, merge sort y quicksort en Java

Escrito por el 03/06/2021.
java planeta-codigo
Enlace permanente Comentarios

Hay una buena cantidad de algoritmos de ordenación conocidos, entre los más conocidos está el bubble sort, el merge sort y el quicksort. No es imprescindible conocerlos todos ni implementarlos ya que las librerías y clases del JDK ya los implementan. Sin embargo, son utilizados como ejemplo para implementar un algoritmo al empezar a programar en un lenguaje de programación.

Java

Por norma general no es necesario implementar ningún algoritmo de ordenación, estos ya están implementados en las bibliotecas y en el caso de Java en las clases de su JDK. Lo único que es necesario implementar es una clase que implemente la interfaz Comparable o Comparator, esto es suficiente para ordenar arrays y colecciones de objetos en Java.

Sin embargo, por temas didácticos los algoritmos de ordenación son utilizados como ejemplo para aprender a programar, no son complejos una vez entendido su funcionamiento.

Entre los algoritmos más conocidos están el de ordenación burbuja o bubble sort, merge sort y quicksort. Cada uno tiene diferentes propiedades.

Contenido del artículo

Propiedades de los algoritmos de ordenación

En función de las propiedades del algoritmo y el conjunto de datos a ordenar o su número un algoritmo es más adecuado que otro. Por ejemplo, el algoritmo bubble sort no es el más rápido pero es estable y funciona por intercambio no requiriendo más memoria adicional que una variable temporal. Sin embargo, el algoritmo bubble sort no es paralelizable y hay algoritmos más rápidos.

Teniendo en cuenta las propiedades de los algoritmos para colecciones pequeñas el algoritmo bubble sort puede ser el más adecuado pero para colecciones de datos grandes los algoritmos merge sort y quicksort son más adecuados.

Dado que el algoritmo de ordenación más adecuado puede depender de variables como el número de datos a ordenar o el número de procesadores del sistema muy posiblemente la implementación de una función de utilidad de ordenación las tenga en cuenta para emplear un algoritmo u otro en vez de siempre el mismo.

Un algoritmo de ordenación se clasifica según las siguientes propiedades:

Complejidad computacional: es la complejidad del algoritmo medida según el número de operaciones que necesita realizar, se utiliza la notación Big O.
Uso de memoria: es la cantidad de memoria que necesita el algoritmo para realizar la ordenación. Los algoritmos in-place que realizan la ordenación en la misma colección solo necesitan una posición de memoria para realizar el intercambio.
Recursividad: algunos algoritmos son recursivos o no recursivos, mientras otros una parte es recursiva y otra no. Este último caso es el de merge sort que es una parte recursiva y otra no.
Estabilidad: los algoritmos de ordenación estables mantienen el orden en el que aparecen los elementos en la colección para aquellos que son considerados iguales.
Método general: puede ser por inserción, intercambio, selección, fusión, … Los algoritmos de intercambio incluyen bubble sort y quicksort.
Si el algoritmo es en serie o paralelo.
Adaptabilidad: la ordenación de los elementos afecta al tiempo de ejecución, los algoritmos que tienen en cuenta esto son adaptativos.
Online

Algoritmo bubble sort

El algoritmo de burbuja o bubble sort dada una colección de elementos compara los dos primeros elementos de la colección y los intercambia en función de su orden si es necesario.

A continuación realiza la comparación para el segundo y tercer elemento de la colección y los intercambia en función de su orden.

Este proceso se repite hasta llegar al último elemento de la colección, como resultado se tiene que en la última posición de la colección estará el elemento con mayor valor.

El proceso se repite de nuevo comenzando desde la primera posición de la colección sin incluir la posición del elemento ya ordenado anteriormente, como resultado dará al siguiente elemento de mayor orden. Se repite esta ordenación tantas veces como elementos tenga la colección menos uno.

Esta es una interfaz que define un método para ordenar una colección, se proporciona la colección y una clase Comparator.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


package io.github.picodotdev.blogbitix.javasort;

import java.util.Collection;
import java.util.Comparator;
import java.util.List;

public interface SortAlgorithm<T> {

    List<T> sort(Collection<T> collection, Comparator<T> comparator);

    default void swap(List<T> list, int i, int j) {
        T ti = list.get(i);
        T tj = list.get(j);
        list.set(j, ti);
        list.set(i, tj);
    }
}

SortAlgorithm.java

El programa Java crea una colección de 25 elementos con un valor aleatorio entre 0 y 100, y los ordena con cada uno de los algoritmos.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


package io.github.picodotdev.blogbitix.javasort;

...

public class Main {

    public static void main(String[] args) {
        ...

        {
            List<Integer> integers = randomList(25);
            List<Integer> bubbleSort = new BubbleSort<Integer>().sort(integers, Integer::compareTo);
            List<Integer> mergeSort = new MergeSort<Integer>().sort(integers, Integer::compareTo);
            List<Integer> quickSort = new QuickSort<Integer>().sort(integers, Integer::compareTo);
            System.out.printf("Integers (%s):    %s%n", integers.size(), integers.stream().map(i -> i.toString()).collect(Collectors.joining(",")));
            System.out.printf("Bubble Sort (%s): %s%n", bubbleSort.size(), bubbleSort.stream().map(i -> i.toString()).collect(Collectors.joining(",")));
            System.out.printf("Merge Sort (%s):  %s%n", mergeSort.size(), mergeSort.stream().map(i -> i.toString()).collect(Collectors.joining(",")));
            System.out.printf("Quick Sort (%s):  %s%n", quickSort.size(), quickSort.stream().map(i -> i.toString()).collect(Collectors.joining(",")));
        }
    }

    ...

    public static List<Integer> randomList(int elements) {
        return new Random().ints(elements, 0, 100).boxed().collect(Collectors.toList());
    }
}

Main.java

Esta es la implementación del algoritmos de burbuja.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


package io.github.picodotdev.blogbitix.javasort;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.List;

public class BubbleSort<T> implements SortAlgorithm<T> {

    @Override
    public List<T> sort(Collection<T> collection, Comparator<T> comparator) {
        List<T> list = new ArrayList<>(collection);
        for (int i = 0; i < list.size(); ++i) {
            for (int j = 1; j < list.size() - i; ++j) {
                T a = list.get(j - 1);
                T b = list.get(j);
                if (comparator.compare(a, b) > 0) {
                    swap(list, j - 1, j);
                }
            }
        }
        return list;
    }
}

BubbleSort.java

Algoritmo de ordenación merge sort

El algoritmo merge sort comienza con una fase de dividir listas, se divide la colección en dos partes del mismo número de elementos o una parte con elemento más que la otra si el número de elementos es impar. La división se aplica recursivamente hasta que las listas sean de un único elemento.

Una vez divididas las listas en elementos individuales comienza la fase de merge donde los elementos se juntan tomando de cada lista el elemento que sea menor hasta que las listas ya no tengan más elementos.

La fase de merge termina cuando se tenga una única lista con los elementos ordenados.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53


package io.github.picodotdev.blogbitix.javasort;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.List;

public class MergeSort<T> implements SortAlgorithm<T> {

    @Override
    public List<T> sort(Collection<T> collection, Comparator<T> comparator) {
        List<T> list = new ArrayList<>(collection);
        int n = list.size();
        if (n < 2) {
            return list;
        }
        int mid = n / 2;
        List<T> l = list.subList(0, mid);
        List<T> r = list.subList(mid, n);
        l = sort(l, comparator);
        r = sort(r, comparator);
        list = merge(l, r, comparator);
        return list;
    }

    private List<T> merge(List<T> l, List<T> r, Comparator<T> comparator) {
        List<T> list = new ArrayList<>();
        int i = 0;
        int j = 0;
        while (i < l.size() && j < r.size()) {
            T a = l.get(i);
            T b = r.get(j);
            if (comparator.compare(a, b) <= 0) {
                list.add(a);
                i += 1;
            } else {
                list.add(b);
                j += 1;
            }
        }
        while (i < l.size()) {
            T o = l.get(i);
            list.add(o);
            i += 1;
        }
        while (j < r.size()) {
            T o = r.get(j);
            list.add(o);
            j += 1;
        }
        return list;
    }
}

MergeSort.java

Algoritmo de ordenación quicksort

El algoritmo quicskort selecciona un elemento como pivote de la colección. A continuación divide la colección en dos listas de elementos, los que tienen un valor inferior al valor de pivote y los que tiene un valor superior al valor de pivote.

A continuación se aplica la ordenación a cada una de las listas de forma recursiva, hasta que las listas no ordenadas tengan menos de dos elementos.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


package io.github.picodotdev.blogbitix.javasort;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.List;

public class QuickSort<T> implements SortSortAlgorithmable<T> {

    @Override
    public List<T> sort(Collection<T> collection, Comparator<T> comparator) {
        List<T> list = new ArrayList<>(collection);
        sort(list, 0, list.size() - 1, comparator);
        return list;
    }

    void sort(List<T> list, int begin, int end, Comparator<T> comparator) {
        if (begin < end) {
            int p = partition(list, begin, end, comparator);
            sort(list, begin, p - 1, comparator);
            sort(list, p + 1, end, comparator);
        }
    }

    int partition(List<T> list, int begin, int end, Comparator<T> comparator) {
        T pivot = list.get(end);
        int i = begin;
        for (int j = begin; j < end; ++j) {
            T o = list.get(j);
            if (comparator.compare(o, pivot) < 0) {
                swap(list, i, j);
                i += 1;
            }
        }
        swap(list, i, end);
        return i;
    }
}

QuickSort.java

1
2
3
4


Integers (25):    42,69,60,49,21,29,65,11,92,94,19,48,83,97,44,80,7,18,62,91,48,57,35,80,74
Bubble Sort (25): 7,11,18,19,21,29,35,42,44,48,48,49,57,60,62,65,69,74,80,80,83,91,92,94,97
Merge Sort (25):  7,11,18,19,21,29,35,42,44,48,48,49,57,60,62,65,69,74,80,80,83,91,92,94,97
Quick Sort (25):  7,11,18,19,21,29,35,42,44,48,48,49,57,60,62,65,69,74,80,80,83,91,92,94,97

System.out

Otros algoritmo de ordenación

Los anteriores no son los únicos algoritmos conocidos para realizar ordenación, el la página de la wikipedia sobre algoritmos de ordenación hay muchos otros con una tabla de información acerca de su complejidad en el mejor de los casos, promedio y en el peor de los casos, su consumo de memoria, si es estable y el método de ordenación empleado.

Comparación de algunos algoritmos de ordenación

El código fuente completo del ejemplo puedes descargarlo del repositorio de ejemplos de Blog Bitix alojado en GitHub y probarlo en tu equipo ejecutando siguiente comando:
./gradlew run

Implementación de los algoritmos de ordenación bubble sort, merge sort y quicksort en Java

Propiedades de los algoritmos de ordenación

Algoritmo bubble sort

Algoritmo de ordenación merge sort

Algoritmo de ordenación quicksort

Otros algoritmo de ordenación

Cómo ordenar arrays y colecciones de objetos en Java

El patrón de diseño Factory, ventajas sobre new y diferencias con Builder

Crear de forma sencilla un cliente de un servicio REST o HTTP con Retrofit

Herramientas de reconocimiento de texto en imágenes con OCR

Las clases y librerías básicas de Java para bases de datos relacionales

Programas basados en consola con Java usando Lanterna