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