Métodos de ordenamiento en Java

Los métodos de ordenamiento son esenciales para la gestión de elementos en una lista, cada método tiene una eficiencia diferente según sea el caso, aquí los más conocidos.

ORDENAMIENTO POR INTERCAMBIO (Burbuja)

Este método de ordenamiento es el menos eficiente pero el más sencillo de comprender, se le denomina intercambio, porque va comparando una posición con cada una de las posiciones siguientes, dando la condición si el anterior es mayor que el siguiente entonces se realiza un cambio en la posición, el análisis del algoritmo nos da O(n^2), esto si la ordenación completa requiere el peor de los casos.

 

Código en java

public static void blubbleSort1(int arr[]) {
        int aux = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    aux = arr[i];
                    arr[i] = arr[j];
                    arr[j] = aux;
                }
                
            }
        }

    }

ORDENAMIENTO POR SELECCIÓN

Este método de ordenamiento comparado con el anterior es mejor en términos de eficiencia, y consiste en ir seleccionando el valor más pequeño e ir colocándolo al inicio, entonces supongamos un arreglo a[ ], con el ordenamiento por selección va a buscar el valor más pequeño y lo coloca en a[0], así sucesivamente hasta a[n-1], su complejidad es  O(n^2). 

 

Código en java

public static void selectionsort(int numeros[]) {
        int min = 0;
        int aux = 0;
        for (int i = 0; i < numeros.length; i++) {
            min = i;
            for (int j = i + 1; j < numeros.length; j++) {

                if (numeros[j] < numeros[min]) {
                    min = j;
                }
            }
            if (min != i) {
                aux = numeros[i];
                numeros[i] = numeros[min];
                numeros[min] = aux;
            }

        }
    }
  
  
  

ORDENAMIENTO POR INSERCIÓN

El ordenamiento por inserción tiene un funcionamiento similar a ordenar cartas de una baraja, consiste en insertar un elemento en su posición correcta o indicada en un arreglo ya ordenado, la complejidad del algoritmo de inserción es 0(n^2).

Código en java

public static void insertionsort(int a[]){
        int aux;
        for (int i = 1; i < a.length; i++) {
            aux = a[i];
            for (int j = i-1; j >=0 && a[j]>aux; j--) {
                a[j+1]=a[j];
                a[j]=aux;
            }
        }
    }
 
 
 

ORDENAMIENTO QUICKSORT

Este algoritmo consiste en dividir el arreglo a ordenar, se considera el más eficiente y con el código mas sencillo y muy interesante, la división del arreglo queda en la parte izquierda, un elemento mitad que se le asigna el nombre de pivote y y una parte derecha, la función del pivote es dividir exactamente en la mitad la lista, la ordenación se realiza de forma recursiva haciendo llamados así mismo sobre el método, para determinar su complejidad se considera difícil pero en promedio su complejidad es de 0(n log n), de esta manera su eficiencia es mejor en comparación con los anteriores métodos.

Código en java

public static void quicksort(int A[], int izq, int der) {

        int pivote = A[izq];
        int i = izq;
        int j = der;
        int aux;


        while (i < j) {

            while (A[i] <= pivote && i < j) i++;

            while (A[j] > pivote) j--;

            if (i < j) {
                aux = A[i];
                A[i] = A[j];
                A[j] = aux;
            }
        }
        A[izq] = A[j];
        A[j] = pivote;
        if (izq < j - 1)
            quicksort(A, izq, j - 1);
        if (j + 1 < der)
            quicksort(A, j + 1, der);
    }
   

ORDENAMIENTO SHELL SORT

Consiste en dividir el rango de las iteraciones, es por ello que en el primer ciclo tenemos que saltos/2, luego se presenta la condición que hace un cambio en la posición el arreglo, si en el rango de los saltos que da las iteraciones no hay ningún cambio, saltos se divide nuevamente entre 2, para seguir haciendo iteraciones representadas en saltos e ir comparando los elementos del arreglo.

Código en java

    public static void shellsort(int numbers[]){
        int salto, aux, i;
        boolean cambios;
        for(salto=numbers.length/2; salto!=0; salto/=2){
            cambios=true;
            while(cambios){
                cambios=false;
                System.out.println(salto+" ");
                for(i=salto; i< numbers.length; i++)
                    if(numbers[i-salto]>numbers[i]){
                        aux=numbers[i];
                        numbers[i]=numbers[i-salto];
                        numbers[i-salto]=aux;
                        cambios=true;
                    }
            }
        }
    }