I progetti di sviluppo utilizzano vari algoritmi più spesso di quanto si possa pensare. Ad esempio, supponiamo di dover ordinare alcuni dati in base a determinati parametri (colonne) in modo da poter navigare tra i dati senza troppi sforzi. Quindi non sarebbe affatto strano che un intervistatore ti chiedesse informazioni su uno specifico algoritmo di base e magari ti desse il compito di implementarlo utilizzando il codice. E visto che sei su questo sito, sarò così audace da presumere che tu stia scrivendo in Java. Ecco perché oggi ti suggerisco di familiarizzare con alcuni algoritmi di base e con esempi specifici di come implementarli in Java. Con "alcuni" intendo:
Panoramica degli algoritmi di ordinamento degli array:
sorta di bolla,
ordinamento di selezione,
ordinamento per inserzione,
Tipo di conchiglia,
smistamento rapido,
unisci ordinamento,
Algoritmi avidi
Algoritmi di ricerca del percorso
ricerca in profondità
ricerca in ampiezza
Algoritmo del primo percorso più breve di Dijkstra
Bene, senza ulteriori indugi, mettiamoci al lavoro.
1. Cenni sugli algoritmi di ordinamento
Sorta a bolle
Questo algoritmo di ordinamento è noto principalmente per la sua semplicità, ma è anche uno dei più lenti. Ad esempio, consideriamo un ordinamento a bolle per i numeri in ordine crescente. Immaginiamo una sequenza casuale di numeri. Eseguiremo i seguenti passaggi su questi numeri, partendo dall'inizio della sequenza:
confrontare due numeri;
se il numero a sinistra è più grande, scambiali;
spostati di una posizione a destra.
Dopo aver eseguito questi passaggi sull'intera sequenza, scopriremo che il numero più grande si trova alla fine della nostra serie di numeri. Quindi eseguiamo un altro passaggio sulla sequenza, eseguendo esattamente gli stessi passaggi di cui sopra. Ma questa volta non includeremo l'ultimo elemento dell'elenco, poiché è il numero più grande e già esattamente dove dovrebbe essere quando i numeri vengono ordinati. Ancora una volta, finiremo per spostare il prossimo numero più grande alla fine della nostra sequenza. Ovviamente, ciò significa che i due numeri più grandi sono al posto giusto. Ancora una volta, eseguiamo passaggi sulla sequenza, escludendo gli elementi che sono già al loro posto, finché tutti gli elementi non sono nell'ordine richiesto. Diamo un'occhiata a come viene implementato il bubble sort nel codice 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;
}
}
}
}
}
Come puoi vedere, non c'è niente di complicato qui. Tutto sembra semplicemente fantastico e lo sarebbe se non fosse per un difetto: il bubble sort è molto, molto lento. La sua complessità temporale è O(N²), dato che abbiamo cicli nidificati. Il ciclo esterno sugli elementi viene eseguito N volte. Anche il ciclo interno viene eseguito N volte. Di conseguenza, otteniamo N*N, o N², iterazioni.
Ordinamento della selezione
Questo algoritmo è simile al bubble sort, ma funziona un po' più velocemente. Di nuovo, come esempio, prendiamo una sequenza di numeri che vogliamo disporre in ordine crescente. L'essenza di questo algoritmo consiste nell'iterare in sequenza tutti i numeri e selezionare l'elemento più piccolo, che prendiamo e scambiamo con l'elemento più a sinistra (l'elemento 0). Qui abbiamo una situazione simile al bubble sort, ma in questo caso il nostro elemento ordinato sarà il più piccolo. Pertanto, il passaggio successivo tra gli elementi inizierà dall'elemento con indice 1. Ripeteremo questi passaggi finché tutti gli elementi non saranno stati ordinati. Implementazione 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;
}
}
}
Questo algoritmo è superiore al bubble sort, perché qui il numero di turni richiesti è ridotto da O(N²) a O(N). Non stiamo guidando un elemento attraverso l'intero elenco, ma il numero di confronti è ancora O(N²).
Ordinamento per inserzione
Consideriamo ancora un'altra sequenza numerica che vogliamo organizzare in ordine crescente. Questo algoritmo consiste nel posizionare un marcatore, dove tutti gli elementi a sinistra del marcatore sono già parzialmente ordinati tra loro. Ad ogni passo dell'algoritmo, uno degli elementi verrà selezionato e collocato nella posizione desiderata nella sequenza parzialmente ordinata. Pertanto, la parte ordinata crescerà fino a quando tutti gli elementi non saranno stati esaminati. Ti stai chiedendo come ottenere il sottoinsieme di elementi che sono già ordinati e come determiniamo dove posizionare il marcatore? Ma l'array composto dal primo elemento è già ordinato, vero? Diamo un'occhiata all'implementazione 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
}
}
}
Questo tipo di ordinamento è superiore a quelli descritti sopra, perché nonostante abbia lo stesso tempo di esecuzione O(N²), questo algoritmo è due volte più veloce del bubble sort e leggermente più veloce del selection sort.
Tipo di conchiglia
Questo ordinamento è essenzialmente un ordinamento di inserimento modificato. Di cosa sto parlando? Mettiamo le prime cose al primo posto. Dobbiamo prima scegliere un intervallo. Ci sono molti approcci per fare questa scelta. Non entreremo troppo nei dettagli su questo. Dividiamo il nostro array a metà e otteniamo un numero: questo sarà il nostro intervallo. Quindi, se abbiamo 9 elementi nel nostro array, il nostro intervallo sarà 9/2 = 4,5. Scartiamo la parte frazionaria e otteniamo 4, poiché gli indici dell'array possono essere solo numeri interi. Useremo questo intervallo per formare i nostri gruppi. Se un elemento ha indice 0, l'indice dell'elemento successivo nel suo gruppo è 0+4, cioè 4. Il terzo elemento avrà l'indice 4+4, il quarto 8+4 e così via. Nel secondo gruppo, il primo elemento sarà 1,5,9... Nel terzo e quarto gruppo la situazione sarà la stessa. Di conseguenza, dall'array numerico {6,3,8,8,6,9,4,11,1} otteniamo quattro gruppi: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} Mantengono il loro posto nell'array generale, ma li abbiamo contrassegnati come membri dello stesso gruppo: {6,3,8,8,6,9,4,11,1} Avanti, inserimento sort viene applicato a questi gruppi, e quindi appaiono così: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} Nell'array generale, il le celle occupate dai gruppi rimarranno le stesse, ma il loro ordine interno cambierà, secondo l'ordine dei gruppi sopra: {1,3,4,8,6,9,8,11,6} L'array è diventato un un po' più ordinato, vero? Il prossimo intervallo sarà diviso per 2: 4/2 = 2 Abbiamo due gruppi: I — {1,4,6,8,6} II — {3,8,9,11} Nell'array generale, abbiamo : {1,3,4,8,6,9,8,11,6} Eseguiamo l'algoritmo di ordinamento dell'inserimento su entrambi i gruppi e otteniamo questo array: {1,3,4,8,6,9,6, 11, 8} Ora il nostro array è quasi ordinato. Dobbiamo eseguire un'iterazione finale dell'algoritmo: dividiamo l'intervallo per 2: 2/2 = 1. Otteniamo un gruppo composto dall'intero array: {1,3,4,8,6,9,6,11 ,8} Eseguendo l'algoritmo di ordinamento dell'inserimento su questo, otteniamo: {1,3,4,6,6,8,8,9,11} Diamo un'occhiata a come possiamo dare vita a questo ordinamento nel codice 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
}
}
}
Al momento, la performance di Shellsort non è facile da caratterizzare, poiché i risultati differiscono in diverse situazioni. Le stime sperimentali vanno da O(N 3/2 ) a O(N 7/6 ).
Ordinamento rapido
Questo è uno degli algoritmi più popolari, quindi vale la pena prestare particolare attenzione. L'essenza di questo algoritmo è che un elemento pivot viene selezionato in un elenco di elementi. Ordiniamo tutti gli altri elementi rispetto all'elemento pivot. I valori inferiori all'elemento pivot sono sulla sinistra. Valori maggiori di quelli sulla destra. Successivamente, vengono selezionati anche gli elementi pivot nelle parti destra e sinistra e accade la stessa cosa: i valori vengono ordinati rispetto a questi elementi. Quindi vengono selezionati gli elementi pivot nelle parti appena formate e così via finché non otteniamo una sequenza ordinata. La seguente implementazione Java di questo algoritmo utilizza la ricorsione:
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);
}
}
Senza dubbio, l'algoritmo quicksort è il più popolare, poiché nella maggior parte delle situazioni funziona più velocemente di altri. La sua complessità temporale è O(N*logN).
Unisci ordinamento
Anche questo tipo è popolare. È uno dei tanti algoritmi che si basa sul principio del "divide et impera". Tali algoritmi prima dividono il problema in parti gestibili (quicksort è un altro esempio di tale algoritmo). Quindi qual è il succo di questo algoritmo?
Dividere:
L'array è diviso in due parti approssimativamente della stessa dimensione. Ognuna di queste due parti è divisa in altre due, e così via fino a quando rimangono le parti indivisibili più piccole possibili. Abbiamo le parti indivisibili più piccole quando ogni array ha un elemento, cioè un array che è già ordinato.
Conquistare:
È qui che iniziamo il processo che ha dato il nome all'algoritmo: fusione. Per fare ciò, prendiamo i due array ordinati risultanti e li uniamo in uno solo. In questo caso, il più piccolo dei primi elementi dei due array viene scritto nell'array risultante. Questa operazione viene ripetuta fino a quando tutti gli elementi in questi due array non sono stati copiati. Cioè, se abbiamo due array minimi {6} e {4}, confrontiamo i loro valori e generiamo questo risultato unito: {4,6}. Se abbiamo ordinato gli array {4,6} e {2,8}, prima confrontiamo i valori 4 e 2, quindi scriviamo 2 nell'array risultante. Successivamente, verranno confrontati 4 e 8 e scriveremo 4. Infine, verranno confrontati 6 e 8. Di conseguenza, scriveremo 6 e solo dopo scriveremo 8. Di conseguenza, otteniamo il seguente array unito: {2,4,6,8}. Come apparirà questo nel codice Java? Per eseguire questo algoritmo, sarà conveniente per noi utilizzare la ricorsione:
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;
}
}
Come nell'ordinamento rapido, spostiamo il metodo ricorsivo in un metodo intermedio in modo che l'utente debba solo fornire l'array da ordinare e non debba preoccuparsi di fornire argomenti predefiniti aggiuntivi. Questo algoritmo ha somiglianze con quicksort e, prevedibilmente, la sua velocità di esecuzione è la stessa: O(N*logN).
2. Algoritmi golosi
Un algoritmo greedy è un approccio in cui vengono prese decisioni ottimali a livello locale in ogni fase, con il presupposto che anche la soluzione finale sarà ottimale. La soluzione "ottimale" sarà quella che offre il vantaggio più ovvio e immediato in ogni particolare fase/fase. Per esplorare questo algoritmo, prendiamo un problema abbastanza comune: il problema dello zaino. Fai finta per un momento di essere un ladro. Hai fatto irruzione in un negozio di notte con uno zaino (zaino). Di fronte a te ci sono diversi beni che potresti rubare. Ma allo stesso tempo, il tuo zaino ha una capacità limitata. Non può trasportare più di 30 unità di peso. Vuoi anche portare via il set di beni più prezioso che entrerà nello zaino. Come determini cosa mettere nella tua borsa? COSÌ,
Scegli l'oggetto più costoso che non è stato ancora preso.
Se entra nello zaino, mettilo dentro. In caso contrario, lascialo.
Abbiamo già rubato tutto? In caso contrario, torniamo al passaggio 1. Se sì, allora facciamo la nostra rapida fuga dal negozio, poiché abbiamo realizzato ciò per cui eravamo venuti.
Diamo un'occhiata a questo, ma in Java. Ecco come apparirà 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;
}
}
Non c'è niente di speciale qui: tre campi (nome, peso, valore) che definiscono le caratteristiche dell'articolo. Inoltre, come puoi vedere, l'interfaccia Comparable è implementata per permetterci di ordinare i nostri articoli in base al prezzo. Successivamente, esamineremo la classe Bag, che rappresenta il nostro zaino:
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 è la capacità del nostro zaino, che viene impostata quando creiamo un oggetto;
items rappresenta gli oggetti nel nostro zaino;
currentWeight , currentValue : questi campi memorizzano il peso e il valore correnti di tutti gli elementi nello zaino, che aumentiamo quando aggiungiamo un nuovo elemento nel metodo addItem.
Ad ogni modo, passiamo ora alla classe in cui si svolge tutta l'azione:
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());
}
}
Innanzitutto, creiamo un elenco di elementi e lo ordiniamo. Creiamo un oggetto borsa con una capienza di 30 unità. Successivamente, passiamo gli oggetti e l'oggetto bag al metodo fillBackpack, che riempie lo zaino secondo il nostro greedy algoritmo:
È piuttosto semplice: iniziamo a esaminare un elenco di articoli ordinati per costo e a inserirli nella borsa, se la sua capacità lo consente. Se non c'è abbastanza spazio, l'elemento verrà saltato e continueremo a scorrere il resto degli elementi fino a raggiungere la fine dell'elenco. Una volta eseguito main, ecco l'output della console che otterremo:
Il peso dello zaino è 29. Il valore totale degli oggetti nello zaino è 3700
Questo è un esempio di algoritmo greedy: ad ogni passo viene selezionata una soluzione ottimale a livello locale e, alla fine, si ottiene una soluzione ottimale a livello globale. Nel nostro caso, l'opzione migliore è l'articolo più costoso. Ma è questa la soluzione migliore? Non credi sia possibile migliorare leggermente la nostra soluzione in modo da riempire il nostro zaino di oggetti che hanno un valore complessivo ancora maggiore? Diamo un'occhiata a come questo può essere fatto.
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());
}
}
}
Qui per prima cosa calcoliamo il rapporto valore-peso per ogni articolo. Questo ci dice il valore di ciascuna unità di un dato articolo. E poi usiamo questi rapporti per ordinare i nostri articoli e aggiungerli alla nostra borsa. Eseguiamo quanto segue:
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());
Otteniamo questo output della console:
Il peso dello zaino è 29. Il costo totale degli articoli nello zaino è 4150
Un po' meglio, no? L'algoritmo greedy fa una scelta localmente ottimale ad ogni passo, sperando che anche la soluzione finale sia ottimale. Questa ipotesi non è sempre valida, ma per molti compiti gli algoritmi avidi producono una soluzione finale ottimale. La complessità temporale di questo algoritmo è O(N). Abbastanza bene, eh?
E visto che sei su questo sito, sarò così audace da presumere che tu stia scrivendo in Java. Ecco perché oggi ti suggerisco di familiarizzare con alcuni algoritmi di base e con esempi specifici di come implementarli in Java. Con "alcuni" intendo:
GO TO FULL VERSION