Cosa chiedono durante un colloquio: ripasso degli algoritmi, parte 1

Buon pomeriggio a tutti! Vari tipi di algoritmi vengono utilizzati nei progetti più spesso di quanto si possa pensare. Ad esempio, dobbiamo ordinare alcuni dati secondo determinati parametri (colonne) in modo da poterli navigare senza troppi sforzi. Non c'è quindi nulla di strano nel fatto che durante i colloqui di lavoro venga chiesto loro dell'uno o dell'altro algoritmo di base e magari venga loro assegnato il compito di implementarlo tramite codice. E dato che sei su questo sito, oserei immaginare che tu scriva in Java. Pertanto, oggi ti invito a familiarizzare con alcuni algoritmi di base ed esempi specifici della loro implementazione in Java. Per alcuni intendo:

1. Panoramica degli algoritmi di ordinamento degli array:
   • ordinamento delle bolle,
   • ordinamento della selezione,
   • ordinamento per inserimento,
   • Ordinamento della shell,
   • ordinamento veloce,
   • unisci ordinamento.
2. Algoritmo goloso.
3. Algoritmi di ricerca del percorso:
   • strisciando in profondità
   • scansione ampia.
4. L'algoritmo di trasporto è l'algoritmo di Dijkstra.

Bene, senza ulteriori indugi, mettiamoci al lavoro.

1. Panoramica degli algoritmi di ordinamento

Ordinamento delle bolle

Questo algoritmo di ordinamento è noto principalmente per la sua semplicità, ma allo stesso tempo ha una delle velocità di esecuzione più basse. Ad esempio, considera l'ordinamento a bolle per i numeri in ordine crescente. Immaginiamo una catena di numeri posizionati casualmente per la quale verranno eseguiti i seguenti passaggi, partendo dall'inizio della catena:

• confrontare due numeri;
• se il numero a sinistra è maggiore, scambiali;
• spostarsi di una posizione a destra.

Dopo aver attraversato l'intera catena ed eseguito questi passaggi, scopriremo che il numero più grande si trova alla fine della nostra serie di numeri. Successivamente, viene eseguito esattamente lo stesso passaggio lungo la catena, seguendo i passaggi sopra descritti. Ma questa volta non includeremo l'ultimo elemento della lista, poiché è il più grande ed è già all'ultimo posto, come dovrebbe essere. Ancora una volta, otterremo l'ultimo elemento alla fine della nostra serie di numeri in questione. Di conseguenza, i due numeri più grandi saranno già al loro posto. E ancora si inizia il passaggio lungo la catena, escludendo gli elementi già presenti, fino a quando tutti gli elementi sono nell'ordine richiesto. Diamo un'occhiata all'implementazione del 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'è nulla di complicato qui, e tutto sembra essere fantastico, se non per un "ma"... Il Bubble sort è molto, molto lento, con una complessità temporale di O(N²) , poiché abbiamo annidato loop. Il passaggio esterno attraverso gli elementi viene eseguito in N volte, anche quello interno è N volte e di conseguenza otteniamo N*N , N² iterazioni. Puoi studiare questo tipo di ordinamento in modo più dettagliato in questo articolo .

Ordinamento per selezione

Questo algoritmo è simile al bubble sort, ma funziona un po' più velocemente. Ancora una volta, come esempio, prendiamo una serie di numeri che vogliamo disporre in ordine crescente. L'essenza dell'algoritmo è esaminare in sequenza tutti i numeri e selezionare l'elemento più piccolo, che prendiamo e scambiamo di posto con l'elemento più a sinistra (elemento 0). Qui otteniamo una situazione simile al bubble sort, ma in questo caso l'elemento ordinato sarà quello più piccolo. Pertanto, il successivo passaggio attraverso gli elementi inizierà con l'elemento con indice 1. Anche in questo caso, questi passaggi verranno ripetuti finché tutti gli elementi non saranno 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++) { // внешний обычный  цикл
           int min = i;

           for (int j = i + 1; j < array.length; j++) { // обычный цикл, но с отчетом с сортированных чисел
               if (array[j] < array[min]) {
                   min = j;
               }
           }
           int temp = array[i];     // вставка отссортиованного числа, в положеную ему ячейку
           array[i] = array[min];
           array[min] = temp;
       }
   }
}

