O que perguntam em uma entrevista: revisão de algoritmos, parte 1

Boa tarde a todos! Vários tipos de algoritmos são usados ​​em projetos com mais frequência do que você imagina. Por exemplo, precisamos ordenar alguns dados de acordo com determinados parâmetros (colunas) para que possamos navegar por eles sem muito esforço. Portanto, não há nada de estranho no fato de que durante as entrevistas de emprego eles possam ser questionados sobre um ou outro algoritmo básico e talvez receber a tarefa de implementá-lo por meio de código. E já que você está neste site, atrevo-me a adivinhar que você escreve em Java. Portanto, hoje convido você a se familiarizar com alguns algoritmos básicos e exemplos específicos de sua implementação em Java. Por alguns quero dizer:

1. Visão geral dos algoritmos de classificação de array:
   • Tipo de bolha,
   • classificação de seleção,
   • classificação de inserção,
   • Tipo de concha,
   • ordenação rápida,
   • classificação de mesclagem.
2. Algoritmo ganancioso.
3. Algoritmos de localização de caminhos:
   • rastejando em profundidade
   • caminhada ampla.
4. O algoritmo de transporte é o algoritmo de Dijkstra.

Bem, sem mais delongas, vamos ao que interessa.

1. Visão geral dos algoritmos de classificação

Tipo de bolha

Esse algoritmo de classificação é conhecido principalmente por sua simplicidade, mas também possui uma das velocidades de execução mais baixas. Por exemplo, considere a classificação por bolha para números em ordem crescente. Vamos imaginar uma cadeia de números colocados aleatoriamente para a qual serão executadas as seguintes etapas, começando do início da cadeia:

• compare dois números;
• se o número à esquerda for maior, troque-os;
• mova uma posição para a direita.

Depois de percorrer toda a cadeia e realizar estas etapas, descobriremos que o maior número está no final da nossa série de números. A seguir, é realizada exatamente a mesma passagem ao longo da cadeia, seguindo os passos descritos acima. Mas desta vez não incluiremos o último elemento da lista, pois é o maior e já está em último lugar, como deveria estar. Novamente, obteremos o último elemento no final da nossa série de números em questão. Assim, os dois maiores números já estarão em seus lugares. E novamente se inicia a passagem ao longo da cadeia, excluindo os elementos que já estão no lugar, até que todos os elementos estejam na ordem exigida. Vejamos a implementação do bubble sort no 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 você pode ver, não há nada complicado aqui, e tudo parece estar ótimo, se não fosse por um “mas”... A classificação por bolha é muito, muito lenta, com uma complexidade de tempo de O(N²) , já que aninhamos rotações. A passagem externa pelos elementos é realizada N vezes, a interna também é N vezes, e como resultado obtemos N*N , N² iterações. Você pode estudar esse tipo de ordenação com mais detalhes neste artigo .

Classificando por seleção

Este algoritmo é semelhante ao bubble sort, mas funciona um pouco mais rápido. Novamente, como exemplo, tomemos uma série de números que queremos organizar em ordem crescente. A essência do algoritmo é percorrer sequencialmente todos os números e selecionar o menor elemento, que pegamos e trocamos de lugar com o elemento mais à esquerda (elemento 0). Aqui temos uma situação semelhante à classificação por bolha, mas neste caso o elemento classificado será o menor. Portanto, a próxima passagem pelos elementos começará com o elemento no índice 1. Novamente, essas passagens serão repetidas até que todos os elementos sejam classificados. Implementação em 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 é superior ao bubble sort, porque aqui o número de permutações necessárias é reduzido de O(N²) para O(N): não empurramos um elemento por toda a lista, mas mesmo assim, o número de comparações permanece O(N² ) . Para quem deseja aprender mais sobre esse algoritmo, recomendo este material .

Classificação de inserção

Mais uma vez, como exemplo, tomemos uma série de números que queremos organizar em ordem crescente. Este algoritmo consiste em colocar um marcador, à esquerda do qual os elementos já estarão parcialmente ordenados entre si. A cada etapa do algoritmo, um dos elementos será selecionado e colocado na posição desejada na sequência já ordenada. Assim, a parte classificada continuará a crescer até que todos os elementos tenham sido examinados. Você pode perguntar: onde posso conseguir aquela parte dos elementos que já estão classificados e depois dos quais você precisa colocar um marcador? Mas o array do primeiro elemento já está ordenado, não é? Vejamos a implementação em 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]; // делаем копию помеченного element
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // пока не будет найден меньший элемент
               array[j] = array[j - 1]; // сдвигаем элементы вправо
               --j;
           }
           array[j] = temp;   // вставляем отмеченный элемент, в положеное ему место
       }
   }
}

