[Powered by Google Translate] TOMMY: Diamo un'occhiata a ordinamento per selezione, un algoritmo
per prendere un elenco di numeri e ordinamento.
Un algoritmo, lo ricordiamo, è semplicemente uno step-by-step
procedimento per realizzare un compito.
L'idea alla base di ordinamento per selezione è quello di dividere
la nostra lista in due parti -
una porzione di cernita e di una parte non ordinato.
Ad ogni passo dell'algoritmo, un numero viene spostato dalla
parte non ordinata alla porzione ordinato fino alla fine il
l'intero elenco è ordinato.
Quindi, ecco un elenco di sei numeri -
23, 42, 4, 16, 8, e 15.
In questo momento l'intero elenco è considerato ordinato.
Anche se un numero come 16 potrebbe già essere nella sua corretta
posizione, il nostro algoritmo non ha modo di sapere che fino a quando il
l'intero elenco è ordinato.
Quindi dovremo considerare ogni numero da unsorted fino ordinare
noi stessi.
Sappiamo che si desidera che l'elenco sia in ordine crescente.
Quindi dobbiamo provare a costruire la parte ordinata della nostra lista
da sinistra a destra, dal più piccolo al più grande.
Per fare questo, abbiamo bisogno di trovare l'elemento minimo unsorted
e messo alla fine della porzione ordinato.
Dal momento che questo elenco non è ordinato, l'unico modo per farlo è quello di
guardare ogni elemento nella porzione unsorted, ricordando
elemento che è il più basso e confrontando
ciascun elemento a questo.
Quindi per prima cosa guardare il 23.
Questo è il primo elemento che abbiamo visto, così ci ricorderemo
come il minimo.
Avanti vedremo 42.
42 è maggiore di 23, quindi 23 è ancora il minimo.
La prossima è il 4, che è inferiore a 23, per cui ci ricorderemo quattro
come il nuovo minimo.
Successivo è 16, che è più grande di 4, quindi 4
è ancora il minimo.
8 è maggiore di 4, e 15 è maggiore di 4, quindi 4 deve essere
l'elemento più piccolo indifferenziati.
Così, anche se, come gli esseri umani si può subito vedere che 4 è
l'elemento minimo, il nostro algoritmo ha bisogno di guardare al
ogni elemento indifferenziato, anche dopo che abbiamo trovato il 4 - il
elemento minimo.
Quindi, ora che abbiamo trovato l'elemento minimo, 4, ci vorrà
per spostarlo nella porzione ordinata della lista.
Poiché questo è il primo passo, questo significa che vogliamo mettere a 4
all'inizio della lista.
Adesso 23 è all'inizio della lista, così
Barattiamo il 4 e il 23.
Così ora la nostra lista simile a questa.
Sappiamo che 4 deve essere nella sua posizione definitiva, perché è
sia il più piccolo elemento e l'elemento all'inizio
dell'elenco.
Quindi questo significa che non abbiamo mai bisogno di muoversi di nuovo.
Quindi cerchiamo di ripetere questo processo per aggiungere un altro elemento alla
porzione della lista ordinata.
Sappiamo che non abbiamo bisogno di guardare il 4, perché è
già ordinati.
Così possiamo iniziare dal 42, che ci ricorderemo come il
elemento minimo.
Così la prossima vedremo il 23, che è inferiore a 42, in modo da
ricordate 23 è il nuovo minimo.
Quindi, vediamo la 16, che è inferiore a 23, così
16 è il nuovo minimo.
Ora guardiamo la 8 che è inferiore a 16, in modo da
8 è il nuovo minimo.
E infine 8 è minore di 15, quindi sappiamo che 8 è un minimo
elemento indifferenziati.
Questo significa che dobbiamo aggiungere 8 al ordinati
porzione della lista.
In questo momento 4 è l'unico elemento selezionato, quindi vogliamo mettere
l'8 vicino al 4.
Poiché 42 è il primo elemento nella porzione non ordinata
lista, dobbiamo provare a scambiare il 42 e l'8.
Così ora la nostra lista simile a questa.
4 e 8 rappresentano la porzione della lista ordinata, e la
numeri rimanenti rappresentano il unsorted
porzione della lista.
Quindi cerchiamo di continuare con un'altra iterazione.
Si comincia con 23 questa volta, dal momento che non c'è bisogno di guardare
il 4 e l'8 più perché hanno
già stati ordinati.
16 è inferiore a 23, per cui ci ricorderemo
16 come nuovo minimo.
16 è minore di 42, ma 15 è inferiore a 16, quindi 15 deve essere
l'elemento minimo indifferenziati.
Quindi ora vogliamo scambiare la 15 e la 23 a
ci danno questa lista.
La porzione ordinata della lista consiste di 4, 8 e 15, e
questi elementi sono ancora ordinati.
Ma si da il caso che l'elemento successivo indifferenziati, 16,
è già ordinato.
Tuttavia, non c'è modo per il nostro algoritmo di sapere che il 16
è già nella sua posizione corretta, quindi abbiamo ancora bisogno di
ripetere lo stesso processo.
Così vediamo che 16 è inferiore a 42, e 16 è inferiore a 23, in modo da
16 deve essere l'elemento minimo.
E 'impossibile sostituire questo elemento con se stesso, in modo che possiamo
semplicemente lasciarlo in questa posizione.
Quindi abbiamo bisogno di un altro passaggio del nostro algoritmo.
42 è maggiore di 23, quindi 23 deve essere
minimo elemento indifferenziati.
Una volta che ci scambiamo il 23 e il 42, si finisce con il nostro finale
lista ordinata -
4, 8, 15, 16, 23, 42.
Sappiamo che 42 devono essere nel posto giusto dal momento che è il
unico elemento a sinistra, e questo è per selezione.
Passiamo ora formalizzare il nostro algoritmo con un po '
pseudocodice.
In linea uno, possiamo vedere che abbiamo bisogno di integrare più
ogni elemento della lista.
Tranne l'ultimo elemento, in quanto il 1 elemento
lista è già ordinato.
On line due, si considera il primo elemento della unsorted
parte della lista per essere il minimo, come abbiamo fatto con il nostro
esempio, così abbiamo qualcosa da confrontare.
Linea tre inizia un secondo ciclo in cui iterare
ogni elemento indifferenziati.
Sappiamo che dopo i iterazioni, la parte ordinata
della nostra lista deve avere i elementi in esso da ogni passo
tipo un elemento.
Quindi il primo elemento indifferenziato deve essere in posizione i più 1.
On line quattro, si confronta l'elemento corrente al minimo
elemento che abbiamo visto finora.
Se l'elemento corrente è inferiore al minimo
elemento, allora si dovrebbe ricordare l'elemento corrente come nuovo
minimo sulla linea cinque.
Infine, sulle linee di sei e sette, si scambiano il minimo
elemento con il primo elemento indifferenziato, così
aggiungerlo alla porzione della lista ordinata.
Una volta che abbiamo un algoritmo, una domanda importante per chiedere
noi stessi come i programmatori è quanto tempo ci vuole?
Ecco ora la domanda quanto tempo ci vuole per questo
algoritmo per l'esecuzione nel caso peggiore?
Richiamo che rappresentiamo questa corsa
tempo con grande notazione O.
Per determinare l'elemento minimo unsorted, abbiamo
essenzialmente dovuto confrontare ogni elemento della lista per
ogni altro elemento della lista.
Intuitivamente, questo suona come una O di funzionamento n quadrato.
Guardando alla nostra pseudocodice, abbiamo anche un ciclo nidificato all'interno
un altro loop, che suona davvero come una O
di funzionamento n quadrato.
Tuttavia, ricordate che non abbiamo bisogno di guardare oltre il
intero elenco nel determinare l'elemento minimo unsorted?
Una volta sapeva che il 4 è stato risolto, per esempio, non abbiamo
bisogno di guardare di nuovo.
Così fa questo basso è il tempo di esecuzione?
Per la nostra lista di lunghezza 6, avevamo bisogno di fare cinque
confronti per il primo elemento, per quattro confronti
il secondo elemento, e così via.
Ciò significa che il numero totale di passi è la somma di
gli interi da 1 a la lunghezza della lista meno 1.
Possiamo rappresentare questo con una sommatoria.
Non andrà in sommatorie qui.
Ma si scopre che questa sommatoria è uguale an volte
n meno 1 su 2.
O, equivalentemente, n quadrato più di 2 su 2 meno n.
Quando si parla di runtime asintotico, questo termine n quadrato
sta andando a dominare questo termine n.
Quindi, ordinamento per selezione è O di n quadrato.
Ricordiamo che nel nostro esempio, ordinamento per selezione ancora bisogno di
verificare se un numero che è già stato risolto
bisogno di essere spostati.
In modo che significa che se abbiamo corso per selezione su una già
lista ordinata, richiederebbe lo stesso numero di passi come
sarebbe quando si esegue su un elenco del tutto indifferenziati.
Quindi, ordinamento per selezione ha una prestazione migliore dei casi di quadrato n,
che noi rappresentiamo con omega n quadrato.
E questo è tutto per il selection sort.
Solo uno dei molti algoritmi che possiamo
utilizzare per ordinare un elenco.
Il mio nome è Tommy, e questo è CS50.