[Powered by Google Translate] [Sapludināšana Sakārtot] [Rob Bowden - Hārvarda] [Tas ir CS50. - CS50.TV] Parunāsim par sapludināšanas kārtošanas. Līdz šim jūs esat redzējis burbulis šķirot, ievietošanas kārtot un atlases veida. Kaut gan es ņemšu veida vilnis savu roku pie ko es domāju, labāk, sapludināt kārtošanas parasti veic labāk nekā jebkurš no šiem 3 veidu. 

Bet pirms runāt par sapludināšanas kārtot, parunāsim par apvienojot 2 sakārtoti sarakstus. Mēs saucam procesu ņemot 2 sakārtoti sarakstus, piemēram, šiem, un pieņemt vienotu sakārtoti sarakstu no tiem - apvienojot sarakstus. Kā mēs varam darīt? Nu, viena ideja ir vienkārši brauciet vienu sarakstu uz beigām cita saraksta un tad šķirot iegūto sarakstu. 

Kamēr tas darbojas, tas ir daudz nevajadzīgu darbu. Mēs varam darīt to ātrāk, nekā vienkārši šķirošanu. Ievērojiet, ka viens nepareizs ideja ir vienkārši ņemt pārmaiņus tases no katra saraksta. Kaut kas var šķist, ka darbu pie pirmā, darot, ka mēs galu galā ar 4, 8, 15, 23, 16 - paziņojums, ka 16 un 23 ir nevietā. Tas ir tāpēc, ka 2 elementi, kuri jāiekļauj pēc kārtas šajā apvienotā sarakstā ir vienā sākotnējā sarakstā. Gan 15 un 16 ir sarakstā pa kreisi. Triks ir, lai izmantotu to, ka abas saraksti jau ir sakārtots. Tas nozīmē, ka, ja mēs tikai apskatīt pirmo elementu abu sarakstos - šeit, 4 un 8 - viens no tiem ir arī pirmais elements apvienotā saraksta. Nu, kāpēc tā? Abi no šiem sarakstiem ir jau sakārtoti, un tā nu 4 vai 8 jābūt mazākais elements, ja mēs apvienojam arī 2 sarakstus. Šajā gadījumā, mazākais ir 4, lai mēs varētu izņemt 4 un padara to par pirmo elements mūsu apvienotā saraksta. Tagad mēs turpināsim apvienot atlikušās 3 elementiem pirmajā sarakstā un 4 elementi Otrajā sarakstā. 

Atkal, mēs tikai nepieciešams apskatīt pirmo elementu abu saraksti. Gada 2 mazākas jābūt otrais elements mūsu apvienotā saraksta. Šoreiz, no 8 līdz 15 mazākais ir 8, un tāpēc mēs ievietot, ka kā otro elementu mūsu sakārtotās sarakstā. Mēs varam turpināt salīdzinot pirmos elementus abos sarakstos un novēršot mazāko no 2. Salīdzinot 15 un 23, 15 ir mazāks un tā tas ir mūsu trešais elements. Tagad salīdzinot 16 un 23, 16 ir mazāka. Tā ka ceturtais elements. 

Ievērojiet, ka 2 elementi nāca no tā paša saraksta kārtas. Tas ir iemesls, kāpēc apvienotais saraksts nevar vienkārši mijas elementi no 2 sarakstiem. Salīdzinot 50 un 23, 23 ir mazāks, tāpēc mēs izvēlamies to. Starp 50 un 42, 42 ir mazāka. Starp 50 un 108, 50 ir mazāka. Un, visbeidzot, mēs vienkārši ir 108, tāpēc ir jāiet uz beigām mūsu sarakstā. Ievērojiet, ka mums ir jauka, sakārtoti sarakstu. Katru reizi, kad mēs salīdzinot pirmos 2 elementus no 2 sarakstiem mums bija iespēja noteikt nākamo elementu apvienotā saraksta. Tas nozīmē, ka, ja galīgais saraksts ietver n skaitļus, kur n šeit ir 8, tad mums vajag ne vairāk n salīdzinājumus, lai iegūtu visus šos numurus īstajā vietā. Šāds algoritms ir teikt palaist lineārā laika, bet nav jāuztraucas par to šeit. 

