Utvecklingsprojekt använder olika algoritmer oftare än man kan tro. Anta till exempel att vi behöver sortera vissa data efter vissa parametrar (kolumner) så att vi kan navigera genom data utan större ansträngning. Så det skulle inte alls vara konstigt för en arbetsintervjuare att fråga dig om en specifik grundläggande algoritm och kanske ge uppdraget att implementera den med hjälp av kod. Och eftersom du är på den här webbplatsen, ska jag vara så djärv att anta att du skriver i Java. Det är därför jag idag föreslår att du bekantar dig med några grundläggande algoritmer och med specifika exempel på hur man implementerar dem i Java. Med "några" menar jag:
Översikt över arraysorteringsalgoritmer:
bubbla sortering,
urval sortering,
insättningssort,
Skalsortering,
snabbsort,
slå samman sortering,
giriga algoritmer
Pathfinding-algoritmer
djup-första sökning
utöka första sökningen
Dijkstras Shortest Path First-algoritm
Nåväl, utan vidare, låt oss börja.
1. Översikt över sorteringsalgoritmer
Bubblesort
Denna sorteringsalgoritm är främst känd för sin enkelhet, men den är också en av de långsammaste. Som ett exempel, låt oss betrakta en bubbelsortering för siffror i stigande ordning. Låt oss föreställa oss en slumpmässig sekvens av tal. Vi kommer att utföra följande steg på dessa siffror, med början från början av sekvensen:
jämför två siffror;
om siffran till vänster är större, byt ut dem;
flytta en position åt höger.
Efter att ha utfört dessa steg på hela sekvensen kommer vi att upptäcka att det största numret finns i slutet av vår nummerserie. Sedan gör vi en ny passning över sekvensen och utför exakt samma steg som ovan. Men den här gången tar vi inte med det sista elementet i listan, eftersom det är det största antalet och redan exakt där det ska vara när siffrorna sorteras. Återigen kommer vi att flytta det näst största numret till slutet av vår sekvens. Naturligtvis betyder det att de två största numren står på sina rätta platser. Återigen går vi över sekvensen, exklusive de element som redan finns på sina platser, tills alla element är i önskad ordning. Låt oss ta en titt på hur bubbelsortering implementeras i Java-kod:
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;
}
}
}
}
}
Som du kan se är det inget komplicerat här. Allt verkar bara bra och det skulle vara om det inte vore för en brist - bubbelsortering är väldigt, väldigt långsam. Dess tidskomplexitet är O(N²), eftersom vi har kapslade loopar. Den yttre slingan över elementen utförs N gånger. Den inre slingan exekveras också N gånger. Som ett resultat får vi N*N, eller N², iterationer.
Urvalssortering
Denna algoritm liknar bubbelsortering, men den fungerar lite snabbare. Återigen, som ett exempel, låt oss ta en sekvens av tal som vi vill ordna i stigande ordning. Kärnan i denna algoritm är att sekventiellt iterera genom alla siffror och välja det minsta elementet, som vi tar och byter med elementet längst till vänster (det 0:e elementet). Här har vi en situation som liknar bubbelsortering, men i det här fallet kommer vårt sorterade element att vara det minsta. Därför kommer nästa passage genom elementen att börja från elementet med index 1. Vi kommer att upprepa dessa passager tills alla element har sorterats. Implementering i 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;
}
}
}
Denna algoritm är överlägsen bubbelsortering, eftersom antalet nödvändiga skift här reduceras från O(N²) till O(N). Vi kör inte ett element genom hela listan, men antalet jämförelser är fortfarande O(N²).
Insättningssort
Vi betraktar ännu en nummerföljd som vi vill ordna i stigande ordning. Denna algoritm består i att placera en markör, där alla element till vänster om markören redan är delvis sorterade sinsemellan. Vid varje steg i algoritmen kommer ett av elementen att väljas och placeras på önskad position i den delvis sorterade sekvensen. Således kommer den sorterade delen att växa tills alla grundämnen har undersökts. Undrar du hur du får delmängden av element som redan är sorterade och hur vi bestämmer var markören ska placeras? Men arrayen som består av det första elementet är redan sorterad, eller hur? Låt oss ta en titt på implementeringen i 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
}
}
}
Denna typ av sortering är överlägsen de som beskrivs ovan, för trots att den har samma O(N²) körtid är denna algoritm dubbelt så snabb som bubbelsortering och något snabbare än urvalssortering.
Skalsort
Denna sortering är i huvudsak en modifierad infogningssort. Vad pratar jag om? Låt oss sätta första saker först. Vi måste först välja ett intervall. Det finns många sätt att göra detta val. Vi ska inte gå in för mycket i detalj om detta. Låt oss dela vår array på mitten och få ett antal - det här kommer att vara vårt intervall. Så, om vi har 9 element i vår array, kommer vårt intervall att vara 9/2 = 4,5. Vi kastar bråkdelen och får 4, eftersom matrisindex bara kan vara heltal. Vi kommer att använda detta intervall för att bilda våra grupper. Om ett element har index 0, så är indexet för nästa element i sin grupp 0+4, det vill säga 4. Det tredje elementet kommer att ha indexet 4+4, det fjärde — 8+4, och så vidare. I den andra gruppen kommer det första elementet att vara 1,5,9... I den tredje och fjärde gruppen kommer situationen att vara densamma. Som ett resultat, från talmatrisen {6,3,8,8,6,9,4,11,1} får vi fyra grupper: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} De behåller sina platser i den allmänna arrayen, men vi har markerat som medlemmar i samma grupp: {6,3,8,8,6,9,4,11,1} Nästa, infogning sortering tillämpas på dessa grupper, och sedan ser de ut så här: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} I den allmänna arrayen, celler som upptas av grupperna kommer att förbli oförändrade, men deras interna ordning kommer att ändras, enligt ordningen för grupperna ovan: {1,3,4,8,6,9,8,11,6} Arrayen har blivit en lite mer beställt, eller hur? Nästa intervall kommer att delas med 2: 4/2 = 2 Vi har två grupper: I — {1,4,6,8,6} II — {3,8,9,11} I den allmänna arrayen har vi : {1,3,4,8,6,9,8,11,6} Vi kör sorteringsalgoritmen för infogning på båda grupperna och får denna array: {1,3,4,8,6,9,6, 11, 8} Nu är vår array nästan sorterad. Vi måste utföra en sista iteration av algoritmen: vi dividerar intervallet med 2: 2/2 = 1. Vi får en grupp som består av hela arrayen: {1,3,4,8,6,9,6,11 ,8} När vi kör insättningssorteringsalgoritmen på det får vi: {1,3,4,6,6,8,8,9,11} Låt oss ta en titt på hur vi kan få liv i denna sort i Java-kod:
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
}
}
}
För närvarande är Shellsorts prestanda inte lätt att karakterisera, eftersom resultaten skiljer sig åt i olika situationer. Experimentella uppskattningar sträcker sig från O(N 3/2 ) till O(N 7/6 ).
Quicksort
Detta är en av de mest populära algoritmerna, så det är värt att ägna särskild uppmärksamhet åt. Kontentan av denna algoritm är att ett pivotelement väljs i en lista med element. Vi sorterar alla andra element i förhållande till pivotelementet. Värden mindre än pivotelementet finns till vänster. Värden större än det är till höger. Därefter väljs även pivotelement i höger och vänster del, och samma sak händer: värdena sorteras i förhållande till dessa element. Sedan väljs pivotelement i de nybildade delarna, och så vidare tills vi får en sorterad sekvens. Följande Java-implementering av denna algoritm använder rekursion:
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);
}
}
Quicksort-algoritmen är utan tvekan den mest populära, eftersom den i de flesta situationer går snabbare än andra. Dess tidskomplexitet är O(N*logN).
Slå samman sortering
Denna sort är också populär. Det är en av många algoritmer som bygger på principen om "dela och härska". Sådana algoritmer delar först upp problemet i hanterbara delar (quicksort är ett annat exempel på en sådan algoritm). Så vad är kärnan i denna algoritm?
Dela upp:
Arrayen är uppdelad i två delar av ungefär samma storlek. Var och en av dessa två delar är uppdelad i två till, och så vidare tills de minsta möjliga odelbara delarna återstår. Vi har de minsta odelbara delarna när varje array har ett element, alltså en array som redan är sorterad.
Erövra:
Det är här vi börjar processen som gav algoritmen dess namn: sammanfoga. För att göra detta tar vi de två resulterande sorterade arrayerna och slår samman dem till en. I detta fall skrivs det minsta av de första elementen i de två arrayerna in i den resulterande arrayen. Denna operation upprepas tills alla element i dessa två arrayer har kopierats över. Det vill säga, om vi har två minimala arrayer {6} och {4}, jämför vi deras värden och genererar detta sammanslagna resultat: {4,6}. Om vi har sorterade matriserna {4,6} och {2,8} jämför vi först värdena 4 och 2, och sedan skriver vi 2 i den resulterande matrisen. Efter det kommer 4 och 8 att jämföras, och vi skriver 4. Slutligen kommer 6 och 8 att jämföras. Följaktligen kommer vi att skriva 6, och först efter det kommer vi att skriva 8. Som ett resultat får vi följande sammanslagna array: {2,4,6,8}. Hur kommer detta att se ut i Java-kod? För att köra den här algoritmen är det bekvämt för oss att använda rekursion:
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;
}
}
Som i snabbsorteringen flyttar vi den rekursiva metoden till en mellanmetod så att användaren bara behöver tillhandahålla arrayen som ska sorteras och inte behöver oroa sig för att tillhandahålla några ytterligare standardargument. Denna algoritm har likheter med quicksort, och föga förvånande är dess exekveringshastighet densamma: O(N*logN).
2. giriga algoritmer
En girig algoritm är ett tillvägagångssätt där lokalt optimala beslut fattas i varje steg, med antagandet att den slutliga lösningen också blir optimal. Den "optimala" lösningen kommer att vara den som erbjuder den mest uppenbara och omedelbara fördelen vid ett visst steg/steg. För att utforska denna algoritm, låt oss ta ett ganska vanligt problem - ryggsäcksproblemet. Låtsas för ett ögonblick att du är en tjuv. Du har tagit dig in i en butik på natten med en ryggsäck. Framför dig finns flera varor som du kan stjäla. Men samtidigt har din ryggsäck begränsad kapacitet. Den kan inte bära mer än 30 viktenheter. Du vill också bära bort den mest värdefulla uppsättningen varor som får plats i ryggsäcken. Hur bestämmer du vad du ska lägga i din väska? Så,
Välj det dyraste föremålet som inte har tagits ännu.
Om den får plats i ryggsäcken, lägg i den. Om inte, lämna den då.
Har vi redan stulit allt? Om inte, återgår vi till steg 1. Om ja, då gör vi vår snabba flykt från butiken, eftersom vi har åstadkommit det vi kom för att göra.
Låt oss titta på detta, men i Java. Så här kommer klassen Item att se ut:
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;
}
}
Det finns inget speciellt här: tre fält (namn, vikt, värde) som definierar föremålens egenskaper. Som du kan se är det jämförbara gränssnittet också implementerat så att vi kan sortera våra artiklar efter pris. Därefter ska vi titta på Bag-klassen, som representerar vår ryggsäck:
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 är vår ryggsäcks kapacitet, som ställs in när vi skapar ett objekt;
föremål representerar föremålen i vår ryggsäck;
currentWeight , currentValue — dessa fält lagrar den aktuella vikten och värdet för alla föremål i ryggsäcken, vilket vi ökar när vi lägger till ett nytt föremål i addItem-metoden.
Hur som helst, låt oss nu gå till klassen där all handling äger rum:
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());
}
}
Först skapar vi en lista med objekt och sorterar den. Vi skapar ett påsobjekt med en kapacitet på 30 enheter. Därefter skickar vi föremålen och påsobjektet till fillBackpack-metoden, som fyller ryggsäcken enligt vår giriga algoritm:
Det är ganska enkelt: vi börjar gå igenom en lista med föremål sorterade efter kostnad och lägger dem i påsen om dess kapacitet tillåter. Om det inte finns tillräckligt med utrymme kommer objektet att hoppas över och vi fortsätter att gå över resten av objekten tills vi når slutet av listan. När vi kör main, här är konsolutgången vi får:
Ryggsäckens vikt är 29. Det totala värdet av föremålen i ryggsäcken är 3700
Detta är ett exempel på en girig algoritm: vid varje steg väljs en lokalt optimal lösning, och i slutändan får du en globalt optimal lösning. I vårt fall är det bästa alternativet den dyraste varan. Men är detta den bästa lösningen? Tror du inte att det är möjligt att förbättra vår lösning något för att fylla vår ryggsäck med föremål som har ännu större totalvärde? Låt oss ta en titt på hur detta kan göras.
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());
}
}
}
Här beräknar vi först värde-till-vikt-förhållandet för varje artikel. Detta berättar för oss värdet av varje enhet av en given vara. Och sedan använder vi dessa förhållanden för att sortera våra föremål och lägga till dem i vår väska. Låt oss köra följande:
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());
Vi får denna konsolutgång:
Vikten på ryggsäcken är 29. Den totala kostnaden för föremål i ryggsäcken är 4150
Lite bättre, eller hur? Den giriga algoritmen gör ett lokalt optimalt val vid varje steg, i hopp om att den slutliga lösningen också blir optimal. Detta antagande är inte alltid giltigt, men för många uppgifter ger giriga algoritmer en optimal slutlig lösning. Tidskomplexiteten för denna algoritm är O(N). Ganska bra, va?
Och eftersom du är på den här webbplatsen, ska jag vara så djärv att anta att du skriver i Java. Det är därför jag idag föreslår att du bekantar dig med några grundläggande algoritmer och med specifika exempel på hur man implementerar dem i Java. Med "några" menar jag:
GO TO FULL VERSION