>> [RIPRODUZIONE DI BRANI MUSICALI]
>> DOUG LLOYD: Quindi insertion sort è un altro algoritmo si può utilizzare per ordinare un array.
L'idea alla base di questo algoritmo è quello di costruire il vostro array ordinato
in posto, spostando gli elementi di il modo in cui, come si va, per fare spazio.
Questo è leggermente diverso da ordinamento per selezione o bolla
sorta, per esempio, dove stiamo regolando le posizioni,
dove stiamo facendo swap.
>> In questo caso ciò che siamo realmente facendo è elementi scorrevoli
sopra, fuori strada.
Come funziona questo algoritmo lavorare in pseudocodice?
Pozzo di lasciare che arbitrariamente dire che la primo elemento dell'array è ordinato.
Stiamo costruendo al suo posto.
>> Noi stiamo andando andiamo un elemento alla volta e costruire, e così la prima cosa che vediamo
è un array di un elemento.
E per definizione, uno matrice elemento è ordinato.
>> Poi ci ripete questo processo until-- ci ripetiamo il seguente processo
fino a quando tutti gli elementi sono ordinati.
Guardate il prossimo elemento misti e inserirla nella porzione ordinata,
spostando il numero richiesto di elementi di mezzo.
Speriamo che questa visualizzazione vi aiuterà a vedere esattamente che cosa è
succedendo con insertion sort.
>> Quindi, di nuovo, ecco la nostra intero array indifferenziati,
tutti gli elementi indicati in rosso.
E seguiamo il passi del nostro pseudocodice.
La prima cosa che facciamo, è che chiamiamo primo elemento dell'array, filtrate.
Così siamo solo dire andando cinque, il gioco è ora risolto.
>> Poi guardiamo alla prossima elemento indifferenziato della matrice
e vogliamo inserire tale nella porzione filtrate,
spostando gli elementi sopra.
Così due è il prossimo indifferenziati elemento della matrice.
Chiaramente appartiene prima della cinque, quindi quello che faremo
è una sorta di tenere due da parte per un secondo, spostare cinque sopra, e quindi inserire due
prima delle cinque, dove dovrebbe andare.
E ora possiamo dire che due è ordinato.
>> Quindi, come potete vedere, abbiamo soltanto finora esaminato due elementi della matrice.
Non abbiamo guardato il riposiamo a tutti, ma abbiamo
GOT questi due elementi ordinati per modo del meccanismo di spostamento.
>> Quindi ripetiamo di nuovo il processo.
Guardate la prossima indifferenziati elemento, questo è uno.
Facciamo sostengono che parte per un secondo, spostare tutto finito, e mettere uno
dove dovrebbe andare.
>> Anche in questo caso, ancora, abbiamo sempre e solo guardato uno, due e cinque.
Noi non sappiamo che cosa altro è in arrivo, ma abbiamo risolto questi tre elementi.
>> Successivo elemento indifferenziati è tre, quindi dovremo metterlo da parte.
Ti spostiamo su quello che necessario che, questa volta
non è tutto come nel precedente due casi, è solo il cinque.
E poi ci atteniamo alle tre, tra i due e cinque.
>> Sei è il prossimo indifferenziati elemento all'array.
E infatti sei è maggiore di cinque, così non abbiamo nemmeno bisogno di fare qualsiasi scambio.
Possiamo solo virare sei a destra sulla l'estremità della porzione filtrate.
>> Infine, quattro è il ultimo elemento non differenziati.
Quindi dovremo metterla da parte, spostiamo sopra gli elementi che devono passare sopra,
e poi mettere quattro in cui essa appartiene.
E ora guarda, abbiamo sorta di tutti gli elementi.
Notate con inserzione tipo, non abbiamo avuto
andare avanti e indietro attraverso l'array.
Ci siamo andati solo attraverso l'array una volta, e abbiamo spostato le cose
che avevamo già incontrato, al fine per fare spazio per i nuovi elementi.
>> Allora qual è il caso peggiore scenario con insertion sort?
Nel caso peggiore, la array è in ordine inverso.
Dovete spostare ciascuno degli elementi n fino a n posizioni, ogni volta che ci
fare un inserimento.
Questo è un sacco di spostamento.
>> Nel migliore dei casi, la array è perfettamente ordinato.
E un po 'come quello che è successo con cinque e sei nell'esempio,
dove abbiamo potuto appena virare su senza dover fare qualsiasi spostamento,
avremmo essenzialmente facciamo.
>> Se si immagina che la nostra matrice era uno a sei,
avremmo Cominciamo da dichiarando uno è ordinato.
Due viene dopo uno così possiamo solo dicono, OK, bene uno e due sono ordinati.
Tre arriva dopo due così, OK, uno e due e tre sono ordinati.
>> Non stiamo facendo alcun swap, siamo semplicemente spostando questa linea arbitraria
tra ordinato e non ordinato come andiamo.
Nel modo più efficace come abbiamo fatto nell'esempio, trasformando elementi blu, come si procede.
Allora qual è il runtime caso peggiore, allora?
Ricordate, se dobbiamo passare ciascuno di gli n elementi eventualmente posizioni n,
speriamo che ti dà un'idea che il caso peggiore
runtime è Big O di n al quadrato.
>> Se la matrice è perfettamente ordinato, tutto quello che dobbiamo fare
è guardare ogni singolo elemento una volta, e poi abbiamo finito.
Così nel migliore dei casi, si tratta di omega di n.
>> Sono Doug Lloyd.
Questo è CS50.