Lo que preguntan en una entrevista: revisión de algoritmos, parte 1

¡Buenas tardes a todos! En los proyectos se utilizan varios tipos de algoritmos con más frecuencia de lo que piensas. Por ejemplo, necesitamos ordenar algunos datos según ciertos parámetros (columnas) para poder navegar por ellos sin mucho esfuerzo. Por tanto, no tiene nada de extraño que durante las entrevistas de trabajo se les pueda preguntar sobre uno u otro algoritmo básico, y quizás se les encomiende la tarea de implementarlo mediante código. Y ya que estás en este sitio, me atrevería a suponer que escribes en Java. Por eso, hoy te invito a familiarizarte con algunos algoritmos básicos y ejemplos específicos de su implementación en Java. Con algunos me refiero a:

1. 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.
2. Algoritmo codicioso.
3. Algoritmos de búsqueda de caminos:
   • arrastrándose en profundidad
   • rastreo amplio.
4. El algoritmo de transporte es el algoritmo de Dijkstra.

Bueno, sin más, 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 al mismo tiempo tiene una de las velocidades de ejecución más bajas. Como ejemplo, considere la clasificación por burbujas para números en orden ascendente. Imaginemos una cadena de números colocados aleatoriamente para la cual se realizarán los siguientes pasos, comenzando desde el inicio de la cadena:

• comparar dos números;
• si el número de la izquierda es mayor, cámbielos;
• moverse una posición hacia la derecha.

Después de recorrer toda la cadena y realizar estos pasos, encontraremos que el número más grande está al final de nuestra serie de números. A continuación se realiza exactamente el mismo paso a lo largo de la cadena, siguiendo los pasos descritos anteriormente. Pero en esta ocasión no incluiremos el último elemento de la lista, ya que es el más grande y ya está en el último lugar, como debe ser. Nuevamente obtendremos el último elemento al final de nuestra serie de números en cuestión. En consecuencia, los dos números más grandes ya estarán en sus lugares. Y nuevamente se inicia el paso a lo largo de la cadena, excluyendo los elementos que ya están en su lugar, hasta que todos los elementos estén en el orden requerido. Veamos la implementación de la clasificación de burbujas en 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, aquí no hay nada complicado, y todo parece ir genial, si no fuera por un “pero”... La clasificación de burbujas es muy, muy lenta, con una complejidad temporal de O(N²) , ya que hemos anidado bucles. El paso externo a través de los elementos se realiza en N veces, el interno también en N veces, y como resultado obtenemos N*N , N² iteraciones. Puedes estudiar este tipo de clasificación con más detalle en este artículo .

Ordenar por selección

Este algoritmo es similar al de clasificación de burbujas, pero funciona un poco más rápido. Nuevamente, como ejemplo, tomemos una serie de números que queremos ordenar en orden ascendente. La esencia del algoritmo es recorrer secuencialmente todos los números y seleccionar el elemento más pequeño, que tomamos e intercambiamos lugares con el elemento más a la izquierda (elemento 0). Aquí tenemos una situación similar a la clasificación por burbujas, pero en este caso el elemento ordenado será el más pequeño. Por lo tanto, el siguiente paso por los elementos comenzará con el elemento en el índice 1. Nuevamente, estos pasos se repetirán hasta que todos los elementos estén 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++) { // внешний обычный  цикл
           int min = i;

           for (int j = i + 1; j < array.length; j++) { // обычный цикл, но с отчетом с сортированных чисел
               if (array[j] < array[min]) {
                   min = j;
               }
           }
           int temp = array[i];     // вставка отссортиованного числа, в положеную ему ячейку
           array[i] = array[min];
           array[min] = temp;
       }
   }
}

Este algoritmo es superior al tipo de burbuja, porque aquí el número de permutaciones necesarias se reduce de O(N²) a O(N): no empujamos un elemento a través de toda la lista, pero aún así, el número de comparaciones sigue siendo O(N²). ) . Para aquellos que deseen aprender más sobre este algoritmo, recomiendo este material .

Tipo de inserción

Una vez más, como ejemplo, tomemos una serie de números que queremos ordenar en orden ascendente. Este algoritmo consiste en colocar un marcador, a la izquierda del cual los elementos ya estará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 ya ordenada. Así, la parte ordenada seguirá creciendo hasta que se hayan examinado todos los elementos. Te preguntarás: ¿dónde puedo conseguir esa parte de los elementos que ya están ordenados y tras los cuales hay que poner un marcador? Pero la matriz del primer elemento ya está ordenada, ¿no? Veamos 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 - разделяющий маркер
           int temp = array[i]; // делаем копию помеченного elemento
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // пока не будет найден меньший элемент
               array[j] = array[j - 1]; // сдвигаем элементы вправо
               --j;
           }
           array[j] = temp;   // вставляем отмеченный элемент, в положеное ему место
       }
   }
}

