Utviklingsprosjekter bruker ulike algoritmer oftere enn du kanskje tror. Anta for eksempel at vi må sortere noen data etter bestemte parametere (kolonner) slik at vi kan navigere gjennom dataene uten mye innsats. Så det ville ikke være rart i det hele tatt for en jobbintervjuer å spørre deg om en spesifikk grunnleggende algoritme og kanskje gi oppgaven med å implementere den ved hjelp av kode. Og siden du er på denne nettsiden, skal jeg være så dristig å anta at du skriver i Java. Derfor foreslår jeg i dag at du gjør deg kjent med noen grunnleggende algoritmer og med spesifikke eksempler på hvordan du implementerer dem i Java. Med "noen" mener jeg:
Oversikt over array-sorteringsalgoritmer:
boble sortering,
utvalg sortering,
innsettingssortering,
Skall sortering,
kvikksortering,
slå sammen sortering,
Grådige algoritmer
Stifinnende algoritmer
dybde-første søk
bredde-første søk
Dijkstras Shortest Path First-algoritme
Vel, uten videre, la oss komme i gang.
1. Oversikt over sorteringsalgoritmer
Boble sortering
Denne sorteringsalgoritmen er først og fremst kjent for sin enkelhet, men den er også en av de tregeste. Som et eksempel, la oss vurdere en boblesortering for tall i stigende rekkefølge. La oss forestille oss en tilfeldig rekkefølge av tall. Vi vil utføre følgende trinn på disse tallene, fra begynnelsen av sekvensen:
sammenligne to tall;
hvis tallet til venstre er større, bytt dem;
flytte en posisjon til høyre.
Etter å ha utført disse trinnene på hele sekvensen, vil vi finne at det største tallet er på slutten av vår tallserie. Deretter gjør vi en ny pass over sekvensen, og utfører nøyaktig de samme trinnene som ovenfor. Men denne gangen tar vi ikke med det siste elementet i listen, siden det er det største tallet og allerede nøyaktig der det skal være når tallene sorteres. Nok en gang vil vi ende opp med å flytte det nest største tallet til slutten av sekvensen vår. Det betyr selvfølgelig at de to største tallene står på riktig plass. Igjen går vi over sekvensen, ekskluderer elementene som allerede er på plass, til alle elementene er i ønsket rekkefølge. La oss ta en titt på hvordan boblesortering er implementert i Java-kode:
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, er det ikke noe komplisert her. Alt virker bare bra, og det ville vært hvis ikke for en mangel - boblesortering er veldig, veldig sakte. Tidskompleksiteten er O(N²), siden vi har nestede løkker. Den ytre løkken over elementene utføres N ganger. Den indre sløyfen utføres også N ganger. Som et resultat får vi N*N, eller N², iterasjoner.
Utvalgssortering
Denne algoritmen ligner på boblesortering, men den fungerer litt raskere. Igjen, som et eksempel, la oss ta en rekke tall som vi ønsker å ordne i stigende rekkefølge. Essensen av denne algoritmen er å sekvensielt iterere gjennom alle tallene og velge det minste elementet, som vi tar og bytter med elementet lengst til venstre (det 0. elementet). Her har vi en situasjon som ligner på boblesortering, men i dette tilfellet vil vårt sorterte element være det minste. Derfor vil neste passering gjennom elementene starte fra elementet med indeks 1. Vi gjentar disse passeringene til alle elementene er sortert. 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;
}
}
}
Denne algoritmen er overlegen boblesortering, fordi her er antall nødvendige skift redusert fra O(N²) til O(N). Vi kjører ikke ett element gjennom hele listen, men antall sammenligninger er fortsatt O(N²).
Innsettingssortering
Vi tar for oss enda en tallrekke som vi ønsker å ordne i stigende rekkefølge. Denne algoritmen består i å plassere en markør, der alle elementene til venstre for markøren allerede er delvis sortert mellom seg. Ved hvert trinn i algoritmen vil ett av elementene bli valgt og plassert på ønsket posisjon i den delvis sorterte sekvensen. Dermed vil den sorterte delen vokse til alle elementene er undersøkt. Lurer du på hvordan du får delsettet av elementer som allerede er sortert og hvordan vi bestemmer hvor vi skal plassere markøren? Men matrisen som består av det første elementet er allerede sortert, er det ikke? La 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
}
}
}
Denne typen sortering er overlegen de som er beskrevet ovenfor, fordi til tross for at den har samme O(N²) kjøretid, er denne algoritmen dobbelt så rask som boblesortering og litt raskere enn utvalgssortering.
Skall sortering
Denne typen er i hovedsak en modifisert innsettingssortering. Hva snakker jeg om? La oss sette første ting først. Vi må først velge et intervall. Det er mange måter å gjøre dette valget på. Vi vil ikke gå for mye i detalj om dette. La oss dele matrisen vår i to og få et tall - dette vil være intervallet vårt. Så hvis vi har 9 elementer i matrisen vår, vil intervallet vårt være 9/2 = 4,5. Vi forkaster brøkdelen og får 4, siden matriseindekser bare kan være heltall. Vi vil bruke dette intervallet til å danne våre grupper. Hvis et element har indeks 0, så er indeksen til det neste elementet i gruppen 0+4, det vil si 4. Det tredje elementet vil ha indeksen 4+4, det fjerde — 8+4, og så videre. I den andre gruppen vil det første elementet være 1,5,9... I den tredje og fjerde gruppen vil situasjonen være den samme. Som et resultat, fra tallmatrisen {6,3,8,8,6,9,4,11,1} får vi fire grupper: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} De beholder plassene sine i den generelle matrisen, men vi har merket som medlemmer av samme gruppe: {6,3,8,8,6,9,4,11,1} Neste, innsetting sortering brukes på disse gruppene, og så ser de slik ut: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} I den generelle matrisen, cellene som er okkupert av gruppene vil forbli den samme, men deres interne rekkefølge vil endres, i henhold til rekkefølgen til gruppene ovenfor: {1,3,4,8,6,9,8,11,6} Matrisen har blitt en litt mer bestilt, ikke sant? Det neste intervallet blir delt med 2: 4/2 = 2 Vi har to grupper: I — {1,4,6,8,6} II — {3,8,9,11} I den generelle matrisen har vi : {1,3,4,8,6,9,8,11,6} Vi kjører innsettingssorteringsalgoritmen på begge gruppene, og får denne matrisen: {1,3,4,8,6,9,6, 11, 8} Nå er matrisen vår nesten sortert. Vi må utføre en siste iterasjon av algoritmen: vi deler intervallet med 2: 2/2 = 1. Vi får en gruppe som består av hele matrisen: {1,3,4,8,6,9,6,11 ,8} Når vi kjører innsettingssorteringsalgoritmen på det, får vi: {1,3,4,6,6,8,8,9,11} La oss ta en titt på hvordan vi kan bringe denne typen til live i Java-kode:
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
}
}
}
For øyeblikket er Shellsorts ytelse ikke lett å karakterisere, siden resultatene er forskjellige i ulike situasjoner. Eksperimentelle estimater varierer fra O(N 3/2 ) til O(N 7/6 ).
Quicksort
Dette er en av de mest populære algoritmene, så det er verdt å være spesielt oppmerksom på. Hovedpoenget med denne algoritmen er at et pivotelement er valgt i en liste over elementer. Vi sorterer alle de andre elementene i forhold til pivotelementet. Verdier mindre enn pivotelementet er til venstre. Verdier større enn det er til høyre. Deretter velges også pivotelementer i høyre og venstre del, og det samme skjer: verdiene sorteres i forhold til disse elementene. Deretter velges pivotelementer i de nyopprettede delene, og så videre til vi får en sortert sekvens. Følgende Java-implementering av denne algoritmen bruker rekursjon:
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);
}
}
Uten tvil er quicksort-algoritmen den mest populære, siden den i de fleste situasjoner kjører raskere enn andre. Tidskompleksiteten er O(N*logN).
Slå sammen sortering
Denne typen er også populær. Det er en av mange algoritmer som baserer seg på prinsippet om "del og hersk". Slike algoritmer deler først problemet inn i håndterbare deler (quicksort er et annet eksempel på en slik algoritme). Så hva er kjernen i denne algoritmen?
Dele opp:
Matrisen er delt i to deler av omtrent samme størrelse. Hver av disse to delene er delt i to til, og så videre til de minste mulige udelelige delene gjenstår. Vi har de minste udelelige delene når hver matrise har ett element, altså en matrise som allerede er sortert.
Erobre:
Det er her vi begynner prosessen som ga navnet til algoritmen: flette. For å gjøre dette tar vi de to resulterende sorterte matrisene og slår dem sammen til en. I dette tilfellet skrives det minste av de første elementene i de to matrisene inn i den resulterende matrisen. Denne operasjonen gjentas til alle elementene i disse to matrisene er kopiert over. Det vil si at hvis vi har to minimale matriser {6} og {4}, sammenligner vi verdiene deres og genererer dette sammenslåtte resultatet: {4,6}. Hvis vi har sortert matriser {4,6} og {2,8}, sammenligner vi først verdiene 4 og 2, og så skriver vi 2 inn i den resulterende matrisen. Etter det vil 4 og 8 sammenlignes, og vi skriver 4. Til slutt vil 6 og 8 sammenlignes. Følgelig vil vi skrive 6, og først etter det vil vi skrive 8. Som et resultat får vi følgende sammenslåtte matrise: {2,4,6,8}. Hvordan vil dette se ut i Java-kode? For å kjøre denne algoritmen vil det være praktisk for oss å bruke rekursjon:
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 rask sortering, flytter vi den rekursive metoden til en mellommetode slik at brukeren bare trenger å levere matrisen som skal sorteres og ikke trenger å bekymre seg for å gi noen ekstra standardargumenter. Denne algoritmen har likheter med quicksort, og ikke overraskende er utførelseshastigheten den samme: O(N*logN).
2. Grådige algoritmer
En grådig algoritme er en tilnærming der lokalt optimale beslutninger tas på hvert trinn, med antagelse om at den endelige løsningen også vil være optimal. Den "optimale" løsningen vil være den som gir den mest åpenbare og umiddelbare fordelen på et bestemt trinn/stadium. For å utforske denne algoritmen, la oss ta et ganske vanlig problem - ryggsekkproblemet. Lat som om du er en tyv et øyeblikk. Du har brutt deg inn i en butikk om natten med en ryggsekk. Foran deg er flere varer du kan stjele. Men samtidig har ryggsekken begrenset kapasitet. Den kan ikke bære mer enn 30 vektenheter. Du ønsker også å bære bort det mest verdifulle settet med varer som får plass i ryggsekken. Hvordan bestemmer du hva du skal putte i vesken? Så,
Velg den dyreste varen som ikke er tatt ennå.
Hvis den får plass i ryggsekken, legg den i. Hvis ikke, så la den stå.
Har vi allerede stjålet alt? Hvis ikke, går vi tilbake til trinn 1. Hvis ja, så tar vi en rask flukt fra butikken, siden vi har oppnådd det vi kom for å gjøre.
La oss se på dette, men i Java. Slik vil vareklassen 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 er ikke noe spesielt her: tre felt (navn, vekt, verdi) som definerer egenskapene til varen. Som du kan se, er det sammenlignbare grensesnittet implementert for å tillate oss å sortere varene våre etter pris. Deretter skal vi se på Bag-klassen, som representerer ryggsekken vår:
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 er ryggsekkens kapasitet, som settes når vi lager et objekt;
gjenstander representerer gjenstandene i ryggsekken vår;
currentWeight , currentValue — disse feltene lagrer gjeldende vekt og verdi av alle varene i ryggsekken, som vi øker når vi legger til en ny vare i addItem-metoden.
Uansett, la oss nå gå til klassen der all handlingen finner sted:
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 lager vi en liste over elementer og sorterer den. Vi lager et poseobjekt med en kapasitet på 30 enheter. Deretter sender vi gjenstandene og poseobjektet til fillBackpack-metoden, som fyller ryggsekken i henhold til vår grådige algoritme:
Det er ganske enkelt: vi begynner å gå gjennom en liste over varer sortert etter pris og legge dem i posen hvis kapasiteten tillater det. Hvis det ikke er nok plass, vil elementet hoppes over og vi fortsetter å krysse over resten av elementene til vi når slutten av listen. Når vi kjører main, her er konsollutgangen vi får:
Ryggsekkens vekt er 29. Den totale verdien av gjenstandene i ryggsekken er 3700
Dette er et eksempel på en grådig algoritme: Ved hvert trinn velges en lokalt optimal løsning, og til slutt får du en globalt optimal løsning. I vårt tilfelle er det beste alternativet den dyreste varen. Men er dette den beste løsningen? Tror du ikke det er mulig å forbedre løsningen vår litt for å fylle ryggsekken vår med varer som har enda større totalverdi? La oss ta en titt på hvordan dette kan gjøres.
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());
}
}
}
Her beregner vi først verdi-til-vekt-forholdet for hver vare. Dette forteller oss verdien av hver enhet av en gitt vare. Og så bruker vi disse forholdstallene til å sortere varene våre og legge dem i vesken vår. La oss kjøre følgende:
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 denne konsollutgangen:
Vekten på ryggsekken er 29. Totalkostnaden for varer i ryggsekken er 4150,-
Litt bedre, ikke sant? Den grådige algoritmen gjør et lokalt optimalt valg på hvert trinn, i håp om at den endelige løsningen også blir optimal. Denne antakelsen er ikke alltid gyldig, men for mange oppgaver gir grådige algoritmer en optimal endelig løsning. Tidskompleksiteten til denne algoritmen er O(N). Ganske bra, ikke sant?
Og siden du er på denne nettsiden, skal jeg være så dristig å anta at du skriver i Java. Derfor foreslår jeg i dag at du gjør deg kjent med noen grunnleggende algoritmer og med spesifikke eksempler på hvordan du implementerer dem i Java. Med "noen" mener jeg:
GO TO FULL VERSION