Share
In questa sezione, esamineremo cinque algoritmi utilizzati per ordinare i dati in un array. Inizieremo con un algoritmo ingenuo, ordinamento di bolle e termineremo con l'algoritmo di ordinamento generale più comune, l'ordinamento rapido.
Con ciascun algoritmo spiegherò come è fatto l'ordinamento e fornirò anche informazioni sulla complessità migliore, media e peggiore sia per le prestazioni che per l'utilizzo della memoria.
Per mantenere il codice dell'algoritmo di ordinamento un po 'più facile da leggere, un comune Scambiare il metodo verrà utilizzato da qualsiasi algoritmo di ordinamento che deve scambiare i valori in un array per indice.
void Swap (T [] items, int left, int right) if (left! = right) T temp = items [left]; items [left] = items [right]; articoli [destra] = temp;
| Comportamento | Ordina l'array di input usando l'algoritmo bubble sort. | ||
| Complessità | Caso migliore | Caso medio | Caso peggiore |
| Tempo | Sopra) | Sopra2) | Sopra2) |
| Spazio | O (1) | O (1) | O (1) |
Bubble sort è un algoritmo di ordinamento ingenuo che opera eseguendo più passaggi attraverso l'array, ogni volta spostando il valore più grande non ordinato a destra (fine) dell'array.
Si consideri la seguente matrice di numeri interi non ordinata:
Array di numeri interi non ordinati Al primo passaggio attraverso l'array, vengono confrontati i valori tre e sette. Poiché sette è maggiore di tre, non viene eseguito alcun swap. Successivamente, sette e quattro vengono confrontati. Sette è maggiore di quattro, quindi i valori vengono scambiati, spostando così i sette, un passo più vicino alla fine dell'array. L'array ora si presenta così:
Il 4 e il 7 hanno posizioni scambiate Questo processo viene ripetuto e i sette finiscono per essere confrontati con gli otto, che è maggiore, quindi non è possibile eseguire lo scambio e il passaggio termina alla fine dell'array. Alla fine del primo passaggio, la matrice si presenta così:
La matrice alla fine del passaggio 1 Poiché è stato eseguito almeno uno scambio, verrà eseguito un altro passaggio. Dopo il secondo passaggio, il sei si è spostato in posizione.
La matrice alla fine del passaggio 2 Di nuovo, poiché è stato eseguito almeno uno scambio, viene eseguita un'altra passata.
Il passaggio successivo, tuttavia, rileva che non sono necessari swap perché tutti gli articoli sono ordinati. Poiché non sono stati eseguiti swap, è noto che l'array è ordinato e l'algoritmo di ordinamento è completo.
pubblico vuoto Sort (T [] items) bool swap; do swapped = false; per (int i = 1; i < items.Length; i++) if (items[i - 1].CompareTo(items[i]) > 0) Swap (articoli, i - 1, i); scambiato = vero; while (scambiato! = falso);
| Comportamento | Ordina l'array di input utilizzando l'algoritmo di ordinamento per inserimento. | ||
| Complessità | Caso migliore | Caso medio | Caso peggiore |
| Tempo | Sopra) | Sopra2) | Sopra2) |
| Spazio | O (1) | O (1) | O (1) |
L'ordinamento di inserimento funziona eseguendo un singolo passaggio attraverso l'array e inserendo il valore corrente nella parte già ordinata (iniziale) dell'array. Dopo che ogni indice è stato elaborato, è noto che tutto ciò che è stato rilevato fino ad ora è ordinato e tutto ciò che segue è sconosciuto.
Aspetta cosa?
Il concetto importante è che l'ordinamento di inserimento funziona ordinando gli elementi così come vengono incontrati. Poiché elabora l'array da sinistra a destra, sappiamo che tutto a sinistra dell'indice corrente è ordinato. Questo grafico mostra come l'array viene ordinato quando viene rilevato ogni indice:
Un array in fase di elaborazione per tipo di inserimento Man mano che l'elaborazione continua, la matrice diventa sempre più ordinata finché non viene completamente ordinata.
Diamo un'occhiata ad un esempio concreto. Di seguito è riportato un array non ordinato che verrà ordinato utilizzando l'ordinamento per inserimento.
Array di numeri interi non ordinati Quando inizia il processo di ordinamento, l'algoritmo di ordinamento inizia dall'indice zero con il valore tre. Poiché non ci sono valori che precedono questo, l'array fino a includere lo zero dell'indice è noto per essere ordinato.
L'algoritmo passa quindi al valore sette. Poiché sette è maggiore di qualsiasi cosa nell'intervallo ordinato noto (che attualmente include solo tre), i valori fino a e inclusi sette sono noti per essere ordinati.
A questo punto, gli array array 0-1 sono noti per essere ordinati e 2-n si trovano in uno stato sconosciuto.
Successivamente viene verificato il valore all'indice due (quattro). Poiché quattro sono meno di sette, è noto che quattro devono essere spostati nella giusta posizione nell'area dell'array ordinato. La domanda ora è a quale indice nell'array ordinato deve essere inserito il valore. Il metodo per fare questo è il FindInsertionIndex mostrato nel codice di esempio. Questo metodo confronta il valore da inserire (quattro) con i valori nell'intervallo ordinato, a partire dall'indice zero, fino a quando non trova il punto in cui deve essere inserito il valore.
Questo metodo determina che l'indice uno (tra tre e sette) è il punto di inserimento appropriato. L'algoritmo di inserimento (il Inserire metodo) quindi esegue l'inserimento rimuovendo il valore da inserire dall'array e spostando tutti i valori dal punto di inserimento all'elemento rimosso a destra. L'array ora si presenta così:
Matrice dopo il primo algoritmo di inserimento La matrice dall'indice zero a due è ora nota per essere ordinata e tutto dall'indice tre alla fine è sconosciuto. Il processo ora ricomincia dall'indice tre, che ha il valore quattro. Man mano che l'algoritmo continua, i seguenti inserimenti si verificano finché l'array non viene ordinato.
Matrice dopo ulteriori algoritmi di inserimento Quando non ci sono ulteriori inserimenti da eseguire, o quando la parte ordinata dell'array è l'intero array, l'algoritmo è finito.
Accentsconagua
public void Sort (T [] items) int sortedRangeEndIndex = 1; while (sortedRangeEndIndex < items.Length) if (items[sortedRangeEndIndex].CompareTo(items[sortedRangeEndIndex - 1]) < 0) int insertIndex = FindInsertionIndex(items, items[sortedRangeEndIndex]); Insert(items, insertIndex, sortedRangeEndIndex); sortedRangeEndIndex++; private int FindInsertionIndex(T[] items, T valueToInsert) for (int index = 0; index < items.Length; index++) if (items[index].CompareTo(valueToInsert) > 0) indice di ritorno; lancia nuova InvalidOperationException ("L'indice di inserimento non è stato trovato"); private void Insert (T [] itemArray, int IndexInsertingAt, int IndexInsertingFrom) // itemArray = 0 1 2 4 5 6 3 7 // insertingAt = 3 // insertingFrom = 6 // actions // 1: Store index at in temp temp = 4 // 2: Imposta indice all'indice da -> 0 1 2 3 5 6 3 7 temp = 4 // 3: Passeggia indietro dall'indice dall'indice a + 1. // Spostamento dei valori da sinistra a destra una volta. // 0 1 2 3 5 6 6 7 temp = 4 // 0 1 2 3 5 5 6 7 temp = 4 // 4: Scrive valore temp per indicizzare a + 1. // 0 1 2 3 4 5 6 7 temp = 4 // Passaggio 1. T temp = itemArray [indexInsertingAt]; // Passaggio 2. itemArray [indexInsertingAt] = itemArray [indexInsertingFrom]; // Passaggio 3. for (int current = indexInsertingFrom; current> indexInsertingAt; current--) itemArray [current] = itemArray [current - 1]; // Passaggio 4. itemArray [indexInsertingAt + 1] = temp; | Comportamento | Ordina l'array di input utilizzando l'algoritmo di ordinamento di selezione. | ||
| Complessità | Caso migliore | Caso medio | Caso peggiore |
| Tempo | Sopra) | Sopra2) | Sopra2) |
| Spazio | O (1) | O (1) | O (1) |
L'ordinamento selezione è un tipo di ibrido tra ordinamento a bolle e ordinamento di inserimento. Come il bubble sort, elabora l'array ripetendo continuamente dall'inizio alla fine, selezionando un valore e spostandolo nella posizione corretta. Tuttavia, a differenza di bubble sort, seleziona il valore più piccolo non selezionato anziché il più grande. Come l'ordinamento di inserimento, la parte ordinata dell'array è l'inizio dell'array, mentre con l'ordinamento a bolle la parte ordinata è alla fine.
Vediamo come funziona utilizzando lo stesso array non ordinato che abbiamo usato.
Array di numeri interi non ordinati Al primo passaggio, l'algoritmo tenterà di trovare il valore più piccolo nell'array e inserirlo nel primo indice. Questo è eseguito dal FindIndexOfSmallestFromIndex, che trova l'indice del valore più piccolo non smistato a partire dall'indice fornito.
Con un array così piccolo, possiamo dire che il primo valore, tre, è il valore più piccolo in modo che sia già nel posto giusto. A questo punto sappiamo che il valore nell'array index zero è il valore più piccolo e quindi è nell'ordine corretto. Quindi ora possiamo iniziare il passaggio due, questa volta solo guardando le voci dell'array da uno a n-1.
Il secondo passaggio determinerà che quattro è il valore più piccolo nell'intervallo non ordinato e scambierà il valore nel secondo slot con il valore nello slot in cui sono stati trattenuti quattro (scambiando il quattro e il sette). Dopo aver superato due completamenti, il valore quattro verrà inserito nella sua posizione ordinata.
Matrice dopo il secondo passaggio L'intervallo ordinato è ora dall'indice zero all'indice uno e l'intervallo non ordinato va dall'indice 2 a n-1. Al termine di ogni passaggio successivo, la porzione ordinata dell'array si ingrandisce e la porzione non ordinata diventa più piccola. Se in qualsiasi momento lungo il percorso non vengono eseguiti inserimenti, è noto che l'array è ordinato. In caso contrario, il processo continua fino a quando l'intero array è noto per essere ordinato.
Dopo altri due passaggi, l'array viene ordinato:
Matrice ordinata public void Sort (T [] items) int sortedRangeEnd = 0; while (sortedRangeEnd < items.Length) int nextIndex = FindIndexOfSmallestFromIndex(items, sortedRangeEnd); Swap(items, sortedRangeEnd, nextIndex); sortedRangeEnd++; private int FindIndexOfSmallestFromIndex(T[] items, int sortedRangeEnd) T currentSmallest = items[sortedRangeEnd]; int currentSmallestIndex = sortedRangeEnd; for (int i = sortedRangeEnd + 1; i < items.Length; i++) if (currentSmallest.CompareTo(items[i]) > 0) currentSmallest = items [i]; currentSmallestIndex = i; restituisce currentSmallestIndex;
| Comportamento | Ordina l'array di input utilizzando l'algoritmo di unisci merge. | ||
| Complessità | Caso migliore | Caso medio | Caso peggiore |
| Tempo | O (n log n) | O (n log n) | O (n log n) |
| Spazio | Sopra) | Sopra) | Sopra) |
Finora abbiamo visto algoritmi che operano elaborando linearmente la matrice. Questi algoritmi hanno il vantaggio di operare con pochissimo overhead di memoria, ma al costo della complessità quadratica di runtime. Con l'unire sort, vedremo il nostro primo algoritmo di divisione e conquista.
Gli algoritmi di divisione e conquista funzionano abbattendo grandi problemi in problemi più piccoli, più facilmente risolvibili. Vediamo questi tipi di algoritmi nella vita di tutti i giorni. Ad esempio, utilizziamo un algoritmo divide et impera quando si cerca una rubrica telefonica.
Se si desidera trovare il nome Erin Johnson in una rubrica, non si avvierà da A e si sposterà pagina per pagina. Piuttosto, probabilmente aprirai la rubrica al centro. Se aprissi le M, rileggerei qualche pagina, forse un po 'troppo lontano, forse gli H. Quindi avresti invertito. E continueresti a lanciarti avanti e indietro con incrementi sempre più piccoli finché alla fine non avresti trovato la pagina che volevi (o se fossi così vicina da dare un senso alla verità).
Quanto sono efficienti gli algoritmi di divisione e conquista?
Supponiamo che la rubrica sia lunga 1000 pagine. Quando apri il centro, hai risolto il problema in due problemi di 500 pagine. Supponendo che tu non sia sulla pagina giusta, ora puoi scegliere il lato appropriato per cercare e tagliare di nuovo il problema a metà. Ora lo spazio del tuo problema è di 250 pagine. Dato che il problema si riduce ancora di più, possiamo vedere che una rubrica di 1000 pagine può essere cercata solo in dieci giri di pagina. Questo è l'1% del numero totale di turni di pagina che potrebbero essere necessari quando si esegue una ricerca lineare.
Unisci ordina opera tagliando l'array a metà ancora e ancora fino a quando ogni pezzo è lungo un solo oggetto. Quindi questi elementi vengono rimessi insieme (uniti) in ordine di sorta.
Iniziamo con il seguente array:
Array di numeri interi non ordinati E ora tagliamo la schiera a metà:
Matrice non ordinata tagliata a metà Ora entrambi questi array vengono tagliati a metà ripetutamente fino a quando ciascun elemento è da solo:
Matrice non ordinata tagliata a metà fino a quando ciascun indice non si trova da solo Con l'array ora diviso in parti più piccole possibili, si verifica il processo di unione di queste parti in ordine di ordinamento.
Matrice ordinata in gruppi di due I singoli elementi diventano gruppi ordinati di due, quei gruppi di due si fondono insieme in gruppi ordinati di quattro, e quindi alla fine si uniscono tutti insieme come una matrice ordinata finale.
Matrice ordinata in gruppi di quattro (in alto) e ordinamento completato (in basso) Prendiamo un momento per pensare alle singole operazioni che dobbiamo implementare:
Ordinare il metodo fa questo.fondersi il metodo fa questo.Una considerazione prestazionale dell'ordinamento di fusione è che, a differenza degli algoritmi di ordinamento lineare, merge sort eseguirà l'intera logica di suddivisione e unione, comprese eventuali allocazioni di memoria, anche se l'array è già in ordine. Sebbene abbia prestazioni migliori nel caso peggiore rispetto agli algoritmi di ordinamento lineare, le prestazioni migliori saranno sempre peggiori. Ciò significa che non è un candidato ideale quando si ordinano dati che sono noti per essere quasi ordinati; ad esempio, quando si inseriscono dati in una matrice già ordinata.
pubblico vuoto Sort (T [] items) if (items.Length <= 1) return; int leftSize = items.Length / 2; int rightSize = items.Length - leftSize; T[] left = new T[leftSize]; T[] right = new T[rightSize]; Array.Copy(items, 0, left, 0, leftSize); Array.Copy(items, leftSize, right, 0, rightSize); Sort(left); Sort(right); Merge(items, left, right); private void Merge(T[] items, T[] left, T[] right) int leftIndex = 0; int rightIndex = 0; int targetIndex = 0; int remaining = left.Length + right.Length; while(remaining > 0) if (leftIndex> = left.Length) items [targetIndex] = right [rightIndex ++]; else if (rightIndex> = right.Length) items [targetIndex] = left [leftIndex ++]; else if (left [leftIndex] .CompareTo (right [rightIndex]) < 0) items[targetIndex] = left[leftIndex++]; else items[targetIndex] = right[rightIndex++]; targetIndex++; remaining--;
| Comportamento | Ordina l'array di input utilizzando l'algoritmo di ordinamento rapido. | ||
| Complessità | Caso migliore | Caso medio | Caso peggiore |
| Tempo | O (n log n) | O (n log n) | Sopra2) |
| Spazio | O (1) | O (1) | O (1) |
L'ordinamento rapido è un altro algoritmo di ordinamento per dividere e conquistare. Questo funziona eseguendo ricorsivamente il seguente algoritmo:
Eseguiamo un rapido ordinamento sul seguente array:
Array di numeri interi non ordinati Il primo passo dice che selezioniamo il punto di partizione usando un indice casuale. Nel codice di esempio, questo viene fatto su questa linea:
int pivotIndex = _pivotRng.Next (sinistra, destra);
Scegliere un indice di partizione casuale Ora che conosciamo l'indice della partizione (quattro), osserviamo il valore in quel punto (sei) e spostiamo i valori nell'array in modo che tutto meno del valore sia sul lato sinistro dell'array e su tutto il resto (valori maggiori o uguale) viene spostato sul lato destro dell'array. Tieni presente che lo spostamento dei valori intorno potrebbe modificare l'indice in cui è memorizzato il valore della partizione (lo vedremo a breve).
Lo scambio dei valori viene effettuato dal metodo della partizione nel codice di esempio.
Spostamento dei valori a sinistra e a destra del valore della partizione A questo punto, sappiamo che sei è nel punto giusto dell'array. Lo sappiamo perché ogni valore a sinistra è inferiore al valore della partizione e tutto a destra è maggiore o uguale al valore della partizione. Ora ripetiamo questo processo sulle due partizioni non ordinate dell'array.
La ripetizione viene eseguita nel codice di esempio chiamando in modo ricorsivo il metodo quicksort con ciascuna delle partizioni dell'array. Si noti che questa volta l'array di sinistra è partizionato all'indice uno con il valore cinque. Il processo di spostamento dei valori nelle posizioni appropriate sposta il valore cinque in un altro indice. Lo faccio notare per rafforzare il punto che stai selezionando un valore di partizione, non un indice di partizione.
Ripetendo il pivot e la partizione Ordinamento rapido di nuovo:
Ripeti il pivot e la partizione di nuovo E ordinare rapidamente un'ultima volta:
Ripeti il pivot e la partizione di nuovo Con solo un valore non selezionato rimasto e poiché sappiamo che ogni altro valore è ordinato, l'array è completamente ordinato.
Random _pivotRng = new Random (); public void Sort (T [] items) quicksort (items, 0, items.Length - 1); quicksort private void (T [] items, int left, int right) if (left < right) int pivotIndex = _pivotRng.Next(left, right); int newPivot = partition(items, left, right, pivotIndex); quicksort(items, left, newPivot - 1); quicksort(items, newPivot + 1, right); private int partition(T[] items, int left, int right, int pivotIndex) T pivotValue = items[pivotIndex]; Swap(items, pivotIndex, right); int storeIndex = left; for (int i = left; i < right; i++) if (items[i].CompareTo(pivotValue) < 0) Swap(items, i, storeIndex); storeIndex += 1; Swap(items, storeIndex, right); return storeIndex;