Questo algoritmo è superiore al bubble sort, perché qui il numero di permutazioni necessarie viene ridotto da O(N²) a O(N): non spingiamo un elemento attraverso l'intero elenco, ma tuttavia il numero di confronti rimane O(N² ) . Per chi volesse saperne di più su questo algoritmo, consiglio questo materiale .

Ordinamento di inserimento

Ancora una volta, come esempio, prendiamo una serie di numeri che vogliamo disporre in ordine crescente. Questo algoritmo consiste nel posizionare un marcatore, alla sinistra del quale gli elementi saranno già parzialmente ordinati tra loro. Ad ogni passo dell'algoritmo, uno degli elementi verrà selezionato e posizionato nella posizione desiderata nella sequenza già ordinata. Quindi la parte ordinata continuerà a crescere finché tutti gli elementi non saranno stati esaminati. Potresti chiederti: dove posso prendere quella parte degli elementi che sono già ordinati e dopo i quali devi mettere un pennarello? Ma l’array del primo elemento è già ordinato, no? 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 - разделяющий маркер
           int temp = array[i]; // делаем копию помеченного element
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // пока не будет найден меньший элемент
               array[j] = array[j - 1]; // сдвигаем элементы вправо
               --j;
           }
           array[j] = temp;   // вставляем отмеченный элемент, в положеное ему место
       }
   }
}

Questo tipo di ordinamento è superiore a quelli descritti sopra, perché nonostante il tempo di esecuzione sia lo stesso - O(N²) , questo algoritmo funziona due volte più velocemente del bubble sort e leggermente più velocemente dell'ordinamento per selezione. Leggi di più qui .

Ordinamento della shell

Questo ordinamento, per sua natura, è un ordinamento di inserimento modificato. Di cosa sto parlando? Andiamo con ordine. Viene selezionato un passaggio e ci sono molti approcci a questa scelta. Non entreremo in questo argomento in troppi dettagli. Dividiamo il nostro array a metà e otteniamo un certo numero: questo sarà il nostro passaggio. Quindi, se abbiamo 9 elementi nell'array, il nostro passo sarà 9/2 = 4.5 . Scartiamo la parte frazionaria e otteniamo 4 , poiché gli indici degli array sono solo numeri interi. Con questo passaggio creeremo connessioni per i nostri gruppi. Se un elemento ha indice 0, allora l'indice dell'elemento successivo nel suo gruppo è 0+4 , cioè 4 . Il terzo elemento avrà indice 4+4 , il quarto avrà indice 8+4 e così via. Per il secondo gruppo, il primo elemento sarà 1,5,9…. Nel terzo e quarto gruppo le cose saranno esattamente le stesse. Di conseguenza, dalla matrice di numeri {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 per noi sono contrassegnati come membri dello stesso gruppo: { 6 , 3 , 8 , 8 , 6 , 9 , 4 , 11 , 1 } Inoltre all'interno di questi gruppi si verifica l'ordinamento di inserimento , dopodiché i gruppi appariranno come: I - {1,6,6} II - {3,9} III - {4,8} IV - {8 ,11} Nell'array generale, le celle occupate dai gruppi rimarranno le stesse, ma l'ordine al loro interno cambierà, secondo l'ordine dei gruppi sopra: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } L'array è un po' più ordinato, non è vero? Il passaggio successivo sarà diviso per 2: 4/2 = 2 Abbiamo due gruppi: I - {1,4,6,8,6} II - {3,8,9,11} B array generale: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Esaminiamo entrambi i gruppi utilizzando l'algoritmo di ordinamento per inserimento e otteniamo un array: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8} Ora il nostro array è quasi ordinato. Rimane l'ultima iterazione dell'algoritmo: dividiamo il passo per 2: 2/2 = 1. Otteniamo un gruppo, l'intero array: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } Per che eseguiamo attraverso l'algoritmo di ordinamento per inserimento e otteniamo: { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } Vediamo come possiamo visualizzare 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 = 0; numberOfGroup < length - step; numberOfGroup++) {// проходим по всем нашим группам
              int j = numberOfGroup;
               while (j >= 0 && array[j] > array[j + step]) {//sorting вставкой внутри группы
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // уменьшаем наш шаг
       }
   }
}