Este tipo de clasificación es superior a los descritos anteriormente, porque a pesar de que el tiempo de ejecución es el mismo - O(N²) , este algoritmo funciona dos veces más rápido que la clasificación por burbujas y un poco más rápido que la clasificación por selección. Leer más aquí .

Ordenar conchas

Este tipo, por su naturaleza, es un tipo de inserción modificado. ¿De qué estoy hablando? Vayamos en orden. Se selecciona un paso y hay muchos enfoques para esta elección. No entraremos en esta cuestión con demasiado detalle. Dividamos nuestra matriz por la mitad y obtengamos un número determinado; este será nuestro paso. Entonces, si tenemos 9 elementos en la matriz, entonces nuestro paso será 9/2 = 4,5 . Descartamos la parte fraccionaria y obtenemos 4 , ya que los índices de la matriz son solo números enteros. Con este paso crearemos conexiones para nuestros grupos. Si un elemento tiene índice 0, entonces el índice del siguiente elemento de su grupo es 0+4 , es decir, 4 . El tercer elemento tendrá un índice de 4+4 , el cuarto tendrá un índice de 8+4 , y así sucesivamente. Para el segundo grupo, el primer elemento será 1,5,9…. En el tercer y cuarto grupo todo será exactamente igual. 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 para nosotros están marcados como miembros del mismo grupo: { 6 , 3 , 8 , 8 , 6 , 9 , 4 , 11 , 1 } Además, dentro de estos grupos se produce el tipo de inserción , después del cual los grupos se verán así: I - {1,6,6} II - {3,9} III - {4,8} IV - {8 ,11} En el array general, las celdas ocupadas por los grupos , seguirán siendo las mismas, pero el orden dentro de ellas cambiará, según el orden de los grupos anteriores: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } La matriz está un poco más ordenada, ¿no? El siguiente paso será dividir por 2: 4/2 = 2 Tenemos dos grupos: I - {1,4,6,8,6} II - {3,8,9,11} B matriz general: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Revisamos ambos grupos usando el algoritmo de ordenación por inserción y obtenemos una matriz: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8} Ahora nuestra matriz está casi ordenada. Queda la última iteración del algoritmo: dividimos el paso por 2: 2/2 = 1. Obtenemos un grupo, la matriz completa: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } Por el cual pasamos por el algoritmo de ordenación por inserción y obtenemos: { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } Veamos cómo podemos mostrar esta ordenación 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 = 0; numberOfGroup < length - step; numberOfGroup++) {// проходим по всем нашим группам
              int j = numberOfGroup;
               while (j >= 0 && array[j] > array[j + step]) {//clasificación вставкой внутри группы
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // уменьшаем наш шаг
       }
   }
}

Por el momento, la eficacia de la clasificación Shell no está realmente demostrada, ya que los resultados difieren en diferentes situaciones. Las estimaciones obtenidas de los experimentos varían de O(N ^3/2 ) a O(N ^7/6 ) .

Ordenación rápida

Este es uno de los algoritmos más populares y, por lo tanto, vale la pena prestarle especial atención. La esencia de este algoritmo es que se selecciona un elemento pivote de una lista de elementos, esencialmente cualquier elemento con respecto al cual se deban ordenar los valores restantes. Valores menores que a la izquierda, valores mayores que a la derecha. A continuación, el elemento de soporte también selecciona las partes derecha e izquierda y sucede lo mismo: los valores se clasifican en relación con estos elementos, luego los elementos de soporte se seleccionan de las partes resultantes, y así sucesivamente hasta que obtengamos un elemento ordenado. fila. Este algoritmo en Java se implementa mediante 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)// condición выхода из рекурсии,  если длина массива равна 0
           return;

       if (min >= max) //выходим, так Cómo нечего уже делить
           return;


       int middle = min + (max - min) / 2;  // выбираем середину
       int middleElement = array[middle];


       int i = min, j = max;
       while (i <= j) {  // относительно elemento middle определяемменьшие элементы слева, большие справа
           while (array[i] < middleElement) {
               i++;
           }
           while (array[j] > middleElement) {
               j--;
           }

           if (i <= j) {      //меняем местами
               int temp = array[i];
               array[i] = array[j];
               array[j] = temp;
               i++;
               j--;
           }
       }

       if (min < j) // запускаем рекурсию с elementoми меньшими чем middle
           recursionFastSort(array, min, j);

       if (max > i)// запускаем рекурсию с elementoми большими чем middle
           recursionFastSort(array, i, max);
   }
}

