[Powered by Google Translate] TOMMY: Pieņemsim to apskatīt atlases veida, algoritmu
par tādu sarakstu numurus un šķirošanu.
Algoritms, atcerieties, ir vienkārši soli pa solim
procedūra Veicot uzdevumu.
Pamatideja atlases veida ir sadalīt
Mūsu sarakstā divās daļās -
sakārtoti daļu un nešķirotiem porciju.
Katrā posmā no algoritma, numurs tiek pārvietots no
nešķiroti daļa uz sakārtotās daļu līdz beidzot
viss saraksts ir sakārtots.
Tātad, šeit ir seši numuru saraksts -
23, 42, 4, 16, 8, 15 un.
Tieši tagad viss saraksts tiek uzskatīts nešķirotu.
Kaut gan, piemēram, 16 numuru var jau būt tā pareizs
vieta, mūsu algoritms ir nekādi nevar zināt, ka līdz
viss saraksts ir sakārtots.
Tātad mēs izskatīsim katru numurs ir nešķiroti līdz mēs sakārtot
tā sevi.
Mēs zinām, ka mēs vēlamies saraksts būtu augošā secībā.
Tāpēc mēs vēlamies veidot kārtotas daļu no mūsu saraksta
no kreisās uz labo, mazākā uz lielāko.
Lai to izdarītu, mums ir nepieciešams, lai atrastu minimālo nešķirotu elements
un nodot to beigās no sakārtotās daļu.
Tā kā šis saraksts nav sakārtots, tad vienīgais veids, kā to darīt, ir
apskatīt katru elementu ar nešķirotiem daļu, atceroties
kas elements ir zemākais un salīdzinot
katrs elements tam.
Tāpēc mēs vispirms apskatīt 23.
Šis ir pirmais elements, mēs esam redzējuši, tāpēc mēs atcerēties
tā kā minimums.
Nākamais mēs apskatīt 42.
42 ir lielāks par 23, tāpēc 23 ir vēl minimums.
Nākamais ir 4, kas ir mazāk nekā 23, tāpēc mēs atcerēties 4
kā jaunu minimumu.
Nākamais ir 16, kas ir lielāks par 4, SO 4
joprojām ir minimums.
8 ir lielāks par 4, un 15 ir lielāks par 4, SO 4 jābūt
mazākais nešķiroti elements.
Tātad, pat ja kā cilvēkiem mēs varam uzreiz redzēt, ka 4 ir
minimālais elements, mūsu algoritms ir apskatīt
Katru nešķirotiem elements, pat pēc mēs esam atraduši 4 -
minimālās elements.
Tāpēc tagad, ka mēs esam atraduši minimālo elementu, 4, mēs vēlamies
lai to pārvietotu uz sakārtoti daļu sarakstu.
Tā kā šis ir pirmais solis, tas nozīmē, ka mēs vēlamies likt 4 pie
sākums saraksta.
Šobrīd 23 ir sākumā sarakstu, lai
pieņemsim mijmaiņas 4 un 23.
Tātad tagad mūsu saraksts izskatās šādi.
Mēs zinām, ka 4 ir jābūt tās galīgajā vietā, jo tas ir
gan mazākais elements un elements sākumā
no saraksta.
Tātad tas nozīmē, ka mums nav kādreiz nepieciešams, lai pārvietotu to vēlreiz.
Tāpēc pieņemsim atkārtot šo procesu, lai pievienotu citu elementu
sakārtoti daļu saraksta.
Mēs zinām, ka mums nav nepieciešams apskatīt 4, jo tas ir
jau ir sakārtoti.
Lai mēs varētu sākt 42, ko mēs atcerēties kā
minimālās elements.
Tātad nākamais mēs apskatīt no 23, kas ir mazāk nekā 42, tāpēc mums
atcerieties 23 ir jauns minimums.
Tālāk mēs redzēt 16, kas ir mazāk nekā 23, tāpēc
16 ir jauns minimums.
Tagad mēs skatāmies 8, kas ir mazāk nekā 16, tāpēc
8 ir jauns minimums.
Un visbeidzot 8 ir mazāk nekā 15, lai mēs zinām, ka 8 ir minimālā
nešķiroti elements.
Tātad tas nozīmē, ka mums vajadzētu pievienot 8 līdz sakārtoti
daļa no saraksta.
Tieši tagad 4 ir vienīgais sakārtoti elements, tāpēc mēs vēlamies ievietot
8 blakus 4.
Tā 42 ir pirmais elements nešķirotu daļu no
sarakstu, mēs vēlamies, lai apmainītu 42 un 8.
Tātad tagad mūsu saraksts izskatās šādi.
4 un 8 pārstāv kārtotas daļu sarakstu, un
pārējie skaitļi atspoguļo nešķirotiem
daļa no saraksta.
Tāpēc pieņemsim turpināt ar citu atkārtojuma.
Mēs sākam ar 23 šoreiz, jo mums nav nepieciešams apskatīt
4 un 8 vairs jo tie esam
jau sakārtots.
16 ir mazāk nekā 23, tāpēc mēs atcerēties
16 kā jaunu minimumu.
16 ir mazāk nekā 42, bet 15 ir mazāk nekā 16, tāpēc 15 ir jābūt
minimālo nešķiroti elements.
Tāpēc tagad mēs vēlamies, lai apmainītu 15 un no 23 līdz
dod mums šo sarakstu.
Sakārtošanas daļa saraksts sastāv no 4, 8 un 15, un
šie elementi joprojām nešķirotu.
Bet tas tikai tā notiek, ka nākamais nešķirotu elements, 16,
jau sakārtots.
Tomēr, tur nav veids, kā mūsu algoritms zināt, ka 16
jau to pareizajā vietā, tāpēc mums vēl ir nepieciešams, lai
atkārtot tieši to pašu procesu.
Tātad mēs redzam, ka 16 ir mazāk nekā 42, un 16 ir mazāk nekā 23, tāpēc
16 jābūt vismaz elements.
Tas ir neiespējami apmainīt šo elementu ar sevi, lai mēs varam
vienkārši atstāt to šajā vietā.
Tāpēc mums ir nepieciešams vēl vienu piespēli no mūsu algoritms.
42 ir lielāks par 23, tāpēc 23 ir jābūt
Minimālā nešķiroti elements.
Kad mēs mijmaiņas 23 un 42, mēs galu galā ar mūsu gala
sakārtoti sarakstā -
4, 8, 15, 16, 23, 42.
Mēs zinām, 42 ir jābūt pareizajā vietā, jo tas ir
Vienīgais elements kreisi, un tas ir izvēle veida.
Pieņemsim tagad formalizēt mūsu algoritms ar dažām
pseudocode.
Vienā rindā, mēs varam redzēt, ka mums ir nepieciešams integrēt pār
katrs elements sarakstā.
Izņemot pēdējo elementu, jo 1 elements
Saraksts ir jau sakārtots.
Uz diviem līnijas, mēs uzskatām pirmo elementu nešķirotiem
daļa sarakstā ir minimālais, kā mēs to darījām ar mūsu
Piemēram, lai mēs kaut ko salīdzināt ar.
Līnija 3 sāk otru cilpu, kurā mēs atkārtot pāri
Katru nešķiroti elements.
Mēs zinām, ka pēc tam es iterācijās, sakārtoti daļa
Mūsu sarakstā ir jābūt i elementi tajā kopš katra soļa
sakārto viens elements.
Tātad pirmais nešķiroti elementam jābūt tādā stāvoklī, es plus 1.
Uz četriem līniju, mēs salīdzināt pašreizējo elementu līdz minimumam
elements, ka mēs esam redzējuši līdz šim.
Ja pašreizējais elements ir mazāks par minimālo
elements, tad mēs atcerēties esošo elements, jo jaunais
Minimālā uz pieciem rindā.
Visbeidzot, uz līnijām seši un septiņi, mēs swap minimālo
elements ar pirmo nešķirotu elementa, tādējādi
pievienojot to sakārtoti daļu sarakstu.
Kad mums ir algoritms, svarīgs jautājums, ko uzdot
sevi par programmētāju, cik ilgi tas veic?
Mēs vispirms uzdot jautājumu, cik ilgi tas veic, lai šis
algoritms, lai palaistu sliktākajā gadījumā?
Atceros mēs pārstāvam šo darbību
laiks ar Big O notācija.
Lai noteiktu minimālo nešķirotu elementu, mēs
būtībā bija salīdzināt katru elementu sarakstā uz
katru otro elementu sarakstā.
Intuitīvi, tas izklausās n brusas darbības O.
Skatoties uz mūsu pseudocode, mums ir arī cilpa ligzdotas
cits cilpa, kas tiešām izklausās O
gada n brusas darbību.
Tomēr atcerieties, ka mums nav nepieciešams apskatīt
viss saraksts, nosakot minimālo nešķirotu elements?
Kad mēs zinājām, ka 4 tika sakārtoti, piemēram, mums nav
vajag paskatīties uz to vēlreiz.
Tātad dara zemākas darbības laiku?
Mūsu sarakstu 6 garums, mums vajadzēja padarīt piecas
salīdzinājumi par pirmo elementu, četras salīdzinājumus
Otrais elements, un tā tālāk.
Tas nozīmē, ka kopējais skaits soļiem ir summa
integers no 1 līdz garumā 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 reizes
n mīnus nekā 2 1.
Vai līdzvērtīgi, n rūtiņām vairāk nekā 2 mīnus n nekā 2.
Ja runājam par asimptotiskās runtime, šis n brusas termins
gatavojas dominēt šo n terminu.
Tātad izvēle veida ir O no n rūtiņām.
Atgādināt, ka mūsu piemēram, atlase kārtot vēl vajag
pārbaudiet, vai numurs, kas bija jau sakārtoti
nepieciešams pārvietot.
Tātad tas nozīmē, ka, ja mēs ilga atlases veida pār jau
sakārtoti sarakstā, tas būs nepieciešams tas pats vairākus pasākumus, kā to
būtu braucot pa pilnīgi nešķirotiem sarakstā.
Tātad izvēle šķirot ir labākajā gadījumā sniegumu n brusas,
kas mēs pārstāvam ar omega n brusas.
Un tas ir tas, lai atlases veida.
Tikai viens no daudziem algoritmu mēs varam
izmantot, lai kārtotu sarakstu.
Mans vārds ir Tommy, un tas ir CS50.