Este tipo de ordenação é superior aos descritos acima, pois apesar do tempo de execução ser o mesmo - O(N²) , este algoritmo funciona duas vezes mais rápido que a ordenação por bolha e um pouco mais rápido que a ordenação por seleção. Leia mais aqui .

Classificação de shell

Essa classificação, por natureza, é uma classificação por inserção modificada. Do que estou falando? Vamos em ordem. Uma etapa é selecionada e há muitas abordagens para essa escolha. Não entraremos neste assunto em muitos detalhes. Vamos dividir nosso array ao meio e obter um certo número - este será o nosso passo. Portanto, se tivermos 9 elementos no array, nosso passo será 9/2 = 4.5 . Descartamos a parte fracionária e obtemos 4 , já que os índices do array são apenas inteiros. Com esta etapa criaremos conexões para nossos grupos. Se um elemento tiver índice 0, então o índice do próximo elemento do seu grupo é 0+4 , ou seja, 4 . O terceiro elemento terá um índice de 4+4 , o quarto terá um índice de 8+4 e assim por diante. Para o segundo grupo, o primeiro elemento será 1,5,9…. No terceiro e quarto grupos as coisas serão exatamente iguais. Como resultado, da matriz de números {6,3,8,8,6,9,4,11,1} obtemos quatro grupos: I - {6,6,1} II - {3,9} III - {8, 4} IV - {8,11} Eles mantêm seus lugares na matriz geral, mas para nós são marcados como membros do mesmo grupo: { 6 , 3 , 8 , 8 , 6 , 9 , 4 , 11 , 1 } Mais adiante nesses grupos ocorre a ordenação por inserção , após a qual os grupos terão a seguinte aparência: I - {1,6,6} II - {3,9} III - {4,8} IV - {8 ,11} Na matriz geral, as células ocupadas pelos grupos permanecerão as mesmas, mas a ordem dentro delas mudará, de acordo com a ordem dos grupos acima: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } O array é um pouco mais ordenado, não é? O próximo passo será dividido por 2: 4/2 = 2 Temos dois grupos: I - {1,4,6,8,6} II - {3,8,9,11} B array geral: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Passamos por ambos os grupos usando o algoritmo de classificação por inserção e obtemos uma matriz: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8} Agora nosso array está quase ordenado. A última iteração do algoritmo permanece: dividimos o passo por 2: 2/2 = 1. Obtemos um grupo, o array inteiro: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } Por que passamos pelo algoritmo de classificação por inserção e obtemos: { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } Vamos ver como podemos exibir essa classificação no 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]) {//sorting вставкой внутри группы
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // уменьшаем наш шаг
       }
   }
}

No momento, a eficácia da classificação Shell não está realmente comprovada, uma vez que os resultados diferem em diferentes situações. As estimativas obtidas em experimentos variam de O(N ^3/2 ) a O(N ^7/6 ) .

Ordenação rápida

Este é um dos algoritmos mais populares e, portanto, vale a pena prestar atenção especial. A essência deste algoritmo é que um elemento pivô é selecionado de uma lista de elementos – essencialmente qualquer elemento em relação ao qual os valores restantes precisam ser classificados. Valores menores do que à esquerda, valores maiores do que à direita. Em seguida, as partes direita e esquerda também são selecionadas pelo elemento de suporte e acontece a mesma coisa: os valores são classificados em relação a esses elementos, então os elementos de suporte são selecionados das partes resultantes - e assim por diante até obtermos uma classificação linha. Este algoritmo em Java é implementado usando recursão:

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 выхода из рекурсии,  если длина массива равна 0
           return;

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


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


       int i = min, j = max;
       while (i <= j) {  // относительно element 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) // запускаем рекурсию с elementми меньшими чем middle
           recursionFastSort(array, min, j);

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

Sem dúvida, o algoritmo quicksort é considerado o mais popular, pois na maioria das situações ele roda mais rápido que outras, em tempo O(N*logN) .

Mesclar classificação

Essa classificação também é popular. Refere-se a um dos tipos de algoritmos que funcionam segundo o princípio de “dividir e conquistar”: neles primeiro dividimos as tarefas em partes mínimas ( quick sort também é um representante de tais algoritmos ). Então, qual é a essência desse algoritmo?

Dividir:

A matriz é dividida em duas partes aproximadamente do mesmo tamanho, cada uma dessas duas partes é dividida em mais duas, e assim por diante, até que restem as menores partes indivisíveis. As partes menos indivisíveis ocorrem quando cada array possui um elemento, o que significa que tal array é automaticamente considerado classificado.

Conquistar:

É aqui que começa o processo que dá nome à fusão do algoritmo . Para fazer isso, pegue as duas matrizes ordenadas resultantes e mescle-as em uma. Neste caso, o menor dos primeiros elementos dos dois arrays é gravado no array resultante, e esta operação é repetida até que não haja mais elementos nos dois arrays. Ou seja, se tivermos dois arrays mínimos {6} e {4} , seus valores serão comparados e o resultado será escrito: {4,6} . Se houver matrizes classificadas {4,6} e {2,8} , primeiro os valores 4 e 2 serão comparados , dos quais 2 serão gravados na matriz resultante. Depois disso, 4 e 8 serão comparados , 4 serão anotados e no final serão comparados 6 e 8 . Assim, 6 será escrito, e somente depois dele - 8. Como resultado, obteremos o array resultante: {2,4,6,8} . Como isso ficará no código Java? Para processar este algoritmo, será conveniente usarmos recursão:

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;
   }
}

