[Powered by Google Translate] [După Insertion]
[Tommy MacWilliam] [Universitatea Harvard]
[Acest lucru este CS50.TV]
Să aruncăm o privire la fel de inserare, un algoritm pentru a lua o listă de numere și sortarea lor.
Un algoritm, amintiți-vă, este pur și simplu o procedură pas-cu-pas pentru realizarea unei sarcini.
Ideea de bază din spatele fel de inserare, este de a împărți lista noastră de în două tranșe,
o parte sortati si o parte nesortate.
>> La fiecare pas al algoritmului, un număr este mutat
din partea nesortate la porțiunea sortate
până când în cele din urmă intreaga lista este sortată.
Iată lista cu șase numere nesortate - 23, 42, 4, 16, 8, și 15.
Întrucât aceste numere nu sunt în ordine crescătoare, acestea sunt sortate.
Din moment ce nu am început încă de sortare, vom lua în considerare toate cele șase elemente de partea noastră nesortate.
>> Odată ce vom începe sortarea, vom pune aceste numere sortate la stânga dintre acestea.
Deci, să începem cu 23, primul element din lista noastră.
Noi nu avem nici un element din partea noastră sortate încă,
așa că hai să ia în considerare pur și simplu să fie 23 începutul și sfârșitul partea noastră sortate.
Acum, partea noastră sortate are un număr, 23,
și partea noastră nesortate are aceste cinci numere.
Să se introduce acum urmatorul numar din partea noastră nesortate, 42, în partea sortate.
>> Pentru a face acest lucru, vom avea nevoie pentru a compara 42 până la 23 - singurul element din partea noastră sortate până în prezent.
Patruzeci și doi este mai mare decât 23, astfel încât să putem adăuga pur și simplu la 42 la sfârșitul anului
de porțiunea de sortat lista. Minunat!
Acum partea noastră are două elemente sortate, iar partea noastră nesortate are patru elemente.
Deci, să trecem acum la 4, urmatorul element din partea nesortata.
Deci, în cazul în care ar trebui să fie plasate în această porțiune sortate?
>> Amintiți-vă, vrem să pună acest număr, în ordine sortate
astfel încât partea noastră rămâne sortate în mod corect sortate în orice moment.
Dacă punem 4 la dreapta 42, atunci lista noastră va fi în ordine.
Deci, hai să continue să acționeze de la dreapta la stânga, în partea de sortare nostru.
Pe masura ce inaintam, să transfere fiecare număr în jos un loc pentru a face loc pentru noul număr.
Bine, 4 este, de asemenea, mai puțin de 23, deci nu-l putem plasa nici aici.
Să trecem 23 dreptul de-un singur loc.
>> Asta înseamnă că am dori să plasați 4 în primul slot din partea sortate.
Observați cum acest spațiu în lista era deja gol,
pentru că am fost în mișcare elemente sortate după cum le-am întâlnit.
Bine. Deci, suntem la jumătatea drumului.
Să continuăm algoritmul nostru prin inserarea în 16 porțiunea sortate.
Șaisprezece este mai mică de 42, asa ca hai sa transfere 42 la dreapta.
Șaisprezece este, de asemenea, mai puțin de 23, asa ca hai sa schimba, de asemenea, că acest element.
>> Acum, 16 este mai mare de 4. Deci, se pare ca ne-am dori pentru a insera 16 dintre 4 și 23.
În timp ce se deplasează prin porțiunea de sortat lista de la dreapta la stânga,
4 este primul număr am văzut că este mai mic decât numărul
încercăm să inserați.
Deci, acum putem introduce 16 in acest slot gol,
care, amintiți-vă, am creat cu elemente în mișcare în partea de sortare de peste
cum le-am întâlnit.
>> Bine. Acum, avem patru elemente sunt sortate și două elemente nesortate.
Deci, să trecem în partea 8 sortate.
Opt este mai mică de 42.
Opt este mai mică de 23.
Și 8 este mai mică de 16.
Dar 8 este mai mare de 4.
Deci, am dori pentru a insera 8 dintre 4 și 16.
Și acum avem doar un element mai rămas pentru a sorta - 15.
Cincisprezece este mai mică de 42,
Cincisprezece este mai mică de 23.
Și 15 este mai mică de 16.
Dar 15 este mai mare de 8.
>> Deci, aici este locul unde dorim să facem inserarea nostru final.
Și am terminat.
Noi nu avem mai multe elemente în partea nesortate,
și partea noastră este sortate în ordinea corectă.
Numerele sunt ordonate de la cel mai mic la cel mai mare.
Deci, haideți să aruncăm o privire la unele pseudocod, care descrie pașii ne-am efectuat.
>> Pe linia 1, putem vedea că vom avea nevoie pentru a itera peste fiecare element din listă
cu excepția primei, deoarece primul element din partea nesortata va deveni pur și simplu
primul element în porțiunea sortate.
Pe liniile 2 și 3, suntem urmărirea locul nostru curent în porțiunea nesortate.
Element reprezintă numărul suntem în prezent se deplasează în partea sortate,
și j reprezintă indexul nostru în porțiunea nesortate.
>> Pe linia 4, suntem iterarea prin porțiunea sortate de la dreapta la stânga.
Ne dorim să oprim iterarea o dată elementul la stânga poziției noastre actuale
este mai mică decât elementul noi încercăm să inserați.
Pe linia 5, suntem schimbarea fiecarui element ne întâlnim cu un spațiu la dreapta.
În acest fel, vom avea un spațiu liber pentru a insera în când vom găsi primul element
mai puțin elementul ne mișcăm.
Pe linia 6, suntem actualizarea contra noastră de a continua să se deplaseze lăsat prin porțiunea sortate.
În cele din urmă, pe linia 7, vom introduce elementul în partea de sortat lista.
>> Știm că e în regulă să inserați în poziția j,
pentru că ne-am mutat deja elementul care a folosit pentru a fi acolo un spațiu la dreapta.
Amintiți-vă, ne mișcăm prin porțiunea sortate de la dreapta la stânga,
dar ne mișcăm prin porțiunea nesortate de la stânga la dreapta.
Bine. Să aruncăm acum o privire la modul de mult de rulare, care a avut algoritm.
Vom întreba mai întâi întrebarea cât timp durează pentru acest algoritm pentru a rula în cel mai rău caz.
Reamintească faptul că ne reprezintă de această dată de rulare cu notația Big O.
În scopul de a sorta lista noastră, am avut pentru a itera peste elementele din partea nesortate,
și pentru fiecare dintre aceste elemente, cu potențial peste toate elementele din partea sortate.
Intuitiv, acest lucru sună ca un O (n ^ 2) operațiunea.
>> Privind la pseudocod nostru, avem o buclă imbricată într-o altă buclă,
care, într-adevăr, sună ca un O (n ^ 2) operațiunea.
Cu toate acestea, partea sortate de listă nu conține întreaga listă până la sfârșitul foarte.
Cu toate acestea, am putea introduce un element nou potential, la începutul porțiunii sortate
pe fiecare iterație a algoritmului,
ceea ce înseamnă că vom avea să se uite la fiecare element prezent în porțiunea sortate.
Deci, asta înseamnă că am putea face o comparatie potential pentru al doilea element,
două comparații pentru al treilea element, și așa mai departe.
Deci, numărul total de pași este suma intregi de la 1 la lungimea listei minus 1.
Ne putem reprezenta acest lucru cu o însumare.
>> Nu vom intra în somații aici, dar se pare că acest lucru este egal cu însumării
n (n - 1) pe 2, ceea ce este echivalent cu n ^ 2/2 - n / 2.
Atunci când vorbim despre timpul rulării asimptotică,
acest termen n ^ 2 este de gând să domine acest termen nr.
Deci, un fel de inserare este Big O (n ^ 2).
Ce se întâmplă dacă am alergat un fel inserarea pe o listă deja sortate.
În acest caz, vom construi pur și simplu partea sortate de la stânga la dreapta.
Deci, vom avea nevoie de doar pe ordinea de pași n.
>> Asta înseamnă că un fel de inserare are o performanță mai bună-n caz de,
pe care le reprezintă cu Ω (n).
Și asta e tot pentru sortare inserarea,
doar unul din algoritmii de mai multe le putem folosi pentru a sorta o listă.
Numele meu este Tommy, iar acest lucru este CS50.
[CS50.TV]
Oh, tu chiar nu se poate opri că odată ce începe.
Oh, am făcut asta - Boom >>!