Sin duda, el algoritmo Quicksort es considerado el más popular, ya que en la mayoría de situaciones se ejecuta más rápido que otras, en tiempo O(N*logN) .

Combinar ordenar

Esta clasificación también es popular. Se refiere a uno de los tipos de algoritmos que funcionan según el principio de "divide y vencerás": en ellos primero dividimos las tareas en partes mínimas (la clasificación rápida también es un representante de tales algoritmos ). 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 queden las partes indivisibles más pequeñas. Las partes menos indivisibles son cuando cada matriz tiene un elemento, lo que significa que dicha matriz se considera automáticamente ordenada.

Conquistar:

Aquí es donde comienza el proceso que le da el nombre al algoritmo: fusión . Para hacer esto, tome las dos matrices ordenadas resultantes y combínelas en una. En este caso, el más pequeño de los primeros elementos de las dos matrices se escribe en la matriz resultante y esta operación se repite hasta que no haya más elementos en las dos matrices. Es decir, si tenemos dos arrays mínimos {6} y {4} , se compararán sus valores y se escribirá el resultado: {4,6} . Si hay matrices ordenadas {4,6} y {2,8} , primero se compararán los valores 4 y 2 , de los cuales 2 se escribirán en la matriz resultante. Después de esto se compararán 4 y 8 , se anotará 4 y al final se compararán 6 y 8 . En consecuencia, se escribirá 6, y solo después - 8. Como resultado, obtendremos la matriz resultante: {2,4,6,8} . ¿Cómo se verá esto en el código Java? Para procesar 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);// массив для сортировки
       int[] bufferArr = new int[array1.length];// буферный массив
       return recurtionMergeSort(sortArr, bufferArr, 0, array1.length);
   }


   public static int[] recurtionMergeSort(int[] sortArr, int[] bufferArr,
                                          int startIndex, int endIndex) {
       if (startIndex >= endIndex - 1) {// выход из массива, когда в рассматриваемом промежутке массива, только один элемент
           return sortArr;
       }

       // запускаем рекурсию, чтобы получить два отсортированных массива:
       int middle = startIndex + (endIndex - startIndex) / 2;
       int[] firstSortArr = recurtionMergeSort(sortArr, bufferArr, startIndex, middle);
       int[] secondSortArr = recurtionMergeSort(sortArr, bufferArr, middle, endIndex);

       // Слияние отсортированных массивов:
       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, trasladamos el método recursivo a uno intermedio para que el usuario no tenga que molestarse en configurar argumentos predeterminados adicionales, sino que simplemente pueda especificar la matriz que debe ordenarse. Dado que este algoritmo es similar a un borrado más rápido, su velocidad de ejecución es la misma: O(N*logN) .

2. Algoritmos codiciosos

Un algoritmo codicioso es un enfoque que toma decisiones localmente óptimas en cada etapa y supone que la solución final también será óptima. La solución “óptima” es la que ofrece el beneficio más obvio e inmediato en un determinado paso/etapa. Para considerar este algoritmo, elegiremos un problema bastante común: la mochila. Finjamos por un segundo que eres un ladrón. Entraste en una tienda por la noche con una mochila y frente a ti hay una serie de bienes que puedes robar. Pero al mismo tiempo, la capacidad de la mochila es limitada: no más de 30 unidades convencionales. Al mismo tiempo, quieres llevar un conjunto de mercancías del máximo valor que quepan en tu mochila. ¿Cómo decides qué poner? Entonces, el algoritmo codicioso para el problema de la mochila consta de los siguientes pasos (asumimos que todos los objetos caben en la mochila):

1. Elija el artículo más caro entre los que aún no han sido tocados.
2. Si cabe en tu mochila, mételo allí; si no, sáltatelo.
3. ¿Has clasificado todos los elementos? Si no volvemos al punto 1, en caso afirmativo salimos corriendo de la tienda, ya que nuestro objetivo aquí está cumplido.

Veamos esto, pero en Java. Así es como se verá la clase Artículo:

public class Item implements Comparable<Item> {
   private String name;
   private int weight;
   private int cost;

   public Item(String name, int weight, int cost) {
       this.name = name;
       this.weight = weight;
       this.cost = cost;
   }

   public String getName() {
       return name;
   }

   public int getWeight() {
       return weight;
   }

   public int getCost() {
       return cost;
   }

   @Override
   public int compareTo(Item o) {
       return this.cost > o.cost ? -1 : 1;
   }
}

No hay nada especial aquí: tres campos ( nombre , peso , coste ) para especificar las características del artículo. Además, como puedes ver, aquí se implementa la interfaz Comparable para que podamos ordenar nuestros Artículos por precio. A continuación nos fijamos en la clase de nuestra mochila - Bolsa :

public class Bag {
   private final int maxWeight;
   private List<Item> items;
   private int currentWeight;
   private int currentCost;

   public Bag(int maxWeight) {
       this.maxWeight = maxWeight;
       items = new ArrayList<>();
       currentCost = 0;
   }

   public int getMaxWeight() {
       return maxWeight;
   }

   public int getCurrentCost() {
       return currentCost;
   }

   public int getCurrentWeight() {
       return currentWeight;
   }

   public void addItem(Item item) {
       items.add(item);
       currentWeight += item.getWeight();
       currentCost += item.getCost();
   }
}

• maxWeight es la capacidad de nuestra mochila, que se establece al crear el objeto;
• artículos : objetos en la mochila;
• currentWeight , currentCost : el peso actual y el costo de todas las cosas en la mochila, que aumentamos al agregar un nuevo artículo en el método addItem .

En realidad, vayamos a la clase, donde ocurre toda la acción:

public class Solution {

   public static void main(String[] args) {
       List<Item> items = new ArrayList<>();
       items.add(new Item("гитара",7, 800));
       items.add(new Item("утюг",6, 500));
       items.add(new Item("чайник",3, 300));
       items.add(new Item("лампа",4, 500));
       items.add(new Item("телевизор",15, 2000));
       items.add(new Item("ваза",2, 450));
       items.add(new Item("миксер",1, 400));
       items.add(new Item("блендер",3, 200));

       Collections.sort(items);

       Bag firstBag = new Bag(30);

       fillBackpack(firstBag, items);

       System.out.println("Вес рюкзака состовляет - " + firstBag.getCurrentWeight() +
               ", общая стоимость вещей в рюкзаке - " + firstBag.getCurrentCost());
}
}

Primero, creamos una lista de elementos y la ordenamos. Crea un objeto bolsa con capacidad de 30 unidades. A continuación, enviamos los elementos y el objeto bolsa al método fillBackpack , en el que, de hecho, la mochila se llena mediante un algoritmo codicioso:

public static void fillBackpack(Bag bag, List<Item> items) {
   for (Item item : items) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + item.getWeight()) {
            bag.addItem(item);
       }
   }
}