Izmantojot mūsu algoritms, kas apvienojas, mēs varam veikt ātri sapludināšanas kārtošanas algoritms. Tātad, pieņemsim reset mūsu sarakstus. Ir 2 lieli soļi procesā sapludināšanas kārtošanas. Pirmkārt, nepārtraukti sadalīt sarakstu tases uz pusēm līdz mums ir ķekars sarakstos tikai ar 1 glāzi tiem. Neuztraucieties, ja sarakstā ir nepāra skaits un jūs nevarat veikt pilnīgi tīru griezumu starp tiem. Tikai patvaļīgi izvēlēties, kuras sarakstā iekļaut papildu tasi iekšā Tātad, pieņemsim sadalīt šos sarakstus. Tagad mums ir 2 saraksti. Tagad mums ir 4 sarakstus. 

Un tagad mums ir 8 saraksti ar vienu tasi katrā sarakstā. Tā ka tas uz 1 soli. Par 2 soli, mēs vairākkārt apvienot pārus saraksti, izmantojot sapludināšanas algoritmu mēs uzzinājām pirms tam. Apvienojot 108 un 15, mēs galu galā ar sarakstu 15, 108. Apvienojot 50 un 4, mēs galu galā ar 4, 50. Apvienojot 8 un 42, mēs galu galā ar 8, 42. Un apvienojot 23 un 16, mēs galu galā ar 16, 23. Tagad visi mūsu saraksti ir 2 izmēru. Ievērojiet, ka katrā no 4 sarakstiem ir sakārtots. 

Lai mēs varētu sākt apvienojot pārus sarakstos atkal. Apvienojot 15 un 108 un 4 un 50 - vispirms veic 4, tad 15, tad 50, tad 108. Apvienojas 8, 42 un 16, 23, mēs vispirms veikt 8, tad 16, tad 23, tad 42. Tāpēc tagad mums ir tikai 2 saraksti 4 izmēra, no kuriem katrs ir sakārtots. Tāpēc tagad mēs apvienot šos 2 sarakstus. Vispirms mēs veikt 4. Tad mēs to 8. Tad mēs veikt 15 līdz 16, tad 23, tad 42, tad 50, tad 108. Un mēs esam darīts. Mums tagad ir sakārtoti sarakstu. Tātad, cik ātri bija tas, tieši? Tehniskā ziņā, apvienot kārtošanas ir O (n log n), tā kā viss burbulis šķirot, ievietošanas šķirot, un atlases veida ir O (n ²). Patiesībā, kā jūs uzzināsiet drīz, jums nebūs iespēja nākt klajā ar sava veida kas veic labāk nekā O (n log n) vispārējā gadījumā. Atkal, nav jāuztraucas par šo lielo O notācija ja neesat to redzējuši vēl. 

Tikai zinu, ka tas nozīmē, ja mēs vēlējāmies, lai kārtotu tiešām liels sarakstu burbulis kārtot, ievietošanas šķirot, un izvēle kārtot potenciāli varētu veikt ievērojami pārsniedz apvienot šķirot. Tas nenozīmē, ka sapludināšanas kārtošanas būs ātrāk par visiem sarakstiem vai pat kādu vienotu sarakstu ar noteiktu lielumu. Piemēram, ievietošanas šķirot varētu būt ātrākais šķirot visus sarakstus mazākiem nekā 5 elementiem. Praksē sapludināšanas kārtošanas parasti ir ātrāk sarakstiem kā maza kā 50 elementi. 

Bet tas papildus ātrums nenāk bez cenu. Atšķirībā no mūsu cita veida, kas ņem sarakstu un grozīt sarakstu vietā kamēr mēs sakārtoti sarakstu, apvienot kārtot vajadzīgas dažas papildu telpu apvienot 2 saraksti kopā. Mēs nevaram uzreiz izmantot sarakstus, kas tiek apvienotas, lai saglabātu šo radušos sarakstu jo mēs varētu ignorēt elementus, kas vēl ir jāapvieno. Šī telpa ir mazliet par cenu, bet tas parasti nav nepamatota. Un tas ir tas, lai sapludināšanas kārtošanas. 

Mans vārds ir Rob Bowden, un tas ir CS50. [CS50.TV] - Un atlase šķirot. [Smejas] Ak, ieguva veikt, ka, pārāk, jo es pārslēdz kā es to iepazīstināt. Sarakstā pa kreisi. Tas bija typo. [Misspoke] Es ieskrūvē - [Smejas] Es nezinu, ko -