Ce qu'ils demandent lors d'un entretien : revue des algorithmes, partie 1

Bonjour à tous ! Différents types d’algorithmes sont utilisés dans les projets plus souvent que vous ne le pensez. Par exemple, nous devons trier certaines données en fonction de certains paramètres (colonnes) afin de pouvoir les parcourir sans trop d'effort. Il n'y a donc rien d'étrange à ce que lors des entretiens d'embauche, ils puissent être interrogés sur l'un ou l'autre algorithme de base, et peut-être se voir confier la tâche de l'implémenter à l'aide de code. Et puisque vous êtes sur ce site, j'oserais deviner que vous écrivez en Java. C'est pourquoi je vous invite aujourd'hui à vous familiariser avec quelques algorithmes de base et des exemples spécifiques de leur implémentation en Java. Par certains, je veux dire :

1. Présentation des algorithmes de tri de tableaux :
   • tri à bulles,
   • tri par sélection,
   • tri par insertion,
   • Tri de coquilles,
   • tri rapide,
   • tri par fusion.
2. Algorithme gourmand.
3. Algorithmes de recherche de chemin :
   • ramper en profondeur
   • large rampe.
4. L'algorithme de transport est l'algorithme de Dijkstra.

Eh bien, sans plus tarder, passons aux choses sérieuses.

1. Présentation des algorithmes de tri

Tri à bulles

Cet algorithme de tri est connu avant tout pour sa simplicité, mais en même temps il présente l'une des vitesses d'exécution les plus faibles. À titre d'exemple, considérons le tri à bulles pour les nombres par ordre croissant. Imaginons une chaîne de nombres placés aléatoirement pour laquelle les étapes suivantes seront effectuées, en commençant par le début de la chaîne :

• comparer deux nombres ;
• si le nombre à gauche est plus grand, échangez-les ;
• déplacer d’une position vers la droite.

Après avoir parcouru toute la chaîne et effectué ces étapes, nous constaterons que le plus grand nombre se trouve à la fin de notre série de nombres. Ensuite, exactement le même passage le long de la chaîne est effectué, en suivant les étapes décrites ci-dessus. Mais cette fois, nous n'inclurons pas le dernier élément de la liste, car il est le plus grand et se trouve déjà à la dernière place, comme il se doit. Encore une fois, nous obtiendrons le dernier élément à la fin de notre série de nombres en question. Ainsi, les deux plus grands nombres seront déjà à leur place. Et encore une fois, le passage le long de la chaîne recommence, en excluant les éléments déjà en place, jusqu'à ce que tous les éléments soient dans l'ordre requis. Regardons l'implémentation du tri à bulles dans le code 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;
             }
         }
       }
   }
}

Comme vous pouvez le voir, il n'y a rien de compliqué ici, et tout semble bien aller, si ce n'est un « mais »... Le tri des bulles est très, très lent, avec une complexité temporelle de O(N²) , puisque nous avons imbriqué boucles. Le passage externe à travers les éléments est effectué N fois, le passage interne est également N fois, et par conséquent nous obtenons N*N , N² itérations. Vous pouvez étudier ce type de tri plus en détail dans cet article .

Tri par sélection

Cet algorithme est similaire au tri à bulles, mais il fonctionne un peu plus rapidement. Encore une fois, à titre d'exemple, prenons une série de nombres que nous souhaitons classer par ordre croissant. L'essence de l'algorithme est de parcourir séquentiellement tous les nombres et de sélectionner le plus petit élément, que nous prenons et échangeons sa place avec l'élément le plus à gauche (élément 0). Ici, nous obtenons une situation similaire au tri à bulles, mais dans ce cas, l'élément trié sera le plus petit. Par conséquent, le prochain passage à travers les éléments commencera par l’élément à l’index 1. Encore une fois, ces passages seront répétés jusqu’à ce que tous les éléments soient triés. Implémentation 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;
       }
   }
}

Cet algorithme est supérieur au tri à bulles, car ici le nombre de permutations nécessaires est réduit de O(N²) à O(N) : on ne pousse pas un élément dans toute la liste, mais néanmoins, le nombre de comparaisons reste O(N² ) . Pour ceux qui souhaitent en savoir plus sur cet algorithme, je recommande ce matériel .

Tri par insertion

Encore une fois, à titre d'exemple, prenons une série de nombres que nous souhaitons classer par ordre croissant. Cet algorithme consiste à placer un marqueur, à gauche duquel les éléments seront déjà partiellement triés entre eux. A chaque étape de l'algorithme, un des éléments sera sélectionné et placé à la position souhaitée dans la séquence déjà triée. Ainsi, la partie triée continuera à croître jusqu'à ce que tous les éléments aient été examinés. Vous vous demandez peut-être : où puis-je obtenir la partie des éléments qui sont déjà triés et après laquelle vous devez mettre un marqueur ? Mais le tableau du premier élément est déjà trié, n’est-ce pas ? Regardons l'implémentation 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]; // делаем копию помеченного element
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // пока не будет найден меньший элемент
               array[j] = array[j - 1]; // сдвигаем элементы вправо
               --j;
           }
           array[j] = temp;   // вставляем отмеченный элемент, в положеное ему место
       }
   }
}

