[Powered by Google Translate] [Iekļaut Sakārtot]
[Tomijs MacWilliam] [Hārvarda]
[Tas ir CS50.TV]
Pieņemsim to apskatīt ievietošanas veida, algoritms ņemot sarakstu numurus un šķirošanu.
Algoritms, atcerieties, ir vienkārši soli pa solim procedūru pabeigšanai uzdevumu.
Pamatideja ievietošanas veida, ir sadalīt savu sarakstu divās daļās,
sakārtoti daļu un nešķirotiem porciju.
>> Katrā posmā no algoritma, numurs tiek pārvietots
no šķirotus daļas uz sakārtotās daļu
līdz beidzot viss saraksts ir sakārtots.
Šeit ir seši nešķirotu numuru saraksts - 23, 42, 4, 16, 8, 15 un.
Tā kā šie skaitļi ir ne visi augošā secībā, viņi nešķirotu.
Kopš mēs neesam sākuši šķirošana vēl, mēs ņemsim vērā visas sešiem elementiem mūsu nešķirotu porciju.
>> Kad mēs sākam šķirošana, mēs nodot šos sakārtoti skaitļus pa kreisi no tiem.
Tātad, sāksim ar 23, pirmais elements mūsu sarakstā.
Mums nav nekādas elementi mūsu sakārtotās daļu vēl,
tāpēc pieņemsim vienkārši uzskatu 23 kā sākums un beigas mūsu šķiroto porciju.
Tagad mūsu sakārtoti daļa ir viens numurs, 23,
un mūsu nešķiroti daļa ir šīs pieci numuri.
Pieņemsim tagad ievietot nākamo numuru mūsu nešķirotu daļu, 42, uz sakārtotās daļu.
>> Lai to izdarītu, mums ir nepieciešams, lai salīdzinātu 42-23 The - vienīgais elements mūsu šķiroto daļā līdz šim.
Četrdesmit divi ir lielāks par 23, lai mēs varētu vienkārši pievienot 42 līdz gada beigām
no sakārtoti daļas sarakstā. Lieliski!
Tagad mūsu sakārtoti daļa ir divas elementi, un mūsu nešķiroti daļa ir četri elementi.
Tātad, pieņemsim tagad pāriet uz 4, nākamais elements nešķirotiem daļu.
Tātad, ja tas būtu ievietots sakārtotās daļu?
>> Atcerieties, mēs vēlamies ievietot šo numuru sakārtoti secībā
tāpēc mūsu sakārtoti daļa paliek pareizi šķirot to visu laiku.
Ja mēs vieta 4 uz tiesībām uz 42, tad mūsu saraksts būs bojātas.
Tātad, pieņemsim turpināt pārvietojas no labās uz kreiso mūsu kārtošanas daļu.
Kā mēs virzāmies, pieņemsim pāriet katru numuru uz leju vietā, lai atbrīvotu vietu jaunajai numuru.
Labi, 4 ir arī mazāk nekā 23, tāpēc mēs nevaram ievietot to šeit, vai nu.
Pāriesim no 23 pareizo vienu vietu.
>> Tas nozīmē, ka mēs gribētu, lai novietotu 4 par pirmo spraugā sakārtotās daļu.
Paziņojums, kā tas sarakstā telpa bija jau tukša,
jo mēs esam pārvietojas sakārtotās elementi noteikti kā mēs esam saskārušās tos.
Labi. Tātad, mēs esam pusceļā tur.
Turpināsim mūsu algoritmu, ievietojot 16 uz sakārtotās daļu.
Sešpadsmit ir mazāks par 42, tāpēc pieņemsim pāriet, 42 pa labi.
Sešpadsmit ir mazāk nekā 23, tāpēc pieņemsim arī novirzīt šo elementu.
>> Tagad, 16 ir lielāks par 4. Tātad, izskatās, ka mēs gribētu, lai ievietotu 16 starp 4 un 23.
Pārvietojoties pa sakārtoti daļu saraksts, no labās uz kreiso,
4 ir pirmais numurs, mēs esam redzējuši, ka ir mazāks nekā skaits
Mēs cenšamies, lai ievietotu.
Tātad, tagad mēs varam ievietot 16 šajā slotā,
kas, atcerieties, mēs esam izveidojuši ar kustīgiem elementiem kārtošanas daļu virs
kā mēs esam konstatējuši tos.
>> Labi. Tagad mums ir četras sakārtotās elementi un divas nešķirotas elementus.
Tātad, pieņemsim pārvietojiet 8 uz sakārtotās daļu.
Astoņi ir mazāk kā 42.
Astoņi ir mazāk nekā 23.
Un 8 ir mazāk nekā 16.
Bet 8 ir lielāks par 4.
Tātad, mēs gribētu, lai ievietotu 8 starp 4 un 16.
Un tagad mums vienkārši ir vēl viens palicis elementu, lai kārtotu - 15.
Piecpadsmit ir mazāk nekā 42,
Piecpadsmit ir mazāk nekā 23.
Un 15 ir mazāk nekā 16.
Bet 15 ir lielāks par 8.
>> Tātad, šeit ir tas, kur mēs vēlamies, lai mūsu gala ievietošanu.
Un mēs esam darīts.
Mums nav vairāk elementus nešķirotu daļu,
un mūsu sakārtoti daļa ir pareizā secībā.
Skaitļi ir pasūtīts no vismazākās līdz lielākajam.
Tātad, pieņemsim apskatīt dažas pseudocode kas apraksta soļus mēs vienkārši veikti.
>> Gada 1 līniju, mēs varam redzēt, ka mums būs nepieciešams atkārtot pār katru elementu sarakstā
izņemot pirmo, jo pirmais elements nešķirotu daļa būs vienkārši kļūs
pirmais elements sakārtotās daļu.
Līnijās 2 un 3, mēs sekotu mūsu pašreizējo vietu nešķirotiem daļu.
Elements atbilst skaitlim mēs šobrīd virzās uz sakārtotās daļu,
un j pārstāv mūsu rādītāju uz nešķirotu daļu.
>> Gada 4 līnijas, mēs atkārtojot caur sakārtotās daļu no labās uz kreiso.
Mēs vēlamies, lai apturētu atkārtojot reizi elementam kreisi no mūsu pašreizējās pozīcijas
ir mazāks nekā elements mēs cenšamies ievietot.
Gada 5 līnijas, mēs novirzot katru elementu mēs saskaramies vienu vietu pa labi.
Tādā veidā, mums būs skaidrs telpu ievietot, kad mēs atrast pirmo elementu
mazāk nekā elements mēs pārvietojas.
Gada 6 līniju, mēs atjaunināt mūsu skaitītāju turpināt virzīties uz kreisi pa sakārtotās daļu.
Visbeidzot, attiecībā uz 7 līnijā, mēs esam ievietojot elementu vērā sakārtoti daļu sarakstu.
>> Mēs zinām, ka tas ir labi, lai ievietotu stāvoklī J,
jo mēs esam jau pārvietots uz elementu, kas izmanto, lai būtu tur viena telpa pa labi.
Atcerieties, mēs esam pārvietojas pa sakārtotās daļu no labās uz kreiso,
bet mēs esam pārvietojas pa nešķirotu daļu no kreisās uz labo pusi.
Labi. Pieņemsim tagad to apskatīt, cik ilgi darbojas, ka algoritms ņēma.
Mēs vispirms uzdot jautājumu, cik ilgi tas veic, lai šis algoritms palaist sliktākajā gadījumā.
Atgādināt, ka mēs pārstāvam šo darbības laiku ar Big O notācija.
Lai sakārtotu mūsu sarakstu, mums bija atkārtot pāri elementus nešķirotu daļu,
un katram no šiem elementiem, potenciāli vairāk nekā visiem šķiroto daļu elementiem.
Intuitīvi, tas izklausās O (n ^ 2) darbību.
>> Skatoties uz mūsu pseudocode, mums ir cilpa ligzdotas citam cilpas,
kas, protams, izklausās O (n ^ 2) darbību.
Tomēr sakārtoti daļa saraksta neietvēra visu sarakstu, līdz pašām beigām.
Tomēr, mēs, iespējams, varētu ievietot jaunu elementu pašā sākumā sakārtotās daļu
par katru atkārtojuma no algoritma,
kas nozīmē, ka mēs ir jāskatās uz katru elementu pašlaik sakārtotās daļu.
Tātad, tas nozīmē, ka mēs, iespējams, varētu iesniegt vienu salīdzinājumu par otro elementu,
divi salīdzinājumi par trešo elementu, un tā tālāk.
Tātad, kopējais skaits soļiem ir summa integers no 1 līdz garumu saraksta mīnus 1.
Mēs varam pārstāvēt šo ar summēšanā.
>> Mēs ne iedziļināties summations šeit, bet izrādās, ka tas sasummēt ir vienāds ar
n (n - 1) vairāk nekā 2, kas ir līdzvērtīgs n ^ 2/2 - N / 2.
Ja runājam par asimptotiskās runtime,
Šī n ^ 2 termins gatavojas dominēt šo n terminu.
Tātad, ievietošanas kārtošanas ir Big O (n ^ 2).
Ko darīt, ja mums bija ievietošanas Šķirot jau šķiroto sarakstā.
Šajā gadījumā mēs vienkārši veidot kārtotas daļu no kreisās uz labo pusi.
Tātad, mēs tikai nepieciešams par kārtību n soļiem.
>> Tas nozīmē, ka ievietošana šķirot ir labākajā gadījumā sniegumu n,
kas mēs pārstāvam ar Ω (n).
Un tas ir tas, lai ievietošanas šķirot,
tikai viens no daudziem algoritmu, mēs varam izmantot, lai sakārtotu sarakstu.
Mans vārds ir Tommy, un tas ir CS50.
[CS50.TV]
Ak, jūs vienkārši nevar pārtraukt ka reiz tas sākas.
Ak, mēs to izdarījām, - >> Boom!