Todo es sumamente sencillo: comenzamos a revisar la lista de artículos ordenados por costo y los metemos en una bolsa, si la capacidad lo permite. Si no lo permite, se omitirá el elemento y se continuará el paso por los elementos restantes hasta el final de la lista. Al ejecutar main, obtenemos el siguiente resultado en la consola: En realidad, 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 podríamos modernizar un poco nuestra solución para poder equipar una mochila con un coste total mayor? Echemos un vistazo a cómo se puede hacer esto:

public static void effectiveFillBackpack(Bag bag, List<Item> items) {
   Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
   for (Item item : items) {
       sortByRatio.put((double)item.getCost() / 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 peso-precio de cada artículo. Por así decirlo, ¿cuánto cuesta una unidad de un artículo determinado? Y por estos valores clasificamos nuestros artículos y los añadimos a nuestra bolsa. Corramos:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

System.out.println("Вес рюкзака составляет - " + secondBag.getCurrentWeight() +
       ", общая стоимость вещей в рюкзаке - " + secondBag.getCurrentCost());

Obtenemos la salida a la consola: Un poquito mejor ¿no? Un algoritmo codicioso toma una decisión localmente óptima en cada paso con la expectativa de que la solución final también sea óptima. Esto no siempre está justificado, pero para muchos problemas los algoritmos codiciosos proporcionan un óptimo. La complejidad temporal de este algoritmo es O(N) , lo cual es bastante bueno, ¿verdad? Bueno, con esto, la primera parte de este artículo ha llegado a su fin. Si estás interesado en la continuación de este artículo, que hablará sobre gráficos y algoritmos relacionados con ellos, puedes encontrarlo aquí .