Al momento, l'efficacia dello Shell sorting non è realmente comprovata, poiché i risultati differiscono a seconda delle situazioni. Le stime ottenute dagli esperimenti vanno da O(N ^3/2 ) a O(N ^7/6 ) .

Ordinamento rapido

Questo è uno degli algoritmi più popolari e quindi vale la pena prestare particolare attenzione. L'essenza di questo algoritmo è che un elemento pivot viene selezionato da un elenco di elementi, essenzialmente qualsiasi elemento rispetto al quale devono essere ordinati i valori rimanenti. Valori inferiori a sinistra, valori maggiori a destra. Successivamente, anche le parti destra e sinistra vengono selezionate dall'elemento di supporto e accade la stessa cosa: i valori vengono ordinati rispetto a questi elementi, quindi gli elementi di supporto vengono selezionati dalle parti risultanti - e così via fino ad ottenere un risultato ordinato riga. Questo algoritmo in Java è implementato utilizzando 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 выхода из рекурсии,  если длина массива равна 0
           return;

       if (min >= max) //выходим, так How нечего уже делить
           return;


       int middle = min + (max - min) / 2;  // выбираем середину
       int middleElement = array[middle];


       int i = min, j = max;
       while (i <= j) {  // относительно element middle определяемменьшие элементы слева, большие справа
           while (array[i] < middleElement) {
               i++;
           }
           while (array[j] > middleElement) {
               j--;
           }

           if (i <= j) {      //меняем местами
               int temp = array[i];
               array[i] = array[j];
               array[j] = temp;
               i++;
               j--;
           }
       }

       if (min < j) // запускаем рекурсию с elementми меньшими чем middle
           recursionFastSort(array, min, j);

       if (max > i)// запускаем рекурсию с elementми большими чем middle
           recursionFastSort(array, i, max);
   }
}

Senza dubbio, l'algoritmo Quicksort è considerato il più popolare, poiché nella maggior parte delle situazioni viene eseguito più velocemente di altri, in tempo O(N*logN) .

Unisci ordinamento

