[Powered by Google Translate] [Ordina inserire]
[Tommy MacWilliam] [Harvard University]
[Questo è CS50.TV]
Diamo un'occhiata a ordinamento per inserzione, un algoritmo per fare un elenco di numeri e ordinarli.
Un algoritmo, lo ricordiamo, è semplicemente un passo per passo la procedura per realizzare un compito.
L'idea alla base insertion sort, è 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 porzione misti alla porzione ordinati
finché alla fine l'intero elenco è ordinato.
Ecco l'elenco dei sei numeri non ordinati - 23, 42, 4, 16, 8, e 15.
Dal momento che questi numeri non sono tutti in ordine crescente, sono ordinati.
Dal momento che non hanno iniziato l'ordinamento ancora, prenderemo in considerazione tutti e sei gli elementi nostra parte indifferenziati.
>> Una volta che cominciamo ordinamento, metteremo questi numeri ordinati a sinistra di questi.
Allora, cominciamo con 23, il primo elemento nella nostra lista.
Non ci sono elementi nella nostra parte ancora ordinati,
quindi cerchiamo di prendere in considerazione solo 23 per l'inizio e la fine della nostra porzione ordinati.
Ora, la nostra parte ha ordinato un numero, 23,
e la nostra parte non ordinato ha queste cinque numeri.
Passiamo ora inserire il numero successivo nella nostra parte indifferenziati, 42, nella porzione ordinata.
>> Per fare ciò, abbiamo bisogno di confrontare il 42 al 23 - l'unico elemento della nostra porzione ordinati finora.
Quarantadue è più grande di 23, in modo che possiamo semplicemente aggiungere 42 alla fine
della porzione della lista ordinata. Fantastico!
Ora la nostra porzione ordinati ha due elementi, e la nostra parte indifferenziati ha quattro elementi.
Allora, ora passare alla 4, l'elemento successivo nella parte indifferenziati.
Così, dove deve essere collocato nella porzione ordinata?
>> Ricordate, ora vogliamo mettere questo numero in modo ordinato
così la nostra porzione ordinati rimane ordinato correttamente in ogni momento.
Se poniamo il 4 alla destra del 42, allora la nostra lista sarà fuori servizio.
Quindi, cerchiamo di continuare a spostare da destra a sinistra nella nostra porzione di sorta.
Come ci muoviamo, facciamo spostare ogni numero giù un posto per fare spazio al nuovo numero.
Ok, 4 è anche inferiore a 23, in modo da non possiamo mettere neanche qui.
Passiamo il 23 giusto posto.
>> Questo significa che ci piacerebbe mettere il 4 nel primo slot nella parte ordinata.
Si noti come questo spazio della lista è già vuoto,
perché abbiamo elementi in movimento filtrate così li abbiamo incontrati.
Bene. Quindi, siamo a metà strada.
Continuiamo il nostro algoritmo inserendo il 16 nella porzione ordinata.
Sedici è inferiore a 42, quindi cerchiamo di spostare il 42 a destra.
Sedici è anche meno di 23, quindi cerchiamo di cambiare anche tale elemento.
>> Ora, 16 è maggiore di 4. Quindi, sembra che vorremmo inserire la 16 tra il 4 e il 23.
Mentre si muove attraverso la porzione della lista ordinata da destra a sinistra,
4 è il primo numero abbiamo visto che è inferiore al numero
stiamo cercando di inserire.
Quindi, ora siamo in grado di inserire il 16 in questo slot vuoto,
che, ricordiamo, abbiamo creato da elementi in movimento nella parte ordinamento sopra
come li abbiamo incontrati.
>> Bene. Ora, abbiamo quattro elementi ordinati e due elementi non sottoposti a cernita.
Quindi, cerchiamo di spostare il 8 nella porzione ordinata.
Otto è inferiore a 42.
Otto è inferiore a 23.
E 8 è inferiore a 16.
Ma 8 è maggiore di 4.
Quindi, vorremmo inserire la 8 tra il 4 e il 16.
Ed ora non ci resta che un elemento in più a sinistra per ordinare - il 15.
Quindici è inferiore a 42,
Quindici è inferiore a 23.
E 15 è inferiore a 16.
Ma 15 è maggiore di 8.
>> Così, qui è dove vogliamo rendere il nostro inserimento definitivo.
E abbiamo finito.
Non ci sono più elementi nella parte non ordinata,
e la nostra parte è ordinata secondo l'ordine corretto.
I numeri sono ordinati dal più piccolo al più grande.
Quindi, diamo uno sguardo ad alcuni pseudocodice che descrive i passaggi che abbiamo appena eseguiti.
>> In linea 1, possiamo vedere che abbiamo bisogno di eseguire iterazioni su ogni elemento della lista
tranne la prima, in quanto il primo elemento nella porzione unsorted diventerà semplicemente
il primo elemento nella porzione ordinata.
Sulle linee 2 e 3, stiamo tenendo traccia del nostro posto attuale nella parte indifferenziati.
Elemento rappresenta il numero che stiamo muovendo nella porzione ordinata,
e j rappresenta il nostro indice nella porzione indifferenziati.
>> In linea 4, che stiamo scorrendo la porzione ordinati da destra a sinistra.
Vogliamo fermare iterazione volta che l'elemento a sinistra della nostra posizione attuale
è minore l'elemento che stiamo cercando di inserire.
Sulla linea 5, ci stiamo spostando ogni elemento che incontriamo uno spazio a destra.
In questo modo, avremo uno spazio libero da inserire quando troviamo il primo elemento
meno l'elemento ci stiamo muovendo.
In linea 6, stiamo aggiornando il nostro contatore per continuare a spostare a sinistra attraverso la porzione ordinata.
Infine, sulla linea 7, stiamo inserendo l'elemento nella porzione ordinata della lista.
>> Sappiamo che è giusto da inserire in posizione j,
perché abbiamo già spostato l'elemento che ha usato per essere lì uno spazio a destra.
Ricordate, ci stiamo muovendo attraverso la porzione ordinati da destra a sinistra,
ma ci stiamo muovendo attraverso la parte non ordinata da sinistra a destra.
Bene. Diamo ora un'occhiata a quanto tempo in esecuzione che l'algoritmo ha preso.
Ecco ora la domanda quanto tempo ci vuole per questo algoritmo per l'esecuzione nel caso peggiore.
Ricordiamo che noi rappresentiamo il tempo di esecuzione con Big notazione O.
Al fine di risolvere la nostra lista, abbiamo dovuto scorrere gli elementi nella parte non ordinata,
e per ciascuno di tali elementi, potenzialmente su tutti gli elementi della porzione ordinata.
Intuitivamente, questo suona come un (n ^ 2) O.
>> Guardando alla nostra pseudocodice, abbiamo un ciclo annidato all'interno di un altro ciclo,
che, anzi, suona come un (n ^ 2) O.
Tuttavia, la porzione di elenco ordinato non conteneva l'intero elenco fino alla fine.
Ancora, si potrebbe potenzialmente inserire un nuovo elemento all'inizio della parte ordinata
su ogni iterazione dell'algoritmo,
il che significa che avremmo dovuto guardare ogni elemento attualmente nella porzione ordinata.
Quindi, questo significa che potrebbe fare una comparazione per il secondo elemento,
due confronti per il terzo elemento, e così via.
Così, il numero totale di operazioni è la somma dei numeri 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 somma è uguale a
n (n - 1) su 2, che equivale n ^ 2/2 - n / 2.
Quando si parla di esecuzione asintotico,
questo termine n ^ 2 sta per dominare questo termine n.
Quindi, insertion sort è Big O (n ^ 2).
Che cosa succede se abbiamo corso ordinamento per inserimento in un elenco già ordinato.
In tal caso, saremmo semplicemente costruire la parte ordinati da sinistra a destra.
Quindi, ci sarà solo bisogno dell'ordine di n passi.
>> Ciò significa che insertion sort ha una migliore prestazione nel caso di n,
che noi rappresentiamo con Ω (n).
E questo è tutto per insertion sort,
solo uno dei molti algoritmi possiamo utilizzare per ordinare un elenco.
Il mio nome è Tommy, e questo è CS50.
[CS50.TV]
Oh, non si può fermare che una volta che si avvia.
Oh, abbiamo fatto - Boom! >>