L'ordinamento è una delle operazioni di base che eseguiamo sugli oggetti. Anche durante l'infanzia, ai bambini viene insegnato a ordinare mentre sviluppano le loro capacità di pensiero. Computer e software non fanno eccezione. Ci sono una grande varietà di algoritmi di ordinamento in Java . Ti consiglio di verificare cosa sono e come funzionano. E se un giorno ti chiedessero di uno di loro durante un colloquio?
introduzione
L'ordinamento degli elementi è una delle categorie di algoritmi che uno sviluppatore deve conoscere. Se una volta l'informatica non veniva presa sul serio quando andavo a scuola, gli studenti di oggi devono essere in grado di implementare e comprendere gli algoritmi di ordinamento. Gli algoritmi di base, i più semplici, sono implementati utilizzando un ciclo for . Naturalmente, per ordinare una raccolta di elementi, come un array, devi in qualche modo passare attraverso la raccolta. Per esempio:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
Cosa si può dire di questo segmento di codice? Abbiamo un ciclo in cui cambiamo l'indice ( int i) da 0 all'ultimo elemento dell'array. In effetti, stiamo semplicemente prendendo ogni elemento dell'array e stampandone il contenuto. Maggiore è il numero di elementi nell'array, più tempo impiegherà il codice a terminare. Cioè, se nè il numero di elementi, quando n = 10il programma impiegherà il doppio del tempo per essere eseguito rispetto a quando n = 5. Se il nostro programma ha un solo ciclo, il tempo di esecuzione cresce linearmente: più elementi ci sono, più lungo è il tempo di esecuzione. Si scopre che l'algoritmo sopra funziona in tempo lineare (una funzione lineare di n). In tali casi, diciamo che la complessità dell'algoritmo è "O(n)". Questa notazione è anche chiamata "grande O" o "comportamento asintotico". Ma puoi solo ricordare "
Il più semplice algoritmo di ordinamento (bubble sort)
Supponiamo di avere un array e di poterlo iterare. Grande. Ora proviamo a ordinarlo in ordine crescente. Cosa significa questo? Significa che dati due elementi (ad esempio, a = 6, b = 5), dobbiamo riordinare ae bif aè maggiore di b(if a > b). Cosa significa questo quando utilizziamo un indice per lavorare con una raccolta (come nel caso di un array)? Significa che se l'elemento con indice a è maggiore dell'elemento con indice b( array[a] > array[b]), allora gli elementi devono essere scambiati. Ci sono diversi modi per cambiare posto. Ma useremo una tecnica semplice, comprensibile e facile da ricordare:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Ora possiamo scrivere quanto segue:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
Come puoi vedere, gli elementi sono stati davvero scambiati. Abbiamo iniziato con index 1, perché se l'array ha un solo elemento, l'espressione array[i] < array[i-1]non è valida per index 0. Fare questo ci protegge anche dai casi in cui l'array non ha elementi o solo un elemento, e migliora l'aspetto del codice. Ma l'array risultante non è ancora ordinato, perché un passaggio non è sufficiente per eseguire l'ordinamento. Dovremo aggiungere un altro ciclo in cui eseguiremo i passaggi ancora e ancora finché non otteniamo un array ordinato:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
Quindi abbiamo terminato il nostro primo algoritmo di ordinamento. Ripetiamo il ciclo esterno ( while) finché non decidiamo che non sono necessarie altre iterazioni. Per impostazione predefinita, prima di ogni nuova iterazione, assumiamo che il nostro array sia ordinato e non abbiamo più bisogno di eseguire il ciclo. Di conseguenza, ci spostiamo in sequenza attraverso gli elementi e controlliamo questa ipotesi. Ma se gli elementi non sono in ordine, li scambiamo e comprendiamo che ora non abbiamo alcuna garanzia che gli elementi siano nell'ordine corretto. Ciò significa che dobbiamo eseguire un'altra iterazione. Ad esempio, supponiamo di avere [3, 5, 2]. 5è più di 3... va tutto bene. Ma 2è inferiore a 5. Tuttavia, [3, 2, 5]richiede un altro passaggio, poiché3 > 2e devono essere scambiati. Poiché stiamo usando un ciclo all'interno di un ciclo, la complessità del nostro algoritmo aumenta. Dati ngli elementi, diventa n * n, cioè O(n^2). Questa si chiama complessità quadratica. In generale, non possiamo sapere esattamente quante iterazioni saranno necessarie. L'espressione di complessità di un algoritmo mostra come la complessità aumenta nel caso peggiore. Cioè, indica quanto aumenterà il tempo di esecuzione al nvariare del numero di elementi. Bubble sort è uno degli algoritmi di ordinamento più semplici e inefficienti. A volte è anche chiamato "tipo stupido". Materiale su questo argomento:
Un altro algoritmo di ordinamento è l'ordinamento per selezione. Ha anche una complessità quadratica, ma ne parleremo più avanti. Quindi l'idea è semplice. Ad ogni passaggio, selezioniamo l'elemento più piccolo e lo spostiamo all'inizio. Inoltre, ogni passaggio inizia un passo a destra. In altre parole, il primo passaggio parte dall'elemento zero, il secondo dal primo, ecc. Avrà questo aspetto:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
Questo ordinamento è instabile, perché elementi identici (in termini di qualunque caratteristica stiamo usando per ordinare gli elementi) possono cambiare le loro posizioni relative. C'è un buon esempio nell'articolo di Wikipedia su selection sort . Materiale su questo argomento:
Anche l'ordinamento per inserzione ha una complessità quadratica, dato che abbiamo di nuovo un ciclo all'interno di un ciclo. Cosa rende diverso l'ordinamento per inserzione? Questo algoritmo di ordinamento è "stabile". Ciò significa che elementi identici non cambieranno il loro ordine relativo. Ancora una volta, intendiamo identici in termini di caratteristiche in base alle quali stiamo ordinando.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
Tipo di navetta
Esiste un altro semplice algoritmo di ordinamento: shuttle sort. Questo è anche noto come tipo di bolla bidirezionale o tipo di shaker per cocktail. Questi nomi alternativi ci dicono che l'ordinamento dello shuttle non riguarda lo space shuttle. Si tratta di qualcosa che si muove avanti e indietro. Ora puoi pensarci quando pensi a questo algoritmo. Qual è l'essenza dell'algoritmo? L'essenza dell'algoritmo è che iteriamo da sinistra a destra, scambiando elementi e controllando se qualcuno degli elementi rimanenti nell'altra direzione deve essere scambiato.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
Un altro semplice algoritmo di ordinamento è lo shell sort. L'essenza è simile al bubble sort, ma in ogni iterazione abbiamo un divario diverso tra gli elementi confrontati. Viene tagliato a metà ad ogni iterazione. Ecco un'implementazione:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
Oltre a questi semplici algoritmi di ordinamento, esistono anche algoritmi di ordinamento più complicati. Ad esempio, unisci ordinamento. Ci sono due cose da notare. Innanzitutto, la ricorsione viene in nostro soccorso qui. In secondo luogo, la complessità dell'algoritmo non è più quadratica, come siamo abituati. La complessità di questo algoritmo è logaritmica. Questo è scritto come O(n log n). Quindi implementiamolo. Innanzitutto, scriveremo una chiamata ricorsiva al metodo sort:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
Ora, aggiungiamo l'azione principale alla nostra implementazione. Ecco il nostro super metodo:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
Possiamo eseguire il nostro esempio chiamandomergeSort(array, 0, array.length-1). Come puoi vedere, il processo si riduce all'accettazione di un array di input insieme alle indicazioni dell'inizio e della fine della sezione che deve essere ordinata. Quando inizia l'ordinamento, questi sono l'inizio e la fine dell'array. Quindi calcoliamo il delimitatore, che è l'indice in cui divideremo l'array. Se l'array può essere diviso in 2 parti, chiamiamo il metodo sort in modo ricorsivo per le due metà dell'array. Prepariamo un buffer ausiliario dove inseriremo la sezione ordinata. Successivamente, imposta l'indice all'inizio della sezione da ordinare e inizia a scorrere ogni elemento del buffer vuoto, riempiendolo con gli elementi più piccoli. Se l'elemento puntato dall'indice è minore dell'elemento puntato dal delimitatore, inseriamo l'elemento nel buffer e spostiamo l'indice. Altrimenti, posizioniamo l'elemento indicato dal delimitatore nel buffer e spostiamo il delimitatore. Non appena il delimitatore supera i limiti della sezione ordinata o riempiamo l'intero array, l'intervallo specificato viene considerato ordinato.Materiale su questo argomento:
Conteggio dell'ordinamento e dell'ordinamento digitale
Un altro interessante algoritmo di ordinamento è il conteggio dell'ordinamento. La complessità algoritmica qui è O(n+k), dove nè il numero di elementi ed kè il valore massimo di un elemento. Questo algoritmo ha un difetto: dobbiamo conoscere i valori minimo e massimo nell'array. Ecco un esempio dell'ordinamento di conteggio:
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
Puoi capire che è molto scomodo quando dobbiamo conoscere in anticipo i valori minimo e massimo. E qui abbiamo un altro algoritmo: radix sort. Presenterò solo l'algoritmo qui visivamente. Vedere i materiali supplementari per l'implementazione: Materiali:
Bene, è il momento del dessert: l'ordinamento rapido, uno degli algoritmi di ordinamento più famosi. Ha complessità logaritmica: O(n log n). Questo algoritmo di ordinamento è stato sviluppato da Tony Hoare. È interessante notare che l'ha inventato mentre viveva in Unione Sovietica, dove ha studiato traduzione automatica all'Università di Mosca e ha sviluppato un frasario russo-inglese. Inoltre, Java utilizza una versione più complessa di questo algoritmo in Arrays.sort. Che dire Collections.sort? Perché non dare un'occhiata a come vengono ordinate le cose "sotto il cofano"? Ecco il codice:
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
Questa è tutta roba molto spaventosa, quindi approfondiamola. Per input array ( int[]source), creiamo due marcatori: left ( L) e right ( R). Durante la prima chiamata al metodo, corrispondono all'inizio e alla fine dell'array. Quindi identifichiamo l'elemento pivot, che è giustamente chiamato pivot. Successivamente, il nostro compito è spostare i valori più piccoli pivota sinistra di pivote quelli più grandi a destra. Per fare ciò, spostiamo prima il Lmarcatore finché non troviamo un valore maggiore di pivot. Se non viene trovato alcun valore inferiore, allora
L diventa uguale a
pivot. Quindi spostiamo il
Rmarcatore finché non troviamo un valore inferiore a
pivot. Se non viene trovato alcun valore maggiore,
Rdiventa uguale a
pivot. Successivamente, se il
Lmarcatore è prima del
Rmarcatore o coincide con esso, proviamo a scambiare gli elementi se l'
Lelemento è inferiore all'elemento
R. Poi ci spostiamo
La destra di 1, e ci spostiamo
Ra sinistra di 1. Quando il
Lmarcatore si sposta oltre il
Rmarcatore, significa che lo scambio è completo: i valori più piccoli sono a sinistra di
pivot, i valori più grandi sono a destra di
pivot. Successivamente, chiamiamo lo stesso metodo di ordinamento in modo ricorsivo sui sottoarray, dall'inizio della sezione da ordinare al marcatore destro e dal marcatore sinistro alla fine della sezione da ordinare. Perché dall'inizio al marcatore giusto? Perché alla fine di un'iterazione, si scopre che il marcatore destro si sposta abbastanza da diventare il confine della parte sinistra. Questo algoritmo è più complesso del semplice ordinamento, quindi è meglio abbozzarlo. Prendi un foglio bianco e scrivi: 4 2 6 7 3. Poi scrivi
pivotal centro, cioè sotto il numero 6. Cerchialo. Sotto il 4 scrivi
L, e sotto il 3 scrivi
R. 4 meno di 6, 2 meno di 6. Finiamo per spostarci
Lnella
pivotposizione, perché
Lnon possiamo andare oltre
pivot, secondo la condizione. Scrivi di nuovo 4 2 6 7 3. Cerchia 6 (
pivot) e mettici
Lsotto. Ora sposta il
Rmarcatore. 3 è minore di 6, quindi metti il
Rmarcatore su 3. Poiché 3 è minore di 6 (
pivot), eseguiamo un
swap. Scrivi il risultato: 4 2 3 7 6. Cerchia 6, perché è ancora il
pivot. Il
Lmarcatore è sul 3. Il
Rmarcatore è sul 6. Ricorda che spostiamo i marcatori finché
Lnon si sposta oltre
R. Passa
Lal numero successivo. Qui vorrei esplorare due possibilità: 1) il caso in cui il penultimo numero è 7 e 2) il caso in cui è 1, non 7.
Se il penultimo numero è 1: sposta il
Lmarcatore su 1, perché possiamo spostarci
Lfinché il
Lindicatore indica un numero inferiore a
pivot. Ma non possiamo allontanarci
Rda 6, perché possiamo spostare R solo se l'
Rindicatore indica un numero maggiore di
pivot. Non eseguiamo un
swap, perché 1 è minore di 6. Scrivi la situazione attuale: 4 2 3 1 6. Cerchia 6 (
pivot).
Lsi sposta
pivote smette di muoversi.
Rnon si muove. Non eseguiamo uno scambio. Shift
Le
Rdi una posizione. Scrivi il
Rmarcatore sotto 1. Il
Lmarcatore è fuori limite. Perché
Lè fuori dai limiti, non facciamo nulla. Ma scriviamo di nuovo 4 2 3 1, perché questo è il nostro lato sinistro, che è minore di
pivot(6). Seleziona il nuovo
pivote ricomincia tutto :)
Se il penultimo numero è 7:Sposta il
Lmarcatore su 7. Non possiamo spostare il marcatore destro, perché punta già al perno. 7 è maggiore di
pivot, quindi eseguiamo a
swap. Scrivi il risultato: 4 2 3 6 7. Cerchia 6, perché è il
pivot. Il
Lmarcatore è ora spostato su 7 e il
Rmarcatore su 3. Non ha senso ordinare la parte dalla
Lfine, perché c'è solo 1 elemento. Tuttavia, inviamo la parte da 4 al
Rmarcatore per l'ordinamento. Scegliamo a
pivote ricominciamo tutto da capo :) A prima vista, può sembrare che se aggiungi molti valori uguali a
pivot, quindi interromperai l'algoritmo. Ma non è così. Puoi inventare combinazioni complicate e sulla carta convincerti che tutto è corretto e meravigliarti che azioni così semplici implementino un meccanismo di ordinamento così affidabile. L'unico aspetto negativo è che questo algoritmo di ordinamento non è stabile. Perché uno scambio può cambiare l'ordine relativo di elementi identici se uno di essi viene incontrato prima
pivotche l'altro elemento venga scambiato nella parte prima di
pivot.
La linea di fondo
Sopra, abbiamo esaminato un insieme di algoritmi di ordinamento "da gentiluomini" implementati in Java. Gli algoritmi sono generalmente utili, sia da una prospettiva applicata che in termini di apprendimento del pensiero. Alcuni sono più semplici, altri più complicati. Le persone intelligenti hanno difeso le loro dissertazioni per alcuni. Per altri, hanno scritto libri molto spessi. Spero che i materiali supplementari ti aiutino a imparare ancora di più, poiché questo articolo è solo una panoramica che si è già rivelata pesante. E il suo scopo è fornire una piccola introduzione. Puoi anche trovare un'introduzione agli algoritmi leggendo
"Grokking Algorithms ". Mi piace anche la playlist di Jack Brown:
AQA Decision 1 1.01 Tracing an Algorithm . Per divertimento, puoi vedere le visualizzazioni dell'algoritmo durante
l'ordinamento.visualgo.net .
GO TO FULL VERSION