Les projets de développement utilisent divers algorithmes plus souvent que vous ne le pensez. Par exemple, supposons que nous ayons besoin de trier certaines données selon certains paramètres (colonnes) afin de pouvoir naviguer dans les données sans trop d'effort. Il ne serait donc pas du tout étrange qu'un recruteur vous pose des questions sur un algorithme de base spécifique et vous confie peut-être la tâche de l'implémenter à l'aide de code. Et puisque vous êtes sur ce site Web, je serai assez audacieux pour supposer que vous écrivez en Java. C'est pourquoi je vous propose aujourd'hui de vous familiariser avec quelques algorithmes de base et avec des exemples précis de leur implémentation en Java. Par "certains", j'entends :
Présentation des algorithmes de tri de tableaux :
tri à bulles,
tri par sélection,
tri par insertion,
Sorte de coque,
tri rapide,
tri par fusion,
Algorithmes gourmands
Algorithmes de recherche de chemin
recherche en profondeur d'abord
recherche en profondeur
Algorithme du plus court chemin d'abord 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 surtout connu pour sa simplicité, mais c'est aussi l'un des plus lents. À titre d'exemple, considérons un tri à bulles pour les nombres dans l'ordre croissant. Imaginons une suite aléatoire de nombres. Nous allons effectuer les étapes suivantes sur ces nombres, en commençant par le début de la séquence :
comparer deux nombres;
si le nombre à gauche est plus grand, échangez-les ;
déplacer d'une position vers la droite.
Après avoir effectué ces étapes sur toute la séquence, nous constaterons que le plus grand nombre se trouve à la fin de notre série de nombres. Ensuite, nous faisons un autre passage sur la séquence, en exécutant exactement les mêmes étapes que ci-dessus. Mais cette fois, nous n'inclurons pas le dernier élément de la liste, car c'est le plus grand nombre et déjà précisément où il devrait être lorsque les nombres sont triés. Encore une fois, nous finirons par déplacer le prochain plus grand nombre à la fin de notre séquence. Bien sûr, cela signifie que les deux plus grands nombres se tiennent à leur place. Encore une fois, nous faisons des passes sur la séquence, en excluant les éléments qui sont déjà à leur place, jusqu'à ce que tous les éléments soient dans l'ordre requis. Voyons comment le tri à bulles est implémenté 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. Tout semble tout simplement génial et ce serait si ce n'était pour une lacune - le tri à bulles est très, très lent. Sa complexité temporelle est O(N²), puisque nous avons des boucles imbriquées. La boucle externe sur les éléments est exécutée N fois. La boucle interne est également exécutée N fois. En conséquence, nous obtenons N*N, ou N², itérations.
Tri de 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équence de nombres que nous voulons organiser par ordre croissant. L'essence de cet algorithme est de parcourir séquentiellement tous les nombres et de sélectionner le plus petit élément, que nous prenons et échangeons avec l'élément le plus à gauche (le 0ème élément). Ici, nous avons une situation similaire au tri à bulles, mais dans ce cas, notre élément trié sera le plus petit. Par conséquent, la prochaine passe à travers les éléments commencera à partir de l'élément avec l'indice 1. Nous répéterons ces passes jusqu'à ce que tous les éléments aient été 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++) { // 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;
}
}
}
Cet algorithme est supérieur au tri à bulles, car ici le nombre de décalages requis est réduit de O(N²) à O(N). Nous ne conduisons pas un élément dans toute la liste, mais le nombre de comparaisons est toujours O(N²).
Tri par insertion
Nous considérons encore une autre séquence de nombres que nous voulons organiser par ordre croissant. Cet algorithme consiste à placer un marqueur, où tous les éléments à gauche du marqueur sont 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 partiellement triée. Ainsi, la partie triée grandira jusqu'à ce que tous les éléments aient été examinés. Vous vous demandez comment vous obtenez le sous-ensemble d'éléments qui sont déjà triés et comment nous déterminons où placer le marqueur ? Mais le tableau composé du premier élément est déjà trié, n'est-ce pas ? Jetons un coup d'œil à 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 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
}
}
}
Ce type de tri est supérieur à ceux décrits ci-dessus, car malgré le fait qu'il ait le même temps d'exécution en O(N²), cet algorithme est deux fois plus rapide que le tri à bulles et légèrement plus rapide que le tri par sélection.
Sorte de coquille
Ce tri est essentiellement un tri par insertion modifié. De quoi je parle ? Mettons les premières choses en premier. Il faut d'abord choisir un intervalle. Il existe de nombreuses approches pour faire ce choix. Nous n'entrerons pas trop dans les détails à ce sujet. Divisons notre tableau en deux et obtenons un certain nombre - ce sera notre intervalle. Donc, si nous avons 9 éléments dans notre tableau, alors notre intervalle sera 9/2 = 4,5. Nous supprimons la partie fractionnaire et obtenons 4, puisque les indices de tableau ne peuvent être que des entiers. Nous utiliserons cet intervalle pour former nos groupes. Si un élément a l'indice 0, alors l'indice de l'élément suivant dans son groupe est 0+4, c'est-à-dire 4. Le troisième élément aura l'indice 4+4, le quatrième — 8+4, et ainsi de suite. Dans le deuxième groupe, le premier élément sera 1,5,9... Dans les troisième et quatrième groupes, la situation sera la même. Par conséquent, à 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 nous les avons marqués comme membres du même groupe : {6,3,8,8,6,9,4,11,1} Ensuite, insertion tri est appliqué à ces groupes, puis ils ressemblent à ceci : I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} Dans le tableau général, les les cellules occupées par les groupes resteront les mêmes, mais leur ordre interne changera, selon l'ordre des groupes ci-dessus : {1,3,4,8,6,9,8,11,6} Le tableau est devenu un peu plus commandé, n'est-ce pas? Le prochain intervalle sera divisé par 2 : 4/2 = 2 Nous avons deux groupes : I — {1,4,6,8,6} II — {3,8,9,11} Dans le tableau général, nous avons : {1,3,4,8,6,9,8,11,6} Nous exécutons l'algorithme de tri par insertion sur les deux groupes et obtenons ce tableau : {1,3,4,8,6,9,6, 11, 8} Maintenant, notre tableau est presque trié. Nous devons effectuer une dernière itération de l'algorithme : nous divisons l'intervalle par 2 : 2/2 = 1. Nous obtenons un groupe composé de l'ensemble du tableau : {1,3,4,8,6,9,6,11 ,8} En exécutant l'algorithme de tri par insertion sur cela, nous obtenons : {1,3,4,6,6,8,8,9,11} Voyons comment nous pouvons donner vie à 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 = 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
}
}
}
À l'heure actuelle, les performances de Shellsort ne sont pas faciles à caractériser, car les résultats diffèrent selon les situations. Les estimations expérimentales vont de O(N 3/2 ) à O(N 7/6 ).
Tri rapide
C'est l'un des algorithmes les plus populaires, il convient donc d'y prêter une attention particulière. L'essentiel de cet algorithme est qu'un élément pivot est sélectionné dans une liste d'éléments. Nous trions tous les autres éléments par rapport à l'élément pivot. Les valeurs inférieures à l'élément pivot sont à gauche. Les valeurs supérieures à celle-ci se trouvent à droite. Ensuite, les éléments pivots sont également sélectionnés dans les parties droite et gauche, et la même chose se produit : les valeurs sont triées par rapport à ces éléments. Ensuite, les éléments pivots sont sélectionnés dans les parties nouvellement formées, et ainsi de suite jusqu'à ce que nous obtenions une séquence triée. L'implémentation Java suivante de cet algorithme utilise 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};
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);
}
}
Sans aucun doute, l'algorithme de tri rapide est le plus populaire, car dans la plupart des situations, il s'exécute plus rapidement que d'autres. Sa complexité temporelle est O(N*logN).
Tri par fusion
Ce type est également populaire. C'est l'un des nombreux algorithmes qui repose sur le principe de "diviser pour mieux régner". De tels algorithmes divisent d'abord le problème en parties gérables (quicksort est un autre exemple d'un tel algorithme). Alors, quel est l'essentiel de cet algorithme ?
Diviser:
Le tableau est divisé en deux parties d'environ la même taille. Chacune de ces deux parties est divisée en deux autres, et ainsi de suite jusqu'à ce qu'il en reste les plus petites parties indivisibles possibles. Nous avons les plus petites parties indivisibles lorsque chaque tableau a un élément, c'est-à-dire un tableau déjà trié.
Conquérir:
C'est ici que débute le processus qui a donné son nom à l'algorithme : la fusion. Pour ce faire, nous prenons les deux tableaux triés résultants et les fusionnons en un seul. Dans ce cas, le plus petit des premiers éléments des deux tableaux est écrit dans le tableau résultant. Cette opération est répétée jusqu'à ce que tous les éléments de ces deux tableaux aient été recopiés. Autrement dit, si nous avons deux tableaux minimaux {6} et {4}, nous comparons leurs valeurs et générons ce résultat fusionné : {4,6}. Si nous avons des tableaux triés {4,6} et {2,8}, nous comparons d'abord les valeurs 4 et 2, puis nous écrivons 2 dans le tableau résultant. Après cela, 4 et 8 seront comparés, et nous écrirons 4. Enfin, 6 et 8 seront comparés. En conséquence, nous écrirons 6, et seulement après cela nous écrirons 8. En conséquence, nous obtenons le tableau fusionné suivant : {2,4,6,8}. À quoi cela ressemblera-t-il dans le code Java ? Pour exécuter cet algorithme, il nous sera commode 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); // 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;
}
}
Comme dans le tri rapide, nous déplaçons la méthode récursive dans une méthode intermédiaire afin que l'utilisateur n'ait qu'à fournir le tableau à trier et n'ait pas à se soucier de fournir des arguments par défaut supplémentaires. Cet algorithme présente des similitudes avec le tri rapide, et sans surprise sa vitesse d'exécution est la même : O(N*logN).
2. Algorithmes gourmands
Un algorithme glouton est une approche où des décisions localement optimales sont prises à chaque étape, avec l'hypothèse que la solution finale sera également optimale. La solution "optimale" sera celle qui offre le bénéfice le plus évident et le plus immédiat à une étape/étape particulière. Pour explorer cet algorithme, prenons un problème assez courant - le problème du sac à dos. Imaginez un instant que vous êtes un voleur. Vous êtes entré par effraction dans un magasin la nuit avec un sac à dos (sac à dos). Devant vous se trouvent plusieurs biens que vous pourriez voler. Mais en même temps, votre sac à dos a une capacité limitée. Il ne peut pas transporter plus de 30 unités de poids. Vous voulez également emporter l'ensemble de marchandises le plus précieux qui ira dans le sac à dos. Comment déterminer quoi mettre dans son sac ? Donc,
Choisissez l'article le plus cher qui n'a pas encore été pris.
S'il tient dans le sac à dos, mettez-le dedans. Sinon, laissez-le.
Avons-nous déjà tout volé ? Sinon, nous revenons à l'étape 1. Si oui, alors nous nous éloignons rapidement du magasin, puisque nous avons accompli ce que nous sommes venus faire.
Regardons cela, mais en Java. Voici à quoi ressemblera la classe 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;
}
}
Rien de spécial ici : trois champs (nom, poids, valeur) qui définissent les caractéristiques de l'article. De plus, comme vous pouvez le voir, l'interface Comparable est implémentée pour nous permettre de trier nos articles par prix. Ensuite, nous allons regarder la classe Bag, qui représente notre sac à dos :
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 est la capacité de notre sac à dos, qui est définie lorsque nous créons un objet ;
items représente les objets dans notre sac à dos ;
currentWeight , currentValue — ces champs stockent le poids et la valeur actuels de tous les éléments du sac à dos, que nous augmentons lorsque nous ajoutons un nouvel élément dans la méthode addItem.
Quoi qu'il en soit, passons maintenant à 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("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());
}
}
Tout d'abord, nous créons une liste d'éléments et la trions. Nous créons un objet sac d'une contenance de 30 unités. Ensuite, nous passons les articles et l'objet sac à la méthode fillBackpack, qui remplit le sac à dos selon notre algorithme gourmand :
C'est assez simple : on commence par parcourir une liste d'articles triés par coût et on les met dans le sac si sa capacité le permet. S'il n'y a pas assez de place, l'élément sera ignoré et nous continuerons à parcourir le reste des éléments jusqu'à ce que nous atteignions la fin de la liste. Une fois que nous aurons exécuté main, voici la sortie de la console que nous obtiendrons :
Le poids du sac à dos est de 29. La valeur totale des articles dans le sac à dos est de 3700
Ceci est un exemple d'algorithme glouton : à chaque étape, une solution localement optimale est sélectionnée, et au final, on obtient 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 qu'il est possible d'améliorer légèrement notre solution afin de remplir notre sac à dos d'articles qui ont une valeur totale encore plus grande ? Voyons comment cela peut être fait.
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());
}
}
}
Ici, nous calculons d'abord le rapport valeur/poids pour chaque article. Cela nous indique la valeur de chaque unité d'un élément donné. Et puis nous utilisons ces ratios pour trier nos articles et les ajouter à notre panier. Exécutons ce qui suit :
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());
Nous obtenons cette sortie de console :
Le poids du sac à dos est de 29. Le coût total des articles dans le sac à dos est de 4150
Un peu mieux, n'est-ce pas ? L'algorithme glouton fait un choix localement optimal à chaque étape, en espérant que la solution finale sera également optimale. Cette hypothèse n'est pas toujours valide, mais pour de nombreuses tâches, les algorithmes gourmands donnent une solution finale optimale. La complexité temporelle de cet algorithme est O(N). Plutôt bien, hein ?
Et puisque vous êtes sur ce site Web, je serai assez audacieux pour supposer que vous écrivez en Java. C'est pourquoi je vous propose aujourd'hui de vous familiariser avec quelques algorithmes de base et avec des exemples précis de leur implémentation en Java. Par "certains", j'entends :
GO TO FULL VERSION