Algoritmos de ordenamiento

Selection sort

El selecting sort resulta ser bastante natural de comprender ya que es una forma en que las personas ordenan la cosas.

• Primero se toma el elemento más pequeños de la lista y se envía a la primera posición de la lista.
• Luego se toma el siguiente elemento más pequeño y se envía a la siguiente posición de la lista.
• Siguiendo estos pasos se continua ordenando hasta que se finaliza el algoritmo.

Código:

public class SelectionSort {

 public int[] doSelectionSort(int[] arr){

    for (int i = 0; i < arr.length - 1; i++){

        int index = i;

        for (int j = i + 1; j < arr.length; j++)

            if (arr[j] < arr[index])

                index = j;

        int smallerNumber = arr[index];

        arr[index] = arr[i];

        arr[i] = smallerNumber;

    }

    return arr;

}

public static void main(String a[]){
    SelectionSort ss = new SelectionSort();
    int[] arr1 = {1, 2, 3, 9, 7, 13, 6, 5, 12, 10};
    int[] arr2 = ss.doSelectionSort(arr1);
    for(int i:arr2){
        System.out.print(i);
        System.out.print(", ");
    }
}

}

Bubble Sort

En el bubble sort se toman dos elementos al mismo tiempo y se comparan para ver cual es mayor.

• Se empieza del lado izquierdo de la lista en las posiciones 1 y 0.
• Luego se comparan ambos números y si el que esta a la izquierda es mayor, se intercambian los valores, en caso contrario no hace nada.
• Ambos indices se mueven una posición a la derecha y vuelve a comparara.
• Continua aplicando los pasos anteriores hasta llegar al final de la lista.
• Vuelve a empezar desde el principio de la lista realizando comparaciones.
• Se recorrerá la lista las veces que sea necesarias hasta que la lista este totalmente ordenada.

Código:

public class BubbleSort {

    public static void bubble_srt(int array[]) {

        int n = array.length;

        int k;

        for (int m = 0; m < n; m++) {

            for (int i = 0; i < n - 1; i++) {

                k = i + 1;

                if (array[i] > array[k]) {

                    int temp;

                    temp = array[i];

                    array[i] = array[k];

                    array[k] = temp;

                }

            }

            printNumbers(array);

        }

    }


    private static void printNumbers(int[] input) {
        for (int i = 0; i < input.length; i++) {
            System.out.print(input[i] + ", ");
        }
        System.out.println("\n");
    }

    public static void main(String[] args) {
        int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
        bubble_srt(input);
    }
}

Insertion Sort

El insertion sort es un algoritmo que también resulta muy natural ya que también es una forma en que las personas ordenan las cosas.

• Se empieza recorriendo la lista verificando que los elementos estén en su lugar de acuerdo a su valor.
• Si detecta que un valor esta fuera de lugar envía el elemento a la posición a la que debe de estar directamente en relación a los elementos que ya reviso.
• Cuando se llegue al final de la lista, está ya estará ordenada.

Código:

public class InsertionSort {

void sort(int arr[]){

    int n = arr.length;

    for (int i=1; i<n; ++i){

        int key = arr[i];

        int inicio = i-1;

        while (inicio>=0 && arr[inicio] > key){

            arr[inicio+1] = arr[inicio];

            inicio = inicio-1;

        }

        arr[inicio+1] = key;

        printArray(arr, inicio, i + 1);

    }

}

public static int[] doInsertionSort(int[] input){

    int temp;

    int contador = 0;

    for (int i = 1; i < input.length; i++) {

        for(int j = i ; j > 0 ; j--){

            if(input[j-1] > input[j]){

                temp = input[j];

                input[j] = input[j-1];

                input[j-1] = temp;

                printArray(input, j-1, j);

            }

            contador++;

        }

    }

    System.out.println(contador);

    return input;

}


static void printArray(int arr[], int i1, int i2){

    int n = arr.length;

    for (int i=0; i<n; ++i)

        if(i == i1)

            System.out.print(arr[i] + " " + i1 + "-" + i2 + " ");

        else System.out.print(arr[i] + " ");

    System.out.println();

}

}

Shell Sort

El shell Sort se puede ver como una versión mejorada del insertion sort, esto debido a que compara los los elementos a una cierta distancia en vez de entre los elementos adyacentes entre si.

• Primero se define la distancia que va a haber entre los elementos a comparar, esto generalmente se hace calculando el largo de la lista entre dos, el resultado sera la distancia que hay entre los elementos a comparar.
• Luego compara el primer grupo de elementos y si el que esta a la derecha es menor, se realizara un cambio, en caso contrario no se hace nada.
• Luego continua con los demás grupos hasta llegar al final de la lista.
• Por último, se vuelve a revisar toda la lista, esto lo hará que la lista este ordenada.

Código:

public class ShellSort {

static void printArray(int arr[]){

    int n = arr.length;

    for (int i=0; i<n; ++i)

        System.out.print(arr[i] + " ");

    System.out.println();

}

public int sort(int arr[]){

    int n = arr.length;

    for (int gap = n/2; gap > 0; gap /= 2){

        for (int i = gap; i < n; i += 1){

            int temp = arr[i];

             int j = 0;

            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)

                arr[j] = arr[j - gap];

            arr[j] = temp;

        }
    }

