[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.