Proiectele de dezvoltare folosesc diverși algoritmi mai des decât ați crede. De exemplu, să presupunem că trebuie să sortăm unele date după anumiți parametri (coloane), astfel încât să putem naviga prin date fără prea mult efort. Așa că nu ar fi deloc ciudat ca un intervievator să vă întrebe despre un anumit algoritm de bază și poate să dea sarcina de a-l implementa folosind cod. Și din moment ce sunteți pe acest site, voi fi atât de îndrăzneț încât să presupun că scrieți în Java. De aceea, astăzi vă sugerez să vă familiarizați cu câțiva algoritmi de bază și cu exemple specifice de implementare a acestora în Java. Prin „unii”, vreau să spun:
Prezentare generală a algoritmilor de sortare a matricei:
sortare cu bule,
sortare de selecție,
sortare prin inserare,
sortare Shell,
sortare rapida,
sortare îmbinare,
Algoritmi lacomi
Algoritmi de descoperire a traseului
căutarea în profunzime
căutarea pe lățimea întâi
Algoritmul Dijkstra’s Shortest Path First
Ei bine, fără alte prelungiri, să trecem la treabă.
1. Prezentare generală a algoritmilor de sortare
Sortare cu bule
Acest algoritm de sortare este cunoscut în primul rând pentru simplitatea sa, dar este și unul dintre cele mai lente. De exemplu, să luăm în considerare un sortare cu bule pentru numere în ordine crescătoare. Să ne imaginăm o succesiune aleatorie de numere. Vom efectua următorii pași pe aceste numere, începând de la începutul secvenței:
compara două numere;
dacă numărul din stânga este mai mare, atunci schimbă-le;
mutați o poziție spre dreapta.
După efectuarea acestor pași pe întreaga secvență, vom descoperi că cel mai mare număr se află la sfârșitul seriei noastre de numere. Apoi facem o altă trecere peste secvență, executând exact aceiași pași ca mai sus. Dar de data aceasta nu vom include ultimul element al listei, deoarece este cel mai mare număr și deja exact unde ar trebui să fie atunci când numerele sunt sortate. Încă o dată, vom ajunge să mutăm următorul număr cel mai mare la sfârșitul secvenței noastre. Desigur, asta înseamnă că cele două numere cele mai mari stau la locul lor. Din nou, facem treceri peste secvență, excluzând elementele care sunt deja la locul lor, până când toate elementele sunt în ordinea necesară. Să aruncăm o privire la modul în care sortarea cu bule este implementată în codul 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;
}
}
}
}
}
După cum puteți vedea, nu este nimic complicat aici. Totul pare grozav și ar fi dacă nu pentru un singur dezavantaj - sortarea cu bule este foarte, foarte lentă. Complexitatea timpului este O(N²), deoarece avem bucle imbricate. Bucla exterioară peste elemente se realizează de N ori. Bucla interioară este, de asemenea, executată de N ori. Ca rezultat, obținem N*N, sau N², iterații.
Sortare selecție
Acest algoritm este similar cu sortarea cu bule, dar funcționează puțin mai rapid. Din nou, ca exemplu, să luăm o succesiune de numere pe care dorim să le aranjam în ordine crescătoare. Esența acestui algoritm este de a repeta secvențial prin toate numerele și de a selecta cel mai mic element, pe care îl luăm și îl schimbăm cu elementul din stânga (al 0-lea element). Aici avem o situație similară cu sortarea cu bule, dar în acest caz elementul nostru sortat va fi cel mai mic. Prin urmare, următoarea trecere prin elemente va începe de la elementul cu indicele 1. Vom repeta aceste treceri până când toate elementele au fost sortate. Implementare 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;
}
}
}
Acest algoritm este superior sortării cu bule, deoarece aici numărul de schimburi necesare este redus de la O(N²) la O(N). Nu conducem un element prin întreaga listă, dar numărul de comparații este încă O(N²).
Sortare prin inserare
Luăm în considerare încă o secvență de numere pe care dorim să o aranjam în ordine crescătoare. Acest algoritm constă în plasarea unui marker, în care toate elementele din stânga markerului sunt deja parțial sortate între ele. La fiecare pas al algoritmului, unul dintre elemente va fi selectat și plasat în poziția dorită în secvența sortată parțial. Astfel, partea sortată va crește până când toate elementele vor fi examinate. Vă întrebați cum obțineți subsetul de elemente care sunt deja sortate și cum determinăm unde să punem marcajul? Dar matricea compusă din primul element este deja sortată, nu-i așa? Să aruncăm o privire asupra implementării în 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
}
}
}
Acest tip de sortare este superior celor descrise mai sus, deoarece, în ciuda faptului că are același timp de rulare O(N²), acest algoritm este de două ori mai rapid decât sortarea cu bule și puțin mai rapid decât sortarea prin selecție.
Sortare Shell
Acest sortare este, în esență, o sortare de inserție modificată. Despre ce vorbesc? Să punem pe primul loc lucrurile. Mai întâi trebuie să alegem un interval. Există multe abordări pentru a face această alegere. Nu vom intra în prea multe detalii despre asta. Să împărțim matricea noastră în jumătate și să obținem un număr - acesta va fi intervalul nostru. Deci, dacă avem 9 elemente în tabloul nostru, atunci intervalul nostru va fi 9/2 = 4,5. Renunțăm la partea fracțională și obținem 4, deoarece indicii de matrice pot fi numai numere întregi. Vom folosi acest interval pentru a ne forma grupurile. Dacă un element are indicele 0, atunci indicele următorului element din grupul său este 0+4, adică 4. Al treilea element va avea indicele 4+4, al patrulea — 8+4 și așa mai departe. În a doua grupă, primul element va fi 1,5,9... În a treia și a patra grupă, situația va fi aceeași. Ca urmare, din tabloul de numere {6,3,8,8,6,9,4,11,1} obținem patru grupuri: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} Ei își păstrează locurile în matricea generală, dar am marcat ca membri ai aceluiași grup: {6,3,8,8,6,9,4,11,1} În continuare, inserare sortarea este aplicată acestor grupuri și apoi arată astfel: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} În tabloul general, celulele ocupate de grupuri vor rămâne aceleași, dar ordinea lor internă se va schimba, conform ordinii grupurilor de mai sus: {1,3,4,8,6,9,8,11,6} Matricea a devenit un putin mai comandat, nu-i asa? Următorul interval va fi împărțit la 2: 4/2 = 2 Avem două grupuri: I — {1,4,6,8,6} II — {3,8,9,11} În tabloul general, avem : {1,3,4,8,6,9,8,11,6} Rulăm algoritmul de sortare prin inserare pe ambele grupuri și obținem această matrice: {1,3,4,8,6,9,6, 11, 8} Acum matricea noastră este aproape sortată. Trebuie să facem o iterație finală a algoritmului: împărțim intervalul la 2: 2/2 = 1. Obținem un grup format din întregul tablou: {1,3,4,8,6,9,6,11 ,8} Rulând algoritmul de sortare prin inserare, obținem: {1,3,4,6,6,8,8,9,11} Să aruncăm o privire la cum putem aduce acest sort la viață în codul 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
}
}
}
În prezent, performanța Shellsort nu este ușor de caracterizat, deoarece rezultatele diferă în diferite situații. Estimările experimentale variază de la O(N3 /2 ) la O(N7 /6 ).
Sortare rapida
Acesta este unul dintre cei mai populari algoritmi, așa că merită să îi acordați o atenție deosebită. Esența acestui algoritm este că un element pivot este selectat într-o listă de elemente. Sortăm toate celelalte elemente în raport cu elementul pivot. Valorile mai mici decât elementul pivot sunt în stânga. Valorile mai mari decât acestea sunt în dreapta. Apoi, elementele pivot sunt selectate și în părțile din dreapta și din stânga și se întâmplă același lucru: valorile sunt sortate în funcție de aceste elemente. Apoi elementele pivot sunt selectate în părțile nou formate și așa mai departe până când obținem o secvență sortată. Următoarea implementare Java a acestui algoritm folosește recursiunea:
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);
}
}
Fără îndoială, algoritmul de sortare rapidă este cel mai popular, deoarece în majoritatea situațiilor rulează mai repede decât altele. Complexitatea sa de timp este O(N*logN).
Sortare îmbinare
Acest tip este, de asemenea, popular. Este unul dintre mulți algoritmi care se bazează pe principiul „împărți și cuceri”. Astfel de algoritmi împart mai întâi problema în părți gestionabile (quicksort este un alt exemplu de astfel de algoritm). Deci, care este esenta acestui algoritm?
Divide:
Matricea este împărțită în două părți de aproximativ aceeași dimensiune. Fiecare dintre aceste două părți este împărțită în încă două și așa mai departe până când rămân cele mai mici părți indivizibile posibile. Avem cele mai mici părți indivizibile atunci când fiecare tablou are un element, adică un tablou care este deja sortat.
A cuceri:
Aici începem procesul care a dat algoritmului numele: merge. Pentru a face acest lucru, luăm cele două matrice sortate rezultate și le îmbinăm într-una singură. În acest caz, cel mai mic dintre primele elemente ale celor două tablouri este scris în tabloul rezultat. Această operație se repetă până când toate elementele din aceste două tablouri au fost copiate. Adică, dacă avem două tablouri minime {6} și {4}, comparăm valorile lor și generăm acest rezultat îmbinat: {4,6}. Dacă avem matrice sortate {4,6} și {2,8}, mai întâi comparăm valorile 4 și 2, apoi scriem 2 în tabloul rezultat. După aceea, 4 și 8 vor fi comparați și vom scrie 4. În cele din urmă, 6 și 8 vor fi comparați. În consecință, vom scrie 6 și numai după aceea vom scrie 8. Ca rezultat, obținem următorul tablou îmbinat: {2,4,6,8}. Cum va arăta asta în codul Java? Pentru a rula acest algoritm, ne va fi convenabil să folosim recursiunea:
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;
}
}
Ca și în sortarea rapidă, mutăm metoda recursivă într-o metodă intermediară, astfel încât utilizatorul trebuie doar să furnizeze matricea care urmează să fie sortată și să nu aibă grijă să furnizeze argumente implicite suplimentare. Acest algoritm are asemănări cu sortarea rapidă și, fără a fi surprinzător, viteza sa de execuție este aceeași: O(N*logN).
2. Algoritmi greedy
Un algoritm lacom este o abordare în care deciziile optime la nivel local sunt luate în fiecare etapă, cu presupunerea că soluția finală va fi, de asemenea, optimă. Soluția „optimă” va fi cea care oferă cel mai evident și imediat beneficiu la orice pas/etapă anume. Pentru a explora acest algoritm, să luăm o problemă destul de comună - problema rucsacului. Prefă-te pentru o clipă că ești un hoț. Ai intrat noaptea într-un magazin cu un rucsac (rucsac). În fața ta sunt mai multe bunuri pe care le-ai putea fura. Dar, în același timp, rucsacul tău are o capacitate limitată. Nu poate transporta mai mult de 30 de unități de greutate. De asemenea, vrei să duci cel mai valoros set de bunuri care se va potrivi în rucsac. Cum stabiliți ce să puneți în geantă? Asa de,
Alegeți cel mai scump articol care nu a fost încă luat.
Dacă se potrivește în rucsac, puneți-l. Dacă nu, lăsați-l.
Am furat deja totul? Dacă nu, revenim la pasul 1. Dacă da, atunci ne evadăm rapid din magazin, din moment ce am realizat ceea ce am venit să facem.
Să ne uităm la asta, dar în Java. Iată cum va arăta clasa 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;
}
}
Nu este nimic special aici: trei câmpuri (nume, greutate, valoare) care definesc caracteristicile articolului. De asemenea, după cum puteți vedea, interfața Comparabil este implementată pentru a ne permite să ne sortăm articolele după preț. În continuare, ne vom uita la clasa Bag, care reprezintă rucsacul nostru:
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 este capacitatea rucsacului nostru, care este setată atunci când creăm un obiect;
articole reprezintă obiectele din rucsacul nostru;
currentWeight , currentValue — aceste câmpuri stochează greutatea și valoarea curentă a tuturor articolelor din rucsac, pe care le creștem atunci când adăugăm un articol nou în metoda addItem.
Oricum, să mergem acum la clasa în care are loc toată acțiunea:
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());
}
}
Mai întâi, creăm o listă de articole și o sortăm. Cream un obiect geanta cu o capacitate de 30 de unitati. Apoi, trecem articolele și obiectul sac la metoda fillBackpack, care umple rucsacul conform algoritmului nostru lacom:
Este destul de simplu: începem să parcurgem o listă de articole sortate după cost și să le punem în geantă dacă capacitatea ne permite. Dacă nu este suficient spațiu, atunci articolul va fi omis și vom continua să parcurgem restul articolelor până ajungem la sfârșitul listei. Odată ce rulăm main, iată ieșirea consolei pe care o vom obține:
Greutatea rucsacului este de 29. Valoarea totală a articolelor din rucsac este de 3700
Acesta este un exemplu de algoritm lacom: la fiecare pas, este selectată o soluție optimă la nivel local și, în final, obțineți o soluție optimă la nivel global. În cazul nostru, cea mai bună opțiune este cel mai scump articol. Dar este aceasta cea mai bună soluție? Nu crezi că este posibil să ne îmbunătățim ușor soluția pentru a ne umple rucsacul cu articole care au o valoare totală și mai mare? Să aruncăm o privire la cum se poate face acest lucru.
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());
}
}
}
Aici calculăm mai întâi raportul valoare-greutate pentru fiecare articol. Aceasta ne spune valoarea fiecărei unități a unui articol dat. Și apoi folosim aceste rapoarte pentru a ne sorta articolele și pentru a le adăuga în geanta noastră. Să rulăm următoarele:
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());
Obținem această ieșire de consolă:
Greutatea rucsacului este de 29. Costul total al articolelor din rucsac este de 4150
Puțin mai bine, nu-i așa? Algoritmul greedy face o alegere optimă local la fiecare pas, sperând că și soluția finală va fi optimă. Această ipoteză nu este întotdeauna validă, dar pentru multe sarcini, algoritmii lacomi oferă o soluție finală optimă. Complexitatea de timp a acestui algoritm este O(N). Destul de bine, nu?
Și din moment ce sunteți pe acest site, voi fi atât de îndrăzneț încât să presupun că scrieți în Java. De aceea, astăzi vă sugerez să vă familiarizați cu câțiva algoritmi de bază și cu exemple specifice de implementare a acestora în Java. Prin „unii”, vreau să spun:
GO TO FULL VERSION