Como na classificação rápida, movemos o método recursivo para um intermediário para que o usuário não precise se preocupar em definir argumentos padrão adicionais, mas possa apenas especificar o array que precisa ser classificado. Como esse algoritmo é semelhante ao apagamento mais rápido, sua velocidade de execução é a mesma - O(N*logN) .

2. Algoritmos gananciosos

Um algoritmo ganancioso é uma abordagem que toma decisões localmente ótimas em cada estágio e assume que a solução final também será ótima. A solução “ótima” é aquela que oferece o benefício mais óbvio e imediato em uma determinada etapa/fase. Para considerar esse algoritmo, escolheremos um problema bastante comum - sobre uma mochila. Vamos fingir por um segundo que você é um ladrão. Você invadiu uma loja à noite com uma mochila e na sua frente há uma série de mercadorias que você pode roubar. Mas, ao mesmo tempo, a capacidade da mochila é limitada - não mais que 30 unidades convencionais. Ao mesmo tempo, você deseja carregar um conjunto de mercadorias com o valor máximo que caiba na sua mochila. Como você decide o que colocar? Portanto, o algoritmo ganancioso para o problema da mochila consiste nas seguintes etapas (assumimos que todos os objetos cabem na mochila):

1. Escolha o item mais caro daqueles que ainda não foram tocados.
2. Se couber na sua mochila, coloque lá; se não, pule.
3. Você classificou todos os itens? Caso contrário, voltamos ao ponto 1, se sim, corremos da loja, pois nosso objetivo aqui está cumprido.

Vejamos isso, mas em Java. Esta é a aparência da classe Item:

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;
   }
}

Não há nada de especial aqui: três campos - nome , peso , custo - para especificar as características do item. Além disso, como você pode ver, a interface Comparable é implementada aqui para que possamos classificar nossos itens por preço. A seguir olhamos para a classe da nossa mochila - Bag :

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 é a capacidade da nossa mochila, que é definida no momento da criação do objeto;
• itens — objetos na mochila;
• currentWeight , currentCost - o peso e custo atuais de todas as coisas na mochila, que aumentamos ao adicionar um novo item no método addItem .

Na verdade, vamos para a aula, onde toda a ação acontece:

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());
}
}

Primeiro, criamos uma lista de elementos e a classificamos. Crie um objeto bolsa com capacidade para 30 unidades. A seguir, enviamos os elementos e o objeto bag para o método fillBackpack , no qual, de fato, a mochila é preenchida usando um algoritmo ganancioso:

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

Tudo é extremamente simples: começamos a percorrer a lista de itens ordenados por custo e colocamos em uma sacola, se a capacidade permitir. Caso não permita, o elemento será pulado e a passagem pelos demais elementos continuará até o final da lista. Ao executar main, obtemos a seguinte saída no console: Na verdade, este é um exemplo de algoritmo ganancioso: a cada passo uma solução localmente ótima é selecionada e, no final, você obtém uma solução globalmente ótima. No nosso caso, a melhor opção é o item mais caro. Mas será esta a melhor solução? Você não acha que poderíamos modernizar um pouco a nossa solução para podermos equipar uma mochila com um custo total maior? Vamos dar uma olhada em como isso pode ser feito:

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());
       }
   }
}

Aqui calculamos primeiro a relação peso-preço para cada item. Por assim dizer, quanto custa uma unidade de um determinado item? E por esses valores classificamos nossos itens e os adicionamos à nossa sacola. Vamos correr:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

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

Obtemos a saída para o console: Um pouco melhor, não é? Um algoritmo ganancioso faz uma escolha localmente ótima em cada etapa com a expectativa de que a solução final também seja ótima. Isto nem sempre é justificado, mas para muitos problemas algoritmos gananciosos fornecem um ótimo. A complexidade de tempo desse algoritmo é O(N) , o que é muito bom, certo? Pois bem, com isso, a primeira parte deste artigo chegou ao fim. Se você tiver interesse na continuação deste artigo, que falará sobre gráficos e algoritmos relacionados a eles, você pode encontrá-lo aqui .