[MUSIC JOC] 

DOUG LLOYD: Deci sortare prin inserție este un alt algoritm putem folosi pentru a sorta un array. Ideea din spatele acestui algoritm este de a construi matrice dumneavoastră sortat în loc, schimbarea elemente din modul cum te duci, pentru a face loc. Acest lucru este puțin diferit de la fel de selecție sau bule fel, de exemplu, în cazul în care suntem ajustarea locații, unde facem swap-uri. 

În acest caz, ceea ce suntem de fapt a face este elemente glisante peste, din drum. Cum functioneaza acest algoritm lucrează în pseudocod? Ei bine, lui să spunem arbitrar că primul element al tabloului este sortat. Suntem o clădire, în loc. 

Vom merge un element la un moment dat și construi, și astfel primul lucru pe care vom vedea este o gamă un element. Și prin definiție, un element de matrice sunt sortate. 

Apoi vom repeta acest proces until-- vom repeta procesul următor până când toate elementele sunt sortate. Uită-te la următorul element nesortate și introduceți-l în porțiunea sortate, prin schimbarea numărului necesar de elemente din drum. Sperăm că această vizualizare vă va ajuta să vedeți exact ceea ce-i întâmplă cu insertie fel. 

Deci, din nou, aici e noastră întreaga matrice nesortate, toate elementele indicate în roșu. Și să urmați trepte de pseudocod nostru. Primul lucru ce facem, este o numim primul element al tabloului, sortate. Deci suntem doar să spun cinci, te sortate acum. 

Apoi ne uităm la următoarea Element nesortate de matrice și vrem să inserați că în porțiunea sortate, prin schimbarea elemente peste. Deci doi este următoarea nesortat Element de matrice. În mod evident acesta face parte înainte ca cinci, astfel încât ceea ce vom face este un fel de organiza două deoparte pentru un al doilea, trecerea peste cinci, iar apoi introduceți de două înainte de cinci, în cazul în care pentru a ar trebui să meargă. Și acum putem spune că două sunt sortate. 

Deci, după cum puteți vedea, am numai în măsura privi două elemente ale tabloului. Nu am uitat la odihnă, la toate, dar am am aceste două elemente clasificate în funcție de intermediul mecanismului de deplasare. 

Așa că am repeta procesul. Uită-te la următoarea nesortat Element, e unul. Să susțin că o parte pentru un al doilea, schimba totul peste, și a pus un în cazul în care ar trebui să meargă. 

Din nou, încă, am doar vreodată sa uitat la una, două, cinci. Nu știm ce altceva se apropie, dar am sortat cele trei elemente. 

Următorul element de nesortate este trei, asa ca o vom deoparte. Vom schimba peste ceea ce am Trebuie să care, de data aceasta nu este totul la fel ca în precedent două cazuri, e doar cinci. Și apoi ne vom lipi trei în, între cele două și cinci. 

Șase este următoarea nesortat Element de matrice. Și, de fapt șase este mai mare de cinci, așa nici măcar nu trebuie să faci orice swapping. Putem tac doar șase dreapta pe la sfârșitul porțiunii sortate. 

În cele din urmă, patru este ultim element nesortate. Deci vom deoparte, trecerea peste elementele trebuie să se mute peste, și a pus apoi patru în cazul în care acesta face parte. Și acum uite, am un fel a tuturor elementelor. Observați cu inserție sortare, nu am avut pentru a merge înainte și înapoi pe matrice. Ne-am dus doar peste matrice o singură dată, și am mutat lucrurile că am întâlnit deja, în scopul de pentru a face loc pentru elementele noi. 

Deci, ce este cel mai rău caz scenariu cu inserție fel? În cel mai rău caz, matrice este în ordine inversă. Trebuie să schimbe fiecare dintre n elemente până la n poziții, fiecare ne-am dată face o inserție. Asta-i o mulțime de schimbare. 

În cel mai bun caz, matrice este sortata perfect. Și un fel de ceea ce sa întâmplat cu cinci și șase în exemplul, în cazul în care am putea doar tac pe fără a fi nevoie de a face orice schimbare, am face în esență, că. 

Dacă vă imaginați că nostru matrice a fost unul prin șase, am începe prin declararea unul este sortate. Două vine dupa o astfel încât să putem doar spune, OK, bine unul și două sunt sortate. Trei vine după două astfel, OK, unu și doi și trei sunt sortate. 

Noi nu facem nici un swap-uri, suntem doar în mișcare această linie arbitrară între sortati si nesortate ca mergem. La fel de eficient cum am făcut în exemplul, cotitură elemente albastru, așa cum vom proceda. Deci, ce este cel mai rău caz Runtime, atunci? Amintiți-vă, dacă trebuie să schimbe fiecare dintre N elementele eventual n pozitiile, sperăm că vă oferă o idee care cel mai rau caz rulare este O mare de n pătrat. 

În cazul în care matricea este perfect sortate, tot ce trebuie să facem este sa te uiti la fiecare singur element o dată, și apoi am terminat. Deci, în cel mai bun caz, este de omega n. 

Sunt Doug Lloyd. Acest lucru este CS50.