Ce type de tri est supérieur à ceux décrits ci-dessus, car malgré le fait que le temps d'exécution soit le même - O(N²) , cet algorithme fonctionne deux fois plus vite que le tri à bulles et légèrement plus rapide que le tri par sélection. Lire la suite ici .

Tri des coquilles

Ce tri, de par sa nature, est un tri par insertion modifié. De quoi je parle ? Allons-y dans l'ordre. Une étape est sélectionnée, et il existe de nombreuses approches pour ce choix. Nous n’entrerons pas dans les détails de cette question. Divisons notre tableau en deux et obtenons un certain nombre - ce sera notre étape. Donc, si nous avons 9 éléments dans le tableau, alors notre pas sera 9/2 = 4.5 . Nous supprimons la partie fractionnaire et obtenons 4 , puisque les indices de tableau ne sont que des entiers. Avec cette étape, nous créerons des liens pour nos groupes. Si un élément a l'index 0, alors l'index de l'élément suivant de son groupe est 0+4 , c'est-à-dire 4 . Le troisième élément aura un indice de 4+4 , le quatrième aura un indice de 8+4 , et ainsi de suite. Pour le deuxième groupe, le premier élément sera 1,5,9…. Dans les troisième et quatrième groupes, les choses seront exactement les mêmes. En conséquence, à partir du tableau de nombres {6,3,8,8,6,9,4,11,1} nous obtenons quatre groupes : I - {6,6,1} II - {3,9} III - {8, 4} IV - {8,11} Ils conservent leur place dans le tableau général, mais pour nous ils sont marqués comme membres d'un même groupe : { 6 , 3 , 8 , 8 , 6 , 9 , 4 , 11 , 1 } Ensuite, au sein de ces groupes, le tri par insertion , après quoi les groupes ressembleront à : I - {1,6,6} II - {3,9} III - {4,8} IV - {8 ,11} Dans le tableau général, les cellules occupées par les groupes resteront les mêmes, mais l'ordre à l'intérieur d'elles changera, selon l'ordre des groupes ci-dessus : { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Le tableau est un peu plus ordonné, n'est-ce pas ? L'étape suivante sera divisée par 2 : 4/2 = 2 Nous avons deux groupes : I - {1,4,6,8,6} II - {3,8,9,11} B tableau général : { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Nous parcourons les deux groupes en utilisant l'algorithme de tri par insertion et obtenons un tableau : { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8} Maintenant, notre tableau est presque trié. Reste la dernière itération de l'algorithme : on divise le pas par 2 : 2/2 = 1. On obtient un groupe, le tableau entier : { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } Par que nous passons par l'algorithme de tri par insertion et obtenons : { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } Voyons comment nous pouvons afficher ce tri dans le code 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; // уменьшаем наш шаг
       }
   }
}

Pour le moment, l’efficacité du tri Shell n’est pas vraiment prouvée, car les résultats diffèrent selon les situations. Les estimations obtenues à partir des expériences vont de O(N ^3/2 ) à O(N ^7/6 ) .

Tri rapide

C’est l’un des algorithmes les plus populaires et il mérite donc une attention particulière. L'essence de cet algorithme est qu'un élément pivot est sélectionné dans une liste d'éléments, essentiellement tout élément par rapport auquel les valeurs restantes doivent être triées. Valeurs inférieures à celle de gauche, valeurs supérieures à celles de droite. Ensuite, les parties droite et gauche sont également sélectionnées par l'élément de support et la même chose se produit : les valeurs sont triées par rapport à ces éléments, puis les éléments de support sont sélectionnés parmi les parties résultantes - et ainsi de suite jusqu'à ce que nous obtenions un tri rangée. Cet algorithme en Java est implémenté par récursion :

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

Sans aucun doute, l'algorithme de tri rapide est considéré comme le plus populaire, car dans la plupart des situations, il s'exécute plus rapidement que les autres, en temps O(N*logN) .

Tri par fusion

Ce tri est également populaire. Il fait référence à l'un des types d'algorithmes qui fonctionnent sur le principe « diviser pour mieux régner » : dans ceux-ci, nous divisons d'abord les tâches en parties minimales ( le tri rapide est également un représentant de ces algorithmes ). Alors, quelle est l’essence de cet algorithme ?

Partager:

Le réseau est divisé en deux parties approximativement de même taille, chacune de ces deux parties est divisée en deux autres, et ainsi de suite jusqu'à ce qu'il reste les plus petites parties indivisibles. Les parties les moins indivisibles se produisent lorsque chaque tableau comporte un élément, ce qui signifie qu'un tel tableau est automatiquement considéré comme trié.

Conquérir:

C'est là que commence le processus qui donne son nom à l'algorithme de fusion . Pour ce faire, prenez les deux tableaux ordonnés résultants et fusionnez-les en un seul. Dans ce cas, le plus petit des premiers éléments des deux tableaux est écrit dans le tableau résultant, et cette opération est répétée jusqu'à ce qu'il n'y ait plus d'éléments dans les deux tableaux. Autrement dit, si nous avons deux tableaux minimaux {6} et {4} , leurs valeurs seront comparées et le résultat s'écrira : {4,6} . S'il existe des tableaux triés {4,6} et {2,8} , alors les valeurs 4 et 2 seront d'abord comparées , dont 2 seront écrites dans le tableau résultant. Après cela, 4 et 8 seront comparés , 4 sera noté et à la fin 6 et 8 seront comparés . En conséquence, 6 sera écrit, et seulement après - 8. En conséquence, nous obtiendrons le tableau résultant : {2,4,6,8} . À quoi cela ressemblera-t-il dans le code Java ? Pour traiter cet algorithme, il nous conviendra d'utiliser la récursivité :

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

Comme pour le tri rapide, nous déplaçons la méthode récursive vers une méthode intermédiaire afin que l'utilisateur n'ait pas à se soucier de définir des arguments par défaut supplémentaires, mais puisse simplement spécifier le tableau qui doit être trié. Puisque cet algorithme est similaire à un effacement plus rapide, sa vitesse d'exécution est la même - O(N*logN) .

2. Algorithmes gourmands

Un algorithme glouton est une approche qui prend des décisions localement optimales à chaque étape et suppose que la solution finale sera également optimale. La solution « optimale » est celle qui offre le bénéfice le plus évident et le plus immédiat à une certaine étape/étape. Pour considérer cet algorithme, nous choisirons un problème assez courant : celui d'un sac à dos. Imaginons un instant que vous soyez un voleur. Vous êtes entré par effraction dans un magasin la nuit avec un sac à dos et devant vous se trouve un certain nombre de marchandises que vous pouvez voler. Mais en même temps, la capacité du sac à dos est limitée - pas plus de 30 unités conventionnelles. Dans le même temps, vous souhaitez emporter un ensemble de biens d'une valeur maximale qui rentreront dans votre sac à dos. Comment décidez-vous quoi mettre? Ainsi, l'algorithme glouton pour le problème du sac à dos comprend les étapes suivantes (nous supposons que tous les objets rentrent dans le sac à dos) :

1. Choisissez l'article le plus cher parmi ceux qui n'ont pas encore été touchés.
2. S'il rentre dans votre sac à dos, mettez-le là ; sinon, sautez-le.
3. Avez-vous trié tous les éléments ? Sinon, on revient au point 1, si oui, on fuit le magasin, puisque notre objectif ici est atteint.

Regardons cela, mais en Java. Voici à quoi ressemblera la 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;
   }
}

Il n'y a rien de spécial ici : trois champs - nom , poids , coût - pour préciser les caractéristiques de l'article. De plus, comme vous pouvez le constater, l' interface Comparable est implémentée ici afin que nous puissions trier nos articles par prix. Ensuite, nous regardons la classe de notre sac à dos - 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 est la capacité de notre sac à dos, qui est définie lors de la création de l'objet ;
• objets — objets dans le sac à dos ;
• currentWeight , currentCost - le poids et le coût actuels de tout ce qui se trouve dans le sac à dos, que nous augmentons lors de l'ajout d'un nouvel élément dans la méthode addItem .

En fait, allons à la classe, où se déroule toute l'action :

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

Tout d’abord, nous créons une liste d’éléments et la trions. Créez un objet sac d'une capacité de 30 unités. Ensuite, nous envoyons les éléments et l'objet bag à la méthode fillBackpack , dans laquelle, en fait, le sac à dos est rempli à l'aide d'un algorithme glouton :

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

Tout est extrêmement simple : on commence à parcourir la liste des articles triés par coût et à les mettre dans un sac, si la capacité le permet. Si cela ne le permet pas, l'élément sera ignoré et le passage à travers les éléments restants se poursuivra jusqu'à la fin de la liste. En exécutant main, nous obtenons le résultat suivant sur la console : En fait, il s'agit d'un exemple d'algorithme glouton : à chaque étape, une solution localement optimale est sélectionnée, et à la fin vous obtenez une solution globalement optimale. Dans notre cas, la meilleure option est l’article le plus cher. Mais est-ce la meilleure solution ? Ne pensez-vous pas que nous pourrions moderniser un peu notre solution pour pouvoir équiper un sac à dos avec un coût total plus élevé ? Voyons comment cela peut être fait :

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

Ici, nous calculons d’abord le rapport poids-prix pour chaque article. Pour ainsi dire, combien coûte une unité d’un article donné ? Et selon ces valeurs, nous trions nos articles et les ajoutons à notre sac. Courons :

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

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

Nous obtenons le résultat sur la console : Un peu mieux, non ? Un algorithme glouton fait un choix localement optimal à chaque étape en espérant que la solution finale sera également optimale. Cela n’est pas toujours justifié, mais pour de nombreux problèmes, les algorithmes gloutons fournissent un optimum. La complexité temporelle de cet algorithme est O(N) , ce qui est plutôt bien, non ? Voilà, la première partie de cet article touche à sa fin. Si vous êtes intéressé par la suite de cet article, qui parlera des graphiques et des algorithmes qui s'y rapportent, vous pouvez la trouver ici .