    return 0;

}

public static void main(String args[]){

    int arr[] = {14, 7, 3, 12, 9, 11, 6, 2};

    System.out.println("Antes de ordenar");

    printArray(arr);

    ShellSort ob = new ShellSort();

    ob.sort(arr);

    System.out.println("Después de ordenar");

    printArray(arr);

}

}

Merge Sort

En el merge sort se basa en el "Divide y vencerás" ya que, se toma la lista y se divide en listas más pequeñas que se logran acomodar más rapido.

• Primero se toma la lista y se divide a la mitad en dos listas más pequeñas.
• Luego se vuelve a aplicar el algoritmo a cada sublista recursivamente para ordenarlas.
• Cuando todas las sublistas estén ordenadas se concatenan y se crea una nueva lista ordenada.

Código:

public class MergeSort {

private int[] numeros;

private int[] auxiliar;


private int longitud;

public void sort(int[] valores) {

    this.numeros = valores;

    longitud = valores.length;

    this.auxiliar = new int[longitud];

    mergesort(0, longitud - 1);

    print();
}

private void print(){

    for(int i = 0; i < longitud; i++){

        System.out.print(this.numeros[i] + " ");

    }

}

private void mergesort(int primero, int ultimo) {

    if (primero < ultimo) {

        int mitad = primero + (ultimo - primero) / 2;

        mergesort(primero, mitad);

        mergesort(mitad + 1, ultimo);

        merge(primero, mitad, ultimo);

    }
}

private void merge(int primero, int mitad, int ultimo) {

    for (int i = primero; i <= ultimo; i++) {

        auxiliar[i] = numeros[i];

    }

    int i = primero;

    int j = mitad + 1;

    int k = primero;

    while (i <= mitad && j <= ultimo) {

        if (auxiliar[i] <= auxiliar[j]) {

            numeros[k] = auxiliar[i];

            i++;

        } else {

            numeros[k] = auxiliar[j];

            j++;

        }

        k++;

    }

    while (i <= mitad) {

        numeros[k] = auxiliar[i];

        k++;

        i++;

    }
 }

public static void main(String[] args){

    MergeSort mergeSort = new MergeSort();

    int[] valores =  {12, 34, 54, 2, 3, 4, 21, 1};

    mergeSort.sort(valores);


}

}

Quick Sort

El quickSort es un algoritmo de divide y vencerás ya que toma una posición de la lista como pivote y a partir de este divide la lista en dos partes. El pivote puede ser cualquier elemento del arreglo, sin embargo, generalmente se toma el del medio.

• Primero se toma un valor como el pivote.
• Luego se trasladan los elemento más pequeños al pivote a la izquierda de este y los mayores a la derecha.
• Una vez que la lista principal se separa en dos sublistas se repiten los pasos anteriores en cada sublista de forma recursiva siempre y cuando la cantidad de elementos dentro de las sublistas sea mayor a 1.

Código:

public class Quicksort  {

    private int[] numbers;

    private int number;
    public void sort(int[] values) {

        if (values ==null || values.length==0){

            return;

        }

        this.numbers = values;

        number = values.length;

        quicksort(0, number - 1);

    }

    private void quicksort(int low, int high) {

        int i = low, j = high;

        int pivot = numbers[low + (high-low)/2];

        while (i <= j) {

            while (numbers[i] < pivot) {

                i++;

            }
            while (numbers[j] > pivot) {

                j--;

            }
            if (i <= j) {

                exchange(i, j);

                i++;

                j--;

            }
        }
        if (low < j)

            quicksort(low, j);

        if (i < high)

            quicksort(i, high);

    }
    private void exchange(int i, int j) {

        int temp = numbers[i];

        numbers[i] = numbers[j];

        numbers[j] = temp;

    }

}

Radix Sort

Otros algoritmos ven key de cada elemento como una unidad atómica. Radix sort deshace la key en dígitos y acomoda los datos de acuerdo con el valor de los datos. Analiza cada unidad del elemento del nodo.

Codigo:

public class RadixSort {

    static int getMax(int arr[], int n)

    {
        int mx = arr[0];

        for (int i = 1; i < n; i++)

            if (arr[i] > mx)

                mx = arr[i];

        return mx;

    }

    static void countSort(int arr[], int n, int exp)

    {
        int output[] = new int[n]; // output array

        int i;

        int count[] = new int[10];

        Arrays.fill(count,0);

        for (i = 0; i < n; i++)

            count[ (arr[i]/exp)%10 ]++;

        for (i = 1; i < 10; i++)

            count[i] += count[i - 1];

        for (i = n - 1; i >= 0; i--)
        {
            output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];

            count[ (arr[i]/exp)%10 ]--;
        }

        for (i = 0; i < n; i++)

            arr[i] = output[i];
    }

    static void radixsort(int arr[], int n)

    {

        int m = getMax(arr, n);

        for (int exp = 1; m/exp > 0; exp *= 10)
            countSort(arr, n, exp);
    }

    static void print(int arr[], int n)

    {
        for (int i=0; i<n; i++)

            System.out.print(arr[i]+" ");

    }


    public static void main (String[] args)
    {
        int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};

        int n = arr.length;

        radixsort(arr, n);

        print(arr, n);

    }
}