Anche questo ordinamento è popolare. Si riferisce a uno dei tipi di algoritmi che funzionano secondo il principio del "divide et impera": in essi prima dividiamo i compiti in parti minime ( anche l'ordinamento rapido è un rappresentante di tali algoritmi ). Allora, qual è l'essenza di questo algoritmo?

Condividere:

La matrice è divisa in due parti approssimativamente della stessa dimensione, ciascuna di queste due parti è divisa in altre due e così via fino a quando rimangono le parti indivisibili più piccole. Le parti meno indivisibili si verificano quando ogni array ha un elemento, il che significa che tale array viene automaticamente considerato ordinato.

Conquistare:

È qui che inizia il processo che dà il nome all'algoritmo: fusione . Per fare ciò, prendi i due array ordinati risultanti e uniscili in uno solo. In questo caso, il più piccolo dei primi elementi dei due array viene scritto nell'array risultante e questa operazione viene ripetuta finché non ci sono più elementi nei due array. Cioè, se abbiamo due array minimi {6} e {4} , i loro valori verranno confrontati e il risultato sarà scritto: {4,6} . Se sono presenti array ordinati {4,6} e {2,8} , prima verranno confrontati i valori 4 e 2 , di cui 2 verrà scritto nell'array risultante. Successivamente verranno confrontati 4 e 8 , scritto 4 e alla fine verranno confrontati 6 e 8 . Di conseguenza, verrà scritto 6 e solo dopo - 8. Di conseguenza, otterremo l'array risultante: {2,4,6,8} . Come apparirà nel codice Java? Per elaborare questo algoritmo, ci converrà 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);// массив для сортировки
       int[] bufferArr = new int[array1.length];// буферный массив
       return recurtionMergeSort(sortArr, bufferArr, 0, array1.length);
   }


   public static int[] recurtionMergeSort(int[] sortArr, int[] bufferArr,
                                          int startIndex, int endIndex) {
       if (startIndex >= endIndex - 1) {// выход из массива, когда в рассматриваемом промежутке массива, только один элемент
           return sortArr;
       }

       // запускаем рекурсию, чтобы получить два отсортированных массива:
       int middle = startIndex + (endIndex - startIndex) / 2;
       int[] firstSortArr = recurtionMergeSort(sortArr, bufferArr, startIndex, middle);
       int[] secondSortArr = recurtionMergeSort(sortArr, bufferArr, middle, endIndex);

       // Слияние отсортированных массивов:
       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 uno intermedio in modo che l'utente non debba preoccuparsi di impostare argomenti predefiniti aggiuntivi, ma possa semplicemente specificare l'array che deve essere ordinato. Poiché questo algoritmo è simile alla cancellazione più rapida, la sua velocità di esecuzione è la stessa: O(N*logN) .

2. Algoritmi golosi

Un algoritmo greedy è un approccio che prende decisioni ottimali a livello locale in ogni fase e presuppone che anche la soluzione finale sarà ottimale. La soluzione “ottimale” è quella che offre il beneficio più evidente e immediato in un determinato passaggio/fase. Per considerare questo algoritmo, sceglieremo un problema abbastanza comune: relativo allo zaino. Facciamo finta per un secondo che tu sia un ladro. Di notte sei entrato in un negozio con uno zaino e davanti a te c'è una serie di merci che puoi rubare. Allo stesso tempo, la capacità dello zaino è limitata: non più di 30 unità convenzionali. Allo stesso tempo, vuoi portare con te un set di merci del valore massimo che possa entrare nel tuo zaino. Come decidi cosa inserire? Quindi, l'algoritmo greedy per il problema dello zaino consiste nei seguenti passaggi (assumiamo che tutti gli oggetti entrino nello zaino):

1. Scegli l'oggetto più costoso tra quelli non ancora toccati.
2. Se entra nello zaino, mettilo lì, altrimenti saltalo.
3. Hai messo in ordine tutti gli elementi? In caso contrario, torniamo al punto 1, in caso affermativo, scappiamo dal negozio, poiché il nostro obiettivo qui è completato.

Diamo un'occhiata a questo, ma in Java. Ecco come apparirà la classe Item:

public class Item implements Comparable<Item> {
   private String name;
   private int weight;
   private int cost;

   public Item(String name, int weight, int cost) {
       this.name = name;
       this.weight = weight;
       this.cost = cost;
   }

   public String getName() {
       return name;
   }

   public int getWeight() {
       return weight;
   }

   public int getCost() {
       return cost;
   }

   @Override
   public int compareTo(Item o) {
       return this.cost > o.cost ? -1 : 1;
   }
}

Non c'è niente di speciale qui: tre campi - nome , peso , costo - per specificare le caratteristiche dell'articolo. Inoltre, come puoi vedere, qui è implementata l' interfaccia Comparabile in modo che possiamo ordinare i nostri articoli in base al prezzo. Successivamente esaminiamo la classe del nostro zaino: Borsa :

public class Bag {
   private final int maxWeight;
   private List<Item> items;
   private int currentWeight;
   private int currentCost;

   public Bag(int maxWeight) {
       this.maxWeight = maxWeight;
       items = new ArrayList<>();
       currentCost = 0;
   }

   public int getMaxWeight() {
       return maxWeight;
   }

   public int getCurrentCost() {
       return currentCost;
   }

   public int getCurrentWeight() {
       return currentWeight;
   }

   public void addItem(Item item) {
       items.add(item);
       currentWeight += item.getWeight();
       currentCost += item.getCost();
   }
}

• maxWeight è la capacità del nostro zaino, che viene impostata in fase di creazione dell'oggetto;
• oggetti : oggetti nello zaino;
• currentWeight , currentCost - il peso e il costo attuali di tutte le cose nello zaino, che aumentiamo quando aggiungiamo un nuovo articolo nel metodo addItem .

In realtà, andiamo in classe, dove si svolge tutta l'azione:

public class Solution {

   public static void main(String[] args) {
       List<Item> items = new ArrayList<>();
       items.add(new Item("гитара",7, 800));
       items.add(new Item("утюг",6, 500));
       items.add(new Item("чайник",3, 300));
       items.add(new Item("лампа",4, 500));
       items.add(new Item("телевизор",15, 2000));
       items.add(new Item("ваза",2, 450));
       items.add(new Item("миксер",1, 400));
       items.add(new Item("блендер",3, 200));

       Collections.sort(items);

       Bag firstBag = new Bag(30);

       fillBackpack(firstBag, items);

       System.out.println("Вес рюкзака состовляет - " + firstBag.getCurrentWeight() +
               ", общая стоимость вещей в рюкзаке - " + firstBag.getCurrentCost());
}
}

Per prima cosa creiamo un elenco di elementi e lo ordiniamo. Crea un oggetto borsa con una capacità di 30 unità. Successivamente inviamo gli elementi e l'oggetto bag al metodo fillBackpack , in cui, appunto, lo zaino viene riempito utilizzando un algoritmo greedy:

public static void fillBackpack(Bag bag, List<Item> items) {
   for (Item item : items) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + item.getWeight()) {
            bag.addItem(item);
       }
   }
}

