Introducci贸n
Contenido
La clasificaci贸n es un aspecto crucial de la digesti贸n de datos. Para nosotros, los humanos, es mucho m谩s natural ordenar las cosas que tienen algo en com煤n, como la fecha de publicaci贸n, el orden alfab茅tico, los art铆culos que pertenecen a un autor, del m谩s peque帽o al m谩s grande, etc. Esto hace que sea mucho m谩s f谩cil comprender los datos ya que conectados l贸gicamente en lugar de dispersos por todas partes.
Y lo que es igualmente importante, las matrices ordenadas son m谩s f谩ciles de utilizar para las computadoras. Por ejemplo, una matriz ordenada se puede buscar mucho m谩s r谩pido, como con el b煤squeda binaria algoritmo, que se ejecuta en tiempo O (logn). Un algoritmo como este simplemente no funciona sin una matriz ordenada.
Tipo de inserci贸n
La ordenaci贸n por inserci贸n es uno de los algoritmos de ordenaci贸n m谩s simples, que funciona considerablemente m谩s r谩pido en colecciones m谩s peque帽as que la ordenaci贸n por burbujas introductoria e incluso la ordenaci贸n por selecci贸n, aunque todos son algoritmos cuadr谩ticos simples (O (n2).
Es ideal para colecciones peque帽as y casi ordenadas (~ 10 elementos), lo que lo hace extremadamente 煤til cuando se usa en combinaci贸n con otros algoritmos de clasificaci贸n m谩s avanzados, como Quicksort o Merge Sort. Oficial de Java sort()
La implementaci贸n de la API de colecciones utiliz贸 un Quicksort de doble pivote, aunque se recurri贸 a Insertion Sort para colecciones de tama帽o 7
.
Por lo general, se implementa de manera imperativa (aunque tambi茅n puede ser recursiva) y representa un algoritmo estable en el lugar que funciona de maravilla en peque帽os conjuntos de datos.
Esto significa que conserva el orden relativo de los elementos duplicados despu茅s de la clasificaci贸n (en el lugar) y no requiere ninguna memoria adicional para clasificar con una complejidad de espacio constante O (1) (estable).
Insertion Sort funciona de manera muy similar a como los humanos clasifican las tarjetas en sus manos dividiendo la colecci贸n en dos partes: clasificadas y sin clasificar.
A continuaci贸n, atraviesa la partici贸n sin clasificar e inserta cada elemento en su lugar relativo correcto en la matriz ordenada.
Aqu铆 hay una representaci贸n visual de c贸mo funciona:
Si esto no tiene mucho sentido ahora, se explica paso a paso en la implementaci贸n a continuaci贸n junto con el c贸digo.
Implementaci贸n
Dicho esto, sigamos adelante e implementemos el algoritmo en matrices de enteros primitivos y una colecci贸n de objetos con un compareTo()
m茅todo para definir criterios de comparaci贸n.
Tambi茅n podr铆amos implementar el Comparable
interfaz y anular la compareTo()
m茅todo para definir los criterios de comparaci贸n y utilizar la API de colecciones, simplemente llamando al sort()
m茅todo proporcionado all铆. Sin embargo, de esa manera, no implementamos nuestra propia l贸gica de clasificaci贸n.
Ordenaci贸n de matrices
La ordenaci贸n de matrices de enteros primitivos es r谩pida y sencilla mediante la ordenaci贸n por inserci贸n:
public static void insertionSort(int array[]) {
for (int j = 1; j < array.length; j++) {
int current = array[j];
int i = j-1;
while ((i > -1) && (array[i] > current)) {
array[i+1] = array[i];
i--;
}
array[i+1] = current;
}
}
La iteraci贸n comienza en el segundo elemento (el primero se considera ordenado de forma predeterminada) y compara el primer elemento de la matriz no ordenada con el 煤ltimo elemento de la matriz ordenada.
El elemento no clasificado se “guarda” en la variable current
y si el elemento m谩s alto en la matriz ordenada es m谩s grande que el current
variable: la parte adecuada de la matriz ordenada se desplaza hacia la derecha.
Tenga en cuenta que no se han intercambiado, se ha desplazado a la derecha y ahora ambos array[j]
(se accede a trav茅s de array[i+1]
) y array[i]
tienen el mismo valor.
Luego, independientemente de si una parte de la matriz ordenada se desplaza hacia la derecha, establecemos el array[j]
a current
, insertando efectivamente el entero guardado en su lugar correcto.
Si el current
El elemento no es m谩s peque帽o que el elemento ordenado m谩s grande (es decir, es m谩s grande), simplemente se inserta al final donde pertenece.
Sigamos adelante y completemos una peque帽a matriz de n煤meros enteros y luego ord茅nelos:
int[] array = new int[]{1, 7, 5, 6, 9, 4, 2, 3};
insertionSort(array);
System.out.println(Arrays.toString(array));
Ejecutar este fragmento de c贸digo producir谩:
[1, 2, 3, 4, 5, 6, 7, 9]
Ordenar ArrayLists
Clasificando un ArrayList
es un ejemplo m谩s pr谩ctico / del mundo real que probablemente encontrar谩 con mucha m谩s frecuencia que los enteros primitivos.
Dado que estamos ordenando objetos seg煤n ciertos criterios, primero definamos una clase para nuestro Element
de una colecci贸n:
public class Element {
private int id;
public Element(int id) {
this.id = id;
}
// Getters and setters
public int compareTo(Element element) {
int res = 0;
if (this.id < element.getId()) {
res = -1;
}
if (this.id > element.getId()) {
res = 1;
}
return res;
}
}
Contiene un compareTo()
m茅todo que acepta otro Element
para ser comparado. En esta implementaci贸n mundana, su id
se est谩n comparando, aunque aqu铆 es donde puede ser creativo.
En su lugar, reelaboremos el algoritmo para ordenar estos objetos:
public static void insertionSortArrayList(List<Element> list) {
for (int j = 1; j < list.size(); j++) {
Element current = list.get(j);
int i = j-1;
while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
list.set(i+1, list.get(i));
i--;
}
list.set(i+1, current);
}
}
No ha cambiado mucho, espere utilizar los m茅todos proporcionados por un List
y comparando los elementos con nuestra costumbre compareTo()
m茅todo. Aqu铆, comprobamos si el resultado de la comparaci贸n es 1
ya que eso significa que el primer elemento es m谩s grande que el segundo como se define en nuestro m茅todo.
Ahora, poblaremos un ArrayList
con algunos elementos y mezclarlo:
List<Element> list = new ArrayList<>();
// Create elements w/ IDs 0-24
for (int i = 0; i < 25; i++) {
list.add(new Element(i));
}
// Move the elements to a random order
Collections.shuffle(list);
Y ahora, ordenemos esa lista:
// Print list before sorting
list.forEach(e -> System.out.print(e.getId() + ", "));
// Sort the list
insertionSortArrayList(list);
System.out.println();
// Print sorted list
list.forEach(e -> System.out.print(e.getId() + ", "));
Este fragmento de c贸digo nos dar谩:
4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
Complejidad del tiempo
La complejidad del tiempo, tanto la media como la peor del tipo de inserci贸n es O (n2), que es bastante terrible. Hay muchas mejores complejidades de tiempo disponibles a trav茅s de otros algoritmos de clasificaci贸n m谩s avanzados, aunque lo que hace que Insertion Sort se destaque es lo r谩pido que es en colecciones peque帽as y casi ordenadas.
Intentemos sincronizarlo a trav茅s de 5 ejecuciones de colecciones peque帽as y 5 ejecuciones de colecciones grandes.
List<Element> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add(new Element(i));
}
Collections.shuffle(list);
// Print shuffled list
list.forEach(e -> System.out.print(e.getId() + ", "));
long startTime1 = System.nanoTime();
insertionSort.insertionSortArrayList(list);
long endTime1 = System.nanoTime();
// Print sorted collection
list.forEach(e -> System.out.print(e.getId() + ", "));
System.out.println();
// Print runtime in nanoseconds
System.out.println("Insertion Sort runtime: " + (endTime1 - startTime1));
Orden de inserci贸n (10) Hora (s)
Primer intento | 0,000058 |
Segunda ejecuci贸n | 0,000085 |
Tercera carrera | 0,000073 |
Cuarta carrera | 0,000060 |
Quinta carrera | 0,000073 |
Orden de inserci贸n (10k) tiempo (s)
Primer intento | 0.091 |
Segunda ejecuci贸n | 0,125 |
Tercera carrera | 0.104 |
Cuarta carrera | 0.108 |
Quinta carrera | 0,123 |
En comparaci贸n con Bubble Sort, que tiene la misma complejidad de tiempo, Insertion Sort es ~ 5 veces m谩s r谩pido.
Conclusi贸n
La ordenaci贸n por inserci贸n es uno de los algoritmos de ordenaci贸n m谩s simples, que funciona considerablemente m谩s r谩pido en colecciones m谩s peque帽as que la ordenaci贸n por burbujas introductoria e incluso la ordenaci贸n por selecci贸n, aunque todos son algoritmos cuadr谩ticos simples (O (n2).
Es ideal para colecciones peque帽as y casi ordenadas (~ 10 elementos), lo que lo hace extremadamente 煤til cuando se usa en combinaci贸n con otros algoritmos de clasificaci贸n m谩s avanzados, como Quicksort o Merge Sort.
Por lo general, se implementa de manera imperativa (aunque tambi茅n puede ser recursiva) y representa un algoritmo estable en el lugar que funciona de maravilla en peque帽os conjuntos de datos.
Esto significa que conserva el orden relativo de los elementos duplicados (en el lugar) y no requiere memoria adicional para ordenar con una complejidad de espacio constante O (1) (estable).!