Ontwikkelingsprojecten maken vaker gebruik van verschillende algoritmen dan je zou denken. Stel dat we sommige gegevens moeten sorteren op bepaalde parameters (kolommen), zodat we zonder veel moeite door de gegevens kunnen navigeren. Het zou dus helemaal niet vreemd zijn als een sollicitant je vraagt naar een specifiek basisalgoritme en misschien de opdracht geeft om het met behulp van code te implementeren. En aangezien u zich op deze website bevindt, durf ik te veronderstellen dat u in Java schrijft. Daarom stel ik vandaag voor dat u vertrouwd raakt met enkele basisalgoritmen en met specifieke voorbeelden van hoe u ze in Java kunt implementeren. Met "sommigen" bedoel ik:
Overzicht van array-sorteeralgoritmen:
bellen sorteren,
selectie sorteren,
invoeging sorteren,
Shell soort,
Snel sorteren,
samenvoegen sorteren,
Hebzuchtige algoritmen
Pathfinding-algoritmen
diepte-eerst zoeken
breedte-eerst zoeken
Dijkstra's Shortest Path First-algoritme
Nou, zonder verder oponthoud, laten we aan de slag gaan.
1. Overzicht van sorteeralgoritmen
Bellen soort
Dit sorteeralgoritme staat vooral bekend om zijn eenvoud, maar het is ook een van de langzaamste. Laten we als voorbeeld eens kijken naar een bellensortering voor getallen in oplopende volgorde. Laten we ons een willekeurige reeks getallen voorstellen. We zullen de volgende stappen uitvoeren op deze nummers, beginnend vanaf het begin van de reeks:
vergelijk twee getallen;
als het nummer aan de linkerkant groter is, verwissel ze dan;
schuif een positie naar rechts.
Nadat we deze stappen op de hele reeks hebben uitgevoerd, zullen we zien dat het grootste getal aan het einde van onze reeks getallen staat. Vervolgens passeren we de reeks opnieuw en voeren we precies dezelfde stappen uit als hierboven. Maar deze keer nemen we het laatste element van de lijst niet op, omdat het het grootste getal is en al precies waar het zou moeten zijn wanneer de getallen worden gesorteerd. Nogmaals, we zullen uiteindelijk het volgende grootste getal naar het einde van onze reeks verplaatsen. Dat betekent natuurlijk dat de twee grootste getallen op hun juiste plaats staan. Nogmaals, we maken passages over de reeks, exclusief de elementen die al op hun plaats staan, totdat alle elementen in de vereiste volgorde staan. Laten we eens kijken hoe bubbelsortering is geïmplementeerd in Java-code:
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;
}
}
}
}
}
Zoals u kunt zien, is hier niets ingewikkelds. Alles lijkt gewoon geweldig en dat zou zo zijn als er niet één tekortkoming was: het sorteren van bellen is heel, heel traag. De tijdscomplexiteit is O(N²), omdat we geneste lussen hebben. De buitenste lus over de elementen wordt N keer uitgevoerd. De binnenste lus wordt ook N keer uitgevoerd. Als resultaat krijgen we N*N, of N², iteraties.
Selectie sorteren
Dit algoritme is vergelijkbaar met het sorteren van bellen, maar het werkt iets sneller. Laten we nogmaals als voorbeeld een reeks getallen nemen die we in oplopende volgorde willen rangschikken. De essentie van dit algoritme is om achtereenvolgens alle getallen te doorlopen en het kleinste element te selecteren, dat we nemen en verwisselen met het meest linkse element (het 0e element). Hier hebben we een situatie die vergelijkbaar is met bellensortering, maar in dit geval is ons gesorteerde element het kleinste. Daarom zal de volgende doorgang door de elementen beginnen vanaf het element met index 1. We herhalen deze doorgangen totdat alle elementen zijn gesorteerd. Implementatie in 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;
}
}
}
Dit algoritme is superieur aan bellensortering, omdat hier het aantal benodigde verschuivingen wordt teruggebracht van O(N²) naar O(N). We sturen niet één element door de hele lijst, maar het aantal vergelijkingen is nog steeds O(N²).
Invoeg sortering
We beschouwen nog een andere nummerreeks die we in oplopende volgorde willen rangschikken. Dit algoritme bestaat uit het plaatsen van een markering, waarbij alle elementen links van de markering al gedeeltelijk onderling zijn gesorteerd. Bij elke stap van het algoritme wordt een van de elementen geselecteerd en op de gewenste positie in de gedeeltelijk gesorteerde reeks geplaatst. Zo groeit het gesorteerde deel totdat alle elementen zijn onderzocht. Vraag je je af hoe je de subset van elementen krijgt die al gesorteerd zijn en hoe we bepalen waar we de markering moeten plaatsen? Maar de array die bestaat uit het eerste element is al gesorteerd, nietwaar? Laten we eens kijken naar de implementatie in 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
}
}
}
Dit type sortering is superieur aan de hierboven beschreven, omdat ondanks het feit dat het dezelfde O(N²) looptijd heeft, dit algoritme twee keer zo snel is als bellensortering en iets sneller dan selectiesortering.
Shell soort
Deze sortering is in wezen een gemodificeerde invoegsortering. Waar heb ik het over? Laten we de eerste dingen eerst stellen. We moeten eerst een interval kiezen. Er zijn veel manieren om deze keuze te maken. We zullen hier niet te veel in detail op ingaan. Laten we onze array in tweeën delen en een getal krijgen - dit wordt ons interval. Dus als we 9 elementen in onze array hebben, dan is ons interval 9/2 = 4,5. We negeren het fractionele deel en krijgen 4, aangezien array-indices alleen gehele getallen kunnen zijn. We zullen deze pauze gebruiken om onze groepen te vormen. Als een element index 0 heeft, dan is de index van het volgende element in zijn groep 0+4, dat wil zeggen 4. Het derde element heeft de index 4+4, het vierde — 8+4, enzovoort. In de tweede groep is het eerste element 1,5,9... In de derde en vierde groep is de situatie hetzelfde. Als gevolg, uit de getallenreeks {6,3,8,8,6,9,4,11,1} krijgen we vier groepen: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} Ze behouden hun plaats in de algemene reeks, maar we hebben gemarkeerd als leden van dezelfde groep: {6,3,8,8,6,9,4,11,1} Volgende, invoeging sorteren wordt toegepast op deze groepen, en dan zien ze er zo uit: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} In de algemene reeks, de cellen bezet door de groepen blijven hetzelfde, maar hun interne volgorde zal veranderen, volgens de volgorde van de bovenstaande groepen: {1,3,4,8,6,9,8,11,6} De array is een beetje meer geordend, nietwaar? Het volgende interval wordt gedeeld door 2: 4/2 = 2 We hebben twee groepen: I — {1,4,6,8,6} II — {3,8,9,11} In de algemene reeks hebben we : {1,3,4,8,6,9,8,11,6} We voeren het invoegsorteeralgoritme uit op beide groepen en krijgen deze array: {1,3,4,8,6,9,6, 11, 8} Nu is onze array bijna gesorteerd. We moeten een laatste iteratie van het algoritme uitvoeren: we delen het interval door 2: 2/2 = 1. We krijgen een groep bestaande uit de hele array: {1,3,4,8,6,9,6,11 ,8} Als we het invoegsorteeralgoritme hierop uitvoeren, krijgen we: {1,3,4,6,6,8,8,9,11} Laten we eens kijken hoe we deze sortering tot leven kunnen brengen in Java-code:
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
}
}
}
Op dit moment is de prestatie van Shellsort niet gemakkelijk te karakteriseren, aangezien de resultaten in verschillende situaties verschillen. Experimentele schattingen variëren van O(N 3/2 ) tot O(N 7/6 ).
Snel sorteren
Dit is een van de meest populaire algoritmen, dus het is de moeite waard om er speciale aandacht aan te besteden. De kern van dit algoritme is dat een spilelement wordt geselecteerd in een lijst met elementen. We sorteren alle andere elementen ten opzichte van het spilelement. Waarden kleiner dan het spilelement staan aan de linkerkant. Waarden die groter zijn dan deze staan aan de rechterkant. Vervolgens worden ook draaielementen geselecteerd in het rechter en linker deel, en hetzelfde gebeurt: de waarden worden gesorteerd ten opzichte van deze elementen. Vervolgens worden draaielementen geselecteerd in de nieuw gevormde delen, enzovoort totdat we een gesorteerde volgorde krijgen. De volgende Java-implementatie van dit algoritme maakt gebruik van recursie:
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);
}
}
Het quicksort-algoritme is ongetwijfeld het populairst, omdat het in de meeste situaties sneller werkt dan in andere. De tijdscomplexiteit is O(N*logN).
Sorteer samenvoegen
Ook deze soort is populair. Het is een van de vele algoritmen die berusten op het principe van "verdeel en heers". Dergelijke algoritmen verdelen het probleem eerst in hanteerbare delen (quicksort is een ander voorbeeld van zo'n algoritme). Dus wat is de essentie van dit algoritme?
Verdeling:
De array wordt opgesplitst in twee delen van ongeveer dezelfde grootte. Elk van deze twee delen is verdeeld in nog twee, en zo verder totdat de kleinst mogelijke ondeelbare delen overblijven. We hebben de kleinste ondeelbare delen als elke array één element heeft, dwz een array die al is gesorteerd.
Veroveren:
Hier beginnen we het proces dat het algoritme zijn naam gaf: samenvoegen. Om dit te doen, nemen we de twee resulterende gesorteerde arrays en voegen ze samen tot één. In dit geval wordt het kleinste van de eerste elementen van de twee arrays in de resulterende array geschreven. Deze bewerking wordt herhaald totdat alle elementen in deze twee arrays zijn gekopieerd. Dat wil zeggen, als we twee minimale arrays {6} en {4} hebben, vergelijken we hun waarden en genereren we dit samengevoegde resultaat: {4,6}. Als we arrays {4,6} en {2,8} hebben gesorteerd, vergelijken we eerst de waarden 4 en 2, en dan schrijven we 2 in de resulterende array. Daarna worden 4 en 8 vergeleken en schrijven we 4. Ten slotte worden 6 en 8 vergeleken. Dienovereenkomstig schrijven we 6 en pas daarna schrijven we 8. Als resultaat krijgen we de volgende samengevoegde array: {2,4,6,8}. Hoe ziet dit eruit in Java-code? Om dit algoritme uit te voeren, is het handig voor ons om recursie te gebruiken:
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;
}
}
Net als bij snel sorteren verplaatsen we de recursieve methode naar een tussenliggende methode, zodat de gebruiker alleen de te sorteren array hoeft op te geven en zich geen zorgen hoeft te maken over het opgeven van aanvullende standaardargumenten. Dit algoritme heeft overeenkomsten met quicksort, en het is niet verwonderlijk dat de uitvoeringssnelheid hetzelfde is: O(N*logN).
2. Hebzuchtige algoritmen
Een hebzuchtig algoritme is een aanpak waarbij in elke fase lokaal optimale beslissingen worden genomen, in de veronderstelling dat de uiteindelijke oplossing ook optimaal zal zijn. De "optimale" oplossing is degene die het meest voor de hand liggende en onmiddellijke voordeel biedt in een bepaalde stap/fase. Om dit algoritme te verkennen, nemen we een vrij algemeen probleem: het knapzakprobleem. Doe even alsof je een dief bent. Je hebt 's nachts ingebroken in een winkel met een knapzak (rugzak). Voor je liggen verschillende goederen die je zou kunnen stelen. Maar tegelijkertijd heeft je rugzak een beperkte capaciteit. Het kan niet meer dan 30 gewichtseenheden dragen. Je wilt ook de meest waardevolle goederen meenemen die in de rugzak passen. Hoe bepaal je wat je in je tas stopt? Dus,
Kies het duurste item dat nog niet is ingenomen.
Als het in de rugzak past, doe het er dan in. Zo niet, laat het dan liggen.
Hebben we al alles gestolen? Zo niet, dan gaan we terug naar stap 1. Zo ja, dan maken we onze snelle ontsnapping uit de winkel, aangezien we hebben bereikt waarvoor we kwamen.
Laten we hier eens naar kijken, maar dan in Java. Zo ziet de klasse Item eruit:
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;
}
}
Er is hier niets bijzonders: drie velden (naam, gewicht, waarde) die de kenmerken van het item definiëren. Zoals u kunt zien, is de vergelijkbare interface ook geïmplementeerd om ons in staat te stellen onze artikelen op prijs te sorteren. Vervolgens kijken we naar de Bag-klasse, die onze knapzak vertegenwoordigt:
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 is de capaciteit van onze rugzak, die wordt ingesteld wanneer we een object maken;
items vertegenwoordigt de objecten in onze rugzak;
currentWeight , currentValue — deze velden slaan het huidige gewicht en de huidige waarde op van alle items in de rugzak, die we verhogen wanneer we een nieuw item toevoegen in de addItem-methode.
Hoe dan ook, laten we nu naar de klas gaan waar alle actie plaatsvindt:
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());
}
}
Eerst maken we een lijst met items en sorteren deze. We maken een zakobject met een capaciteit van 30 eenheden. Vervolgens geven we de items en het tasobject door aan de methode fillBackpack, die de rugzak vult volgens ons hebzuchtige algoritme:
Het is vrij eenvoudig: we beginnen met het doornemen van een lijst met items gesorteerd op kosten en stoppen ze in de tas als de capaciteit dit toelaat. Als er niet genoeg ruimte is, wordt het item overgeslagen en gaan we door met het doorlopen van de rest van de items totdat we het einde van de lijst bereiken. Zodra we main hebben uitgevoerd, krijgen we hier de console-uitvoer:
Het gewicht van de knapzak is 29. De totale waarde van de items in de knapzak is 3700
Dit is een voorbeeld van een hebzuchtig algoritme: bij elke stap wordt een lokaal optimale oplossing geselecteerd en uiteindelijk krijg je een globaal optimale oplossing. In ons geval is de beste optie het duurste item. Maar is dit de beste oplossing? Denk je niet dat het mogelijk is om onze oplossing iets te verbeteren om onze rugzak te vullen met items die een nog grotere totale waarde hebben? Laten we eens kijken hoe dit kan.
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());
}
}
}
Hier berekenen we eerst de waarde-gewichtsverhouding voor elk item. Dit vertelt ons de waarde van elke eenheid van een bepaald item. En dan gebruiken we deze verhoudingen om onze artikelen te sorteren en aan onze tas toe te voegen. Laten we het volgende uitvoeren:
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());
We krijgen deze console-uitvoer:
Het gewicht van de knapzak is 29. De totale kosten van items in de knapzak zijn 4150
Een beetje beter, nietwaar? Het hebzuchtige algoritme maakt bij elke stap een lokaal optimale keuze, in de hoop dat de uiteindelijke oplossing ook optimaal zal zijn. Deze aanname gaat niet altijd op, maar voor veel taken leveren hebzuchtige algoritmen wel een optimale eindoplossing op. De tijdscomplexiteit van dit algoritme is O(N). Best goed, hè?
En aangezien u zich op deze website bevindt, durf ik te veronderstellen dat u in Java schrijft. Daarom stel ik vandaag voor dat u vertrouwd raakt met enkele basisalgoritmen en met specifieke voorbeelden van hoe u ze in Java kunt implementeren. Met "sommigen" bedoel ik:
GO TO FULL VERSION