Los proyectos de desarrollo usan varios algoritmos con más frecuencia de lo que piensas. Por ejemplo, supongamos que necesitamos ordenar algunos datos por ciertos parámetros (columnas) para que podamos navegar a través de los datos sin mucho esfuerzo. Así que no sería nada extraño que un entrevistador de trabajo te pregunte sobre un algoritmo básico específico y quizás te dé la tarea de implementarlo usando código. Y dado que está en este sitio web, seré tan atrevido como para asumir que está escribiendo en Java. Por eso hoy te sugiero que te familiarices con algunos algoritmos básicos y con ejemplos específicos de cómo implementarlos en Java. Por "algunos", quiero decir:
Descripción general de los algoritmos de clasificación de matrices:
ordenamiento de burbuja,
clasificación de selección,
tipo de inserción,
clasificación de conchas,
ordenación rápida,
ordenar por fusión,
Algoritmos codiciosos
Algoritmos de búsqueda de caminos
búsqueda en profundidad
búsqueda en amplitud
Algoritmo de ruta más corta primero de Dijkstra
Bueno, sin más preámbulos, pongámonos manos a la obra.
1. Descripción general de los algoritmos de clasificación
Ordenamiento de burbuja
Este algoritmo de clasificación es conocido principalmente por su simplicidad, pero también es uno de los más lentos. Como ejemplo, consideremos un tipo de burbuja para números en orden ascendente. Imaginemos una secuencia aleatoria de números. Realizaremos los siguientes pasos en estos números, comenzando desde el comienzo de la secuencia:
comparar dos números;
si el número de la izquierda es mayor, cámbielos;
mover una posición a la derecha.
Después de realizar estos pasos en toda la secuencia, encontraremos que el número más grande está al final de nuestra serie de números. Luego hacemos otra pasada sobre la secuencia, ejecutando exactamente los mismos pasos que arriba. Pero esta vez no incluiremos el último elemento de la lista, ya que es el número más grande y ya precisamente donde debería estar cuando se ordenan los números. Una vez más, terminaremos moviendo el siguiente número más grande al final de nuestra secuencia. Por supuesto, eso significa que los dos números más grandes están parados en sus lugares apropiados. Nuevamente hacemos pases sobre la secuencia, excluyendo los elementos que ya están en sus lugares, hasta que todos los elementos estén en el orden requerido. Echemos un vistazo a cómo se implementa la ordenación de burbujas en el código Java:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
bubbleSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void bubbleSort(int[] array) {
for(int i = array.length -1; i > 1; i--) {
for (int j = 0; j < i; j++) { //
if (array[j] > array[j+1]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
}
Como puedes ver, no hay nada complicado aquí. Todo parece genial y lo sería si no fuera por una deficiencia: la ordenación de burbujas es muy, muy lenta. Su complejidad de tiempo es O(N²), ya que tenemos bucles anidados. El bucle exterior sobre los elementos se realiza N veces. El ciclo interno también se ejecuta N veces. Como resultado, obtenemos N*N, o N², iteraciones.
Clasificación de selección
Este algoritmo es similar al tipo de burbuja, pero funciona un poco más rápido. Nuevamente, como ejemplo, tomemos una secuencia de números que queremos organizar en orden ascendente. La esencia de este algoritmo es iterar secuencialmente a través de todos los números y seleccionar el elemento más pequeño, que tomamos e intercambiamos con el elemento más a la izquierda (el elemento 0). Aquí tenemos una situación similar a la clasificación por burbujas, pero en este caso nuestro elemento ordenado será el más pequeño. Por lo tanto, la siguiente pasada por los elementos comenzará desde el elemento con índice 1. Repetiremos estas pasadas hasta que todos los elementos hayan sido ordenados. Implementación en Java:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
for (int i = 0; i < array.length-1; i++) { // An ordinary outer loop
int min = i;
for (int j = i + 1; j < array.length; j++) { // An ordinary loop, but one that accounts for the sorted numbers
if (array[j] < array[min]) {
min = j;
}
}
int temp = array[i]; // Put the sorted number in the proper cell
array[i] = array[min];
array[min] = temp;
}
}
}
Este algoritmo es superior al tipo de burbuja, porque aquí el número de cambios requeridos se reduce de O(N²) a O(N). No estamos impulsando un elemento a través de toda la lista, pero la cantidad de comparaciones sigue siendo O (N²).
Tipo de inserción
Consideramos otra secuencia de números que queremos organizar en orden ascendente. Este algoritmo consiste en colocar un marcador, donde todos los elementos a la izquierda del marcador ya están parcialmente ordenados entre sí. En cada paso del algoritmo, uno de los elementos será seleccionado y colocado en la posición deseada en la secuencia ordenada parcialmente. Así, la parte clasificada irá creciendo hasta que se hayan examinado todos los elementos. ¿Se pregunta cómo obtiene el subconjunto de elementos que ya están ordenados y cómo determinamos dónde colocar el marcador? Pero la matriz compuesta por el primer elemento ya está ordenada, ¿no es así? Echemos un vistazo a la implementación en Java:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
insertionSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) { // i is the dividing marker
int temp = array[i]; // Make a temporary copy of the marked element
int j = i;
while (j > 0 && array[j - 1] >= temp) { // Until a smaller element is found
array[j] = array[j - 1]; // We shift the element to the right
--j;
}
array[j] = temp; // Insert the marked element in its proper place
}
}
}
Este tipo de clasificación es superior a las descritas anteriormente, ya que a pesar de que tiene el mismo tiempo de ejecución O(N²), este algoritmo es dos veces más rápido que la clasificación de burbujas y un poco más rápido que la clasificación de selección.
Clasificación de concha
Esta ordenación es esencialmente una ordenación por inserción modificada. ¿De qué estoy hablando? Pongamos primero lo primero. Primero debemos elegir un intervalo. Hay muchos enfoques para hacer esta elección. No entraremos en demasiados detalles sobre esto. Dividamos nuestra matriz por la mitad y obtengamos un número: este será nuestro intervalo. Entonces, si tenemos 9 elementos en nuestra matriz, entonces nuestro intervalo será 9/2 = 4.5. Descartamos la parte fraccionaria y obtenemos 4, ya que los índices de los arreglos solo pueden ser números enteros. Usaremos este intervalo para formar nuestros grupos. Si un elemento tiene el índice 0, entonces el índice del siguiente elemento en su grupo es 0+4, es decir, 4. El tercer elemento tendrá el índice 4+4, el cuarto, 8+4, y así sucesivamente. En el segundo grupo, el primer elemento será 1,5,9... En el tercer y cuarto grupo, la situación será la misma. Como resultado, de la matriz de números {6,3,8,8,6,9,4,11,1} obtenemos cuatro grupos: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} Conservan sus lugares en la matriz general, pero los hemos marcado como miembros del mismo grupo: {6,3,8,8,6,9,4,11,1} A continuación, inserción orden se aplica a estos grupos, y luego se ven así: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} En la matriz general, el las celdas ocupadas por los grupos seguirán siendo las mismas, pero su orden interno cambiará, de acuerdo con el orden de los grupos anteriores: {1,3,4,8,6,9,8,11,6} La matriz se ha convertido en un poco más ordenado, ¿no? El siguiente intervalo se dividirá por 2: 4/2 = 2 Tenemos dos grupos: I — {1,4,6,8,6} II — {3,8,9,11} En el arreglo general, tenemos : {1,3,4,8,6,9,8,11,6} Ejecutamos el algoritmo de clasificación por inserción en ambos grupos y obtenemos esta matriz: {1,3,4,8,6,9,6, 11, 8} Ahora nuestra matriz está casi ordenada. Necesitamos realizar una iteración final del algoritmo: dividimos el intervalo por 2: 2/2 = 1. Obtenemos un grupo compuesto por la matriz completa: {1,3,4,8,6,9,6,11 ,8} Ejecutando el algoritmo de ordenación por inserción en eso, obtenemos: {1,3,4,6,6,8,8,9,11} Echemos un vistazo a cómo podemos hacer que esta ordenación cobre vida en código Java:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
sortBySelect(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void sortBySelect(int[] array) {
int length = array.length;
int step = length / 2;
while (step > 0) {
for (int numberOfGroup = 1; numberOfGroup < length - step; numberOfGroup++) { // We pass over all of our groups
int j = numberOfGroup;
while (j >= 0 && array[j] > array[j + step]) { // Insertion sort inside the group
int temp = array[j];
array[j] = array[j + step];
array[j + step] = temp;
j--;
}
}
step = step / 2; // Shrink the interval
}
}
}
Por el momento, el desempeño de Shellsort no es fácil de caracterizar, ya que los resultados difieren en diferentes situaciones. Las estimaciones experimentales van desde O(N 3/2 ) a O(N 7/6 ).
Ordenación rápida
Este es uno de los algoritmos más populares, por lo que vale la pena prestarle especial atención. La esencia de este algoritmo es que se selecciona un elemento pivote en una lista de elementos. Ordenamos todos los demás elementos en relación con el elemento pivote. Los valores menores que el elemento pivote están a la izquierda. Valores mayores que el de la derecha. A continuación, los elementos pivote también se seleccionan en las partes derecha e izquierda, y sucede lo mismo: los valores se ordenan en relación con estos elementos. Luego se seleccionan elementos de pivote en las partes recién formadas, y así sucesivamente hasta obtener una secuencia ordenada. La siguiente implementación de Java de este algoritmo utiliza la recursividad:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
fastSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static void fastSort(int[] array) {
recursionFastSort(array, 0, array.length - 1);
}
public static void recursionFastSort(int[] array, int min, int max) {
if (array.length == 0) // Condition for exiting recursion if the array length is 0
return;
if (min> = max) // Terminate the recursion, since there is nothing to divide
return;
int middle = min + (max - min) / 2; // Select the middle
int middleElement = array[middle];
int i = min, j = max;
while (i <= j) { // Every element less than the middle element will be to the left, and large ones will be to the right
while (array[i] < middleElement) {
i++;
}
while (array[j] > middleElement) {
j--;
}
if (i <= j) { // Swap places
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (min < j) // Make a recursive call on the elements that are less than middle
recursionFastSort(array, min, j);
if (max > i) // Make a recursive call on the elements larger than middle
recursionFastSort(array, i, max);
}
}
Sin duda, el algoritmo quicksort es el más popular, ya que en la mayoría de las situaciones se ejecuta más rápido que en otras. Su complejidad temporal es O(N*logN).
Ordenar por fusión
Este tipo también es popular. Es uno de los muchos algoritmos que se basa en el principio de "divide y vencerás". Dichos algoritmos primero dividen el problema en partes manejables (quicksort es otro ejemplo de dicho algoritmo). Entonces, ¿cuál es la esencia de este algoritmo?
Dividir:
La matriz se divide en dos partes de aproximadamente el mismo tamaño. Cada una de estas dos partes se divide en dos más, y así sucesivamente hasta que quedan las partes indivisibles más pequeñas posibles. Tenemos las partes indivisibles más pequeñas cuando cada matriz tiene un elemento, es decir, una matriz que ya está ordenada.
Conquistar:
Aquí es donde comenzamos el proceso que dio nombre al algoritmo: fusionar. Para hacer esto, tomamos las dos matrices ordenadas resultantes y las fusionamos en una sola. En este caso, el más pequeño de los primeros elementos de las dos matrices se escribe en la matriz resultante. Esta operación se repite hasta que se hayan copiado todos los elementos de estas dos matrices. Es decir, si tenemos dos matrices mínimas {6} y {4}, comparamos sus valores y generamos este resultado combinado: {4,6}. Si hemos ordenado las matrices {4,6} y {2,8}, primero comparamos los valores 4 y 2 y luego escribimos 2 en la matriz resultante. Después de eso, se compararán 4 y 8, y escribiremos 4. Finalmente, se compararán 6 y 8. En consecuencia, escribiremos 6, y solo después de eso escribiremos 8. Como resultado, obtenemos la siguiente matriz combinada: {2,4,6,8}. ¿Cómo se verá esto en código Java? Para ejecutar este algoritmo, nos será conveniente utilizar la recursividad:
public class Solution {
public static void main(String[] args) {
int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
testArr = mergeSort(testArr);
for (int i : testArr) {
System.out.println(i);
}
}
public static int[] mergeSort(int[] array1) {
int[] sortArr = Arrays.copyOf(array1, array1.length); // Array for sorting
int[] bufferArr = new int[array1.length];// Buffer array
return recursionMergeSort(sortArr, bufferArr, 0, array1.length);
}
public static int[] recursionMergeSort(int[] sortArr, int[] bufferArr,
int startIndex, int endIndex) {
if (startIndex> = endIndex - 1) { // Return the array when there is only one element left in the array range under consideration
return sortArr;
}
// Make a recursive call to get two sorted arrays:
int middle = startIndex + (endIndex - startIndex) / 2;
int[] firstSortArr = recursionMergeSort(sortArr, bufferArr, startIndex, middle);
int[] secondSortArr = recursionMergeSort(sortArr, bufferArr, middle, endIndex);
// Merge the sorted arrays:
int firstIndex = startIndex;
int secondIndex = middle;
int destIndex = startIndex;
int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
while (firstIndex < middle && secondIndex < endIndex) {
result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
}
while (firstIndex < middle) {
result[destIndex++] = firstSortArr[firstIndex++];
}
while (secondIndex < endIndex) {
result[destIndex++] = secondSortArr[secondIndex++];
}
return result;
}
}
Al igual que en la clasificación rápida, movemos el método recursivo a un método intermedio para que el usuario solo necesite proporcionar la matriz que se va a clasificar y no tenga que preocuparse por proporcionar argumentos predeterminados adicionales. Este algoritmo tiene similitudes con Quicksort y, como era de esperar, su velocidad de ejecución es la misma: O(N*logN).
2. Algoritmos codiciosos
Un algoritmo codicioso es un enfoque en el que se toman decisiones localmente óptimas en cada etapa, con la suposición de que la solución final también será óptima. La solución "óptima" será aquella que ofrezca el beneficio más obvio e inmediato en cualquier paso/etapa en particular. Para explorar este algoritmo, tomemos un problema bastante común: el problema de la mochila. Finge por un momento que eres un ladrón. Has irrumpido en una tienda por la noche con una mochila (mochila). Frente a ti hay varios bienes que podrías robar. Pero al mismo tiempo, tu mochila tiene una capacidad limitada. No puede transportar más de 30 unidades de peso. También querrás llevarte el conjunto de artículos más valiosos que caben en la mochila. ¿Cómo determinas qué poner en tu bolso? Entonces,
Elija el artículo más caro que aún no se haya tomado.
Si cabe en la mochila, mételo. Si no, déjalo.
¿Ya hemos robado todo? Si no, volvemos al paso 1. Si es así, nos alejamos rápidamente de la tienda, ya que hemos logrado lo que vinimos a hacer.
Veamos esto, pero en Java. Así es como se verá la clase Item:
public class Item implements Comparable {
private String name;
private int weight;
private int value;
public Item(String name, int weight, int value) {
this.name = name;
this.weight = weight;
this.value = value;
}
public String getName() {
return name;
}
public int getWeight() {
return weight;
}
public int getValue() {
return value;
}
@Override
public int compareTo(Item o) {
return this.value > o.value ? -1 : 1;
}
}
Aquí no hay nada especial: tres campos (nombre, peso, valor) que definen las características del artículo. Además, como puede ver, la interfaz Comparable está implementada para permitirnos ordenar nuestros artículos por precio. A continuación, veremos la clase Bag, que representa nuestra mochila:
public class Bag {
private final int maxWeight;
private List<Item> items;
private int currentWeight;
private int currentValue;
public Bag(int maxWeight) {
this.maxWeight = maxWeight;
items = new ArrayList<>();
currentValue = 0;
}
public int getMaxWeight() {
return maxWeight;
}
public int getCurrentValue() {
return currentValue;
}
public int getCurrentWeight() {
return currentWeight;
}
public void addItem(Item item) {
items.add(item);
currentWeight += item.getWeight();
currentValue += item.getValue();
}
}
maxWeight es la capacidad de nuestra mochila, que se establece cuando creamos un objeto;
items representa los objetos en nuestra mochila;
currentWeight , currentValue : estos campos almacenan el peso y el valor actual de todos los artículos en la mochila, que aumentamos cuando agregamos un nuevo artículo en el método addItem.
De todos modos, vayamos ahora a la clase donde tiene lugar toda la acción:
public class Solution {
public static void main(String[] args) {
List<Item> items = new ArrayList<>();
items.add(new Item("Guitar", 7, 800));
items.add(new Item("Iron", 6, 500));
items.add(new Item("Tea pot", 3, 300));
items.add(new Item("Lamp", 4, 500));
items.add(new Item("Television", 15, 2000));
items.add(new Item("Vase", 2, 450));
items.add(new Item("Mixer", 2, 400));
items.add(new Item("Blender", 3, 200));
Collections.sort(items);
Bag firstBag = new Bag(30);
fillBackpack(firstBag, items);
System.out.println("Knapsack weight is " + firstBag.getCurrentWeight() +
". The total value of items in the knapsack is " + firstBag.getCurrentValue());
}
}
Primero, creamos una lista de elementos y la ordenamos. Creamos un objeto bolsa con capacidad para 30 unidades. A continuación, pasamos los artículos y el objeto bolsa al método fillBackpack, que llena la mochila de acuerdo con nuestro algoritmo codicioso:
Es bastante simple: comenzamos revisando una lista de artículos ordenados por costo y colocándolos en la bolsa si su capacidad lo permite. Si no hay suficiente espacio, se omitirá el elemento y continuaremos recorriendo el resto de los elementos hasta llegar al final de la lista. Una vez que ejecutemos main, esta es la salida de la consola que obtendremos:
El peso de la mochila es 29. El valor total de los artículos en la mochila es 3700
Este es un ejemplo de un algoritmo codicioso: en cada paso, se selecciona una solución localmente óptima y, al final, se obtiene una solución globalmente óptima. En nuestro caso, la mejor opción es el artículo más caro. Pero, ¿es esta la mejor solución? ¿No crees que es posible mejorar ligeramente nuestra solución para llenar nuestra mochila con artículos que tienen un valor total aún mayor? Echemos un vistazo a cómo se puede hacer esto.
public static void effectiveFillBackpack(Bag bag, List items) {
Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
for (Item item : items) {
sortByRatio.put((double)item.getValue() / item.getWeight(), item);
}
for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
bag.addItem(entry.getValue());
}
}
}
Aquí primero calculamos la relación valor-peso para cada artículo. Esto nos dice el valor de cada unidad de un artículo dado. Y luego usamos estas proporciones para clasificar nuestros artículos y agregarlos a nuestra bolsa. Ejecutemos lo siguiente:
Bag secondBag = new Bag(30);
effectiveFillBackpack(secondBag, items);
System.out.println("The weight of the knapsack is " + secondBag.getCurrentWeight() +
". The total cost of items in the knapsack is " + secondBag.getCurrentValue());
Obtenemos esta salida de la consola:
El peso de la mochila es 29. El costo total de los artículos en la mochila es 4150
Un poco mejor, ¿no? El algoritmo codicioso hace una elección localmente óptima en cada paso, con la esperanza de que la solución final también sea óptima. Esta suposición no siempre es válida, pero para muchas tareas, los algoritmos codiciosos producen una solución final óptima. La complejidad temporal de este algoritmo es O(N). Bastante bien, ¿eh?
Y dado que está en este sitio web, seré tan atrevido como para asumir que está escribiendo en Java. Por eso hoy te sugiero que te familiarices con algunos algoritmos básicos y con ejemplos específicos de cómo implementarlos en Java. Por "algunos", quiero decir:
GO TO FULL VERSION