Tutto è estremamente semplice: iniziamo a scorrere l'elenco degli articoli ordinati per costo e li mettiamo in una borsa, se la capacità lo consente. Se non lo consente, l'elemento verrà saltato e il passaggio attraverso gli elementi rimanenti continuerà fino alla fine della lista. Eseguendo main, otteniamo il seguente output sulla console: In realtà, questo è un esempio di algoritmo greedy: ad ogni passaggio viene selezionata una soluzione ottima a livello locale e alla fine si ottiene una soluzione ottima a livello globale. Nel nostro caso, l’opzione migliore è l’articolo più costoso. Ma è questa la soluzione migliore? Non pensi che potremmo modernizzare un po' la nostra soluzione in modo da poter equipaggiare uno zaino con un costo totale più elevato? Diamo un'occhiata a come è possibile farlo:

public static void effectiveFillBackpack(Bag bag, List<Item> items) {
   Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
   for (Item item : items) {
       sortByRatio.put((double)item.getCost() / item.getWeight(), item);
   }

   for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
           bag.addItem(entry.getValue());
       }
   }
}

Qui calcoliamo innanzitutto il rapporto peso-prezzo per ciascun articolo. Per così dire, quanto costa un'unità di un determinato articolo? E in base a questi valori ordiniamo i nostri articoli e li aggiungiamo alla nostra borsa. Corriamo:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

System.out.println("Вес рюкзака составляет - " + secondBag.getCurrentWeight() +
       ", общая стоимость вещей в рюкзаке - " + secondBag.getCurrentCost());

Riceviamo l'output sulla console: Un po' meglio, no? Un algoritmo avido fa una scelta localmente ottimale ad ogni passo con l’aspettativa che anche la soluzione finale sarà ottimale. Ciò non è sempre giustificato, ma per molti problemi gli algoritmi greedy forniscono un ottimo. La complessità temporale di questo algoritmo è O(N) , il che è abbastanza buono, giusto? Bene, con questo si conclude la prima parte di questo articolo. Se sei interessato al seguito di questo articolo, che parlerà dei grafici e degli algoritmi ad essi correlati, puoi trovarlo qui .