version en video.
ordenar es poner las cosas siguiendo un orden(que viva la redundancia) por ejemplo podemos ordenar un numero de mayor a menor (5,4,3,2,1) o de menor a mayor (1,2,3,4,5) y en programacion existen muchos metodos de ordenamiento siendo uno de los mas sencillos de implementar bubble sort.
Bubble Sort.
es un método de ordenamiento donde iterativa mente vamos por toda la lista de elementos comparando el valor actual con el anterior (y rotandolos cuando no estan en orden) esto se hace cuantas veces como se necesite hasta que ido por todo el arreglo sin tener que rotar nada (significando esto que ya esta en orden).
es un algoritmo muy sencillo y tambien muy ineficiente en promedio toma O(n*n) *1
en java se puede implementar de la siguiente manera.
public static void main(String args[]) {
int[] array = {13, 14, 42, 54, 56, 38, 97, 24, 57};
bubbleSort(array);
printArray(array);
}
public static boolean printArray(int[] input) {
if (input.length == 0) {
return false;
}
for (int i = 0; i < input.length; i++) {
System.out.println(" " + input[i]);
}
return true;
}
public static boolean bubbleSort(int[] input) {
if (input.length < 2) return false;
boolean isInOrder;
do {
isInOrder = true;
for (int i = 1; i < input.length; i++) {
if (input[i - 1] < input[i]) {
int temporal = input[i - 1];
input[i - 1] = input[i];
input[i] = temporal;
isInOrder = false;
}
}
} while (!isInOrder);
return true;
}
otro algoritmo muy conocido y que es creo de los que mas se usa es
Quick Sort
quicksort(ordenamiento rápido) y gusta bastante por que:
- es rápido en promedio toma O(nlogn)
- toma menos tiempo si los registros estan parcialmente ordenados(es verda en muchos casos)
- optimiza bien el uso de cache *3
yo para entender este algoritmo tuve que ver este video donde se explica muy bien *3.
el algoritmo es mas o menos asi.
- usted empieza con un array (posiblemente desordenado)
- tiene un metodo para ordernarlo(quicksort) que recibe este array, un minimo que es 0 el inicio del array y el tamaño del array(el intervalo que va ordenar)
- este metodo despues de revisar que el min sea menor que el maximo llama a otro metodo que se encarga de encontrar una "particion" y mientras lo hace organiza los mas pequeño que la particion a la izquierda y lo mas grandes a la derecha (ordena no todo sino simplemente lo mayor y menor que donde esta la particion)
- luego teniendo el index de esa particion se vuelve a llamar el metodo inicial dos veces una del inicio a la particion, y otra de la particion(el index de la misma hasta el tamaño original)
- esto se sigue repitiendo recursivamente hasta que se acaba organizando todo.
entrando mas en detalle en el metodo que hace la particion se encarga de lo siguiente.
- setea una variable i con el inicio/minimo y una variable j con el maximo/final
- determina un pivote o elemento en el array para comparar(al inicio o al final del array generamente por facilidad, pero tambien se puede en en cualquier punto.
- empieza a aumentar el i mientras lo que se encuentre sea menor que el pivote(osea que ya esta organizado con respecto al pivote), y a disminuir j mientras lo que se encuentre sea mayor que el pivote(osea que ya esta organizado en relacion al pivote)
- si i es menor que j, es decir encontraron uno mayor y uno menor donde no debian estar estos se intercambian.
- esto se repite y al final el pivote se pone en el "medio"(cambiando la variable en la poscision del pivote y la j) de manera de que queden menores a la izquierda y mayores a derecha del mismo
- se retorna j, ya que en la poscision de j esta el pivote solo queda organizar las otras dos mitades usandolo.
en java una forma de implementar quicksort seria la siguiente.
public class mainClass {
public static void main(String[] args) {
int[] input = {1, 10, 10, 8, 6, 10, 1};
quickSort(input, 0, input.length);
printArray(input);
}
public static boolean printArray(int[] input) {
if (input.length == 0) return false;
System.out.println("");
for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + " ");
}
return true;
}
public static void quickSort(int[] input, int min, int max) {
if (min < max) {
int j = partition(input, min, max);
quickSort(input, min, j);
quickSort(input, j + 1, max);
}
}
public static int partition(int[] input, int min, int max) {
int i = min;
int j = max;
int pivot = input[min];
while (i < j) {
do {
i++;
} while (i < input.length && input[i] < pivot);
do {
j--;
} while (input[j] > pivot);
if (i < j) {
switchTheVariables(input, i, j);
}
}
switchTheVariables(input, min, j);
return j;
}
public static void switchTheVariables(int[] input, int a, int b) {
int temporal = input[a];
input[a] = input[b];
input[b] = temporal;
}
}
implementar quicksort o bubble sort tan literal es interesante como ejercisio pero creo que tiene mas sentido utilizar el ordenamiento que ofrece el lenguaje, para ordenar en java podemos hacerlo asi
import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
public class runjava {
public static void main(String []args){
Integer[] arrayInt={1,3,2,1,5,3,1};
Arrays.sort(arrayInt);
printArray(arrayInt);
List<Integer> listInt=new ArrayList<Integer>();
listInt.add(1);
listInt.add(3);
listInt.add(2);
listInt.add(1);
listInt.add(5);
Collections.sort(listInt);
System.out.print(listInt);
}
public static <A> boolean printArray(A[] array){
if(array.length==0) return false;
for(int i=0;i< array.length;i++){
System.out.print(" "+array[i]);
}
return true;
}
}
y si tuvieramos que implementar basados en un criterio propio x(por ejemplo ordenar un arreglo de string que sabemos son entero) o usando un campo especifico de una clase, o cualquier logica que quisieramos podriamos crear un comparator para informarle a java como queremos que ordene y hacerlo asi.
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class runJava{
public static void main(String[] args) {
Comparator<String> customComparator = ((a, b) -> {
Integer aInt = Integer.valueOf(a);
Integer bInt = Integer.valueOf(b);
return aInt > bInt ? 1 : aInt < bInt ? -1 : 0;
});
List<String> listInt = new ArrayList<String>();
listInt.add("1");
listInt.add("3");
listInt.add("2");
listInt.add("1");
listInt.add("5");
Collections.sort(listInt);
System.out.print(listInt);
}
}
Referencias.
1. bubble sort https://www.geeksforgeeks.org/bubble-sort/
2. quicksort explicacion. https://www.youtube.com/watch?v=7h1s2SojIRw
3. por que gusta quicksort https://cs.stackexchange.com/questions/3/why-is-quicksort-better-than-other-sorting-algorithms-in-practice
4. https://www.opinionatedgeek.com/codecs/htmlencoder
