[RIPRODUZIONE DI BRANI MUSICALI] DOUG LLOYD: ordinamento per selezione è un algoritmo che, come ci si potrebbe aspettare, ordina un insieme di elementi. E richiamo algoritmo è un insieme passo-passo di istruzioni per il completamento di un compito. 

Nella selezione ordinare il idea di base è questa, trovare il più piccolo elemento misti e aggiungerlo alla fine della lista ordinata. In effetti ciò che fa è costruire un elenco ordinato, un elemento alla volta. Scomponendola a pseudocodice potremmo affermare questo algoritmo come segue, ripetere questo fino Nessun elemento non ordinati rimangono. Ricerca tra il indifferenziati i dati per trovare il più piccolo valore, poi scambiare il valore minimo con il primo elemento della parte indifferenziati. 

Può essere utile visualizzare questo, così diamo un'occhiata a questo. Quindi questo, io sostengo, è un allineamento misti e ho indicato che indicando che tutti gli elementi sono di colore rosso, essi non sono ancora ordinati. Questo è l'intero parte indifferenziati della matrice. 

Quindi cerchiamo di passare attraverso le fasi di selection sort per ordinare questo array. Così ancora una volta, stiamo andando ripetere fino a quando non gli elementi non ordinati rimangono. Stiamo andando di ricerca attraverso il i dati per trovare il più piccolo valore, e poi scambiare tale valore con il primo elemento della parte indifferenziati. 

In questo momento, ancora una volta, l'intera array è la parte non ordinata. Tutti gli elementi rossi sono indifferenziati. Così si cerca attraverso e troviamo il valore più piccolo. Partiamo all'inizio, andiamo fino alla fine, troviamo il valore più piccolo è, uno. Ecco, questo è parte uno. E poi la seconda parte, scambiare tale valore con il primo elemento della parte indifferenziati, o il primo elemento rosso. 

In questo caso sarebbe cinque, così abbiamo sostituire uno e cinque. Quando facciamo questo, possiamo vediamo visivamente che abbiamo spostato l'elemento più piccolo valore della matrice, per principio. Effettivamente l'ordinamento quell'elemento. 

E così possiamo davvero confermare e affermano che uno, è ordinato. E così noi indichiamo la porzione ordinato della nostra matrice, colorandola blu. 

Ora dobbiamo solo ripetere il processo. Cerchiamo attraverso la parte non ordinata di la matrice di trovare l'elemento più piccolo. In questo caso, è due. 

Abbiamo swap con la prima elemento della parte indifferenziati. In questo caso due avviene anche per essere il primo elemento della parte indifferenziati. Quindi noi scambiamo due con se stesso, che in realtà lascia solo due dove si trova, ed è ordinato. Proseguendo, si cerca attraverso per trovare l'elemento più piccolo. Sono le tre. Ci scambiamo con il primo elemento, che è cinque. E ora tre è ordinato. 

Cerchiamo attraverso di nuovo, e noi trovare l'elemento più piccolo è di quattro. Noi scambiamo con il primo elemento della parte indifferenziati, e ora quattro è ordinato. 

Troviamo che cinque è l'elemento più piccolo. Ci scambiamo con il primo elemento della parte indifferenziati. E ora cinque è ordinato. 

E poi, infine, il nostro parte indifferenziati è costituito di un solo elemento, così cerchiamo attraverso e troviamo che sei è il più piccolo, e di fatto, unico elemento. E allora si può affermare che esso è ordinato. E ora abbiamo cambiato la nostra gamma da essere completamente unsorted in rosso, a filtrate completamente in blu, con ordinamento per selezione. 

Quindi qual è la peggiore delle ipotesi qui? Beh, nel peggiore in assoluto caso, dobbiamo guardare oltre tutti gli elementi della matrice di trovare il più piccolo elemento indifferenziati, e dobbiamo ripetere questo processo n volte. Una volta per ogni elemento dell'array perché solo in questo algoritmo, tipo un elemento alla volta. 

Qual è la migliore delle ipotesi? Beh, è ​​esattamente lo stesso, giusto? Noi in realtà fare un passo ancora attraverso ogni singolo elemento dell'array al fine di confermare che si tratta, infatti, l'elemento più piccolo. 

Così il runtime caso peggiore, abbiamo ripetere un processo n volte, una volta per ogni di n elementi. E nella migliore delle ipotesi, dobbiamo fare lo stesso. 

Quindi, ripensando al nostro computazionale toolbox complessità, cosa ne pensi è la peggiore caso di runtime per selezione tipo? Cosa ne pensi è la migliore caso di runtime per selezione tipo? 

Avete indovinato Big O di n al quadrato, e Big Omega di n al quadrato? Avreste ragione. Quelli sono, infatti, la caso peggiore e migliore corsa caso volte, per la selezione sorta. 

Sono Doug Lloyd. Questo è CS50.