1 00:00:00,000 --> 00:00:02,826 >> [MUSIC nagpe-play] 2 00:00:02,826 --> 00:00:05,660 3 00:00:05,660 --> 00:00:09,370 >> DOUG LLOYD: So-uuri ay isa pang algorithm maaari naming gamitin upang ayusin ang isang array. 4 00:00:09,370 --> 00:00:12,350 Ang ideya sa likod ng algorithm na ito ay upang bumuo ng iyong pinagsunod-sunod array 5 00:00:12,350 --> 00:00:19,670 sa lugar, paglilipat mga elemento sa labas ng ang paraan na ikaw ay pupunta, upang gumawa ng room. 6 00:00:19,670 --> 00:00:22,240 Ito ay bahagyang naiiba mula sa pagpili ng uri o bubble 7 00:00:22,240 --> 00:00:25,460 uri, halimbawa, kung saan na nag-aayos kami ng mga lokasyon, 8 00:00:25,460 --> 00:00:26,910 kung saan ginagawa namin swaps. 9 00:00:26,910 --> 00:00:29,760 >> Sa kasong ito kung ano kami talaga ginagawa ay sliding elemento 10 00:00:29,760 --> 00:00:31,390 sa ibabaw, sa labas ng paraan. 11 00:00:31,390 --> 00:00:34,030 Paano gumagana ang algorithm na ito magtrabaho sa pseudocode? 12 00:00:34,030 --> 00:00:37,646 Well sabihin lang mang sabihin na ang unang elemento ng array ay inayos. 13 00:00:37,646 --> 00:00:38,770 Kami ay gusali na ito sa lugar. 14 00:00:38,770 --> 00:00:42,660 >> Kami ay gonna pumunta ang isang elemento sa isang panahon at bumuo ng mga ito, at kaya ang unang bagay na nakikita namin 15 00:00:42,660 --> 00:00:43,890 ay isang array isang elemento. 16 00:00:43,890 --> 00:00:47,720 At sa pamamagitan ng kahulugan, ang isang isang element ng array ay inayos. 17 00:00:47,720 --> 00:00:50,850 >> Pagkatapos ay magpapadala kami ulitin ang prosesong ito until-- ipapakita namin ulitin ang mga sumusunod na proseso 18 00:00:50,850 --> 00:00:52,900 hanggang ang lahat ng mga elemento ay nakaayos. 19 00:00:52,900 --> 00:00:57,770 Hanapin sa mga susunod unsorted elemento at ipasok ito sa ang pinagsunod-sunod na bahagi, 20 00:00:57,770 --> 00:01:01,209 sa pamamagitan ng paglilipat ng mga kinakailangang bilang ng mga elemento sa labas ng paraan. 21 00:01:01,209 --> 00:01:03,750 Sana ito visualization ay makakatulong sa iyong makita kung ano mismo ang 22 00:01:03,750 --> 00:01:05,980 nangyayari sa mga uri pagpapasok. 23 00:01:05,980 --> 00:01:08,010 >> Kaya muli, narito ang aming buong unsorted array, 24 00:01:08,010 --> 00:01:10,970 lahat ng mga elemento na nakalagay sa red. 25 00:01:10,970 --> 00:01:13,320 At sundin ang mga hayaan mga hakbang ng aming pseudocode. 26 00:01:13,320 --> 00:01:16,970 Ang unang bagay na ginagawa namin, ay tinatawag naming ang unang elemento ng array, pinagsunod-sunod. 27 00:01:16,970 --> 00:01:20,920 Kaya hindi namin lamang gonna sabihin limang, ngayon ikaw ay nakaayos. 28 00:01:20,920 --> 00:01:24,570 >> Pagkatapos namin tumingin sa mga susunod na unsorted elemento ng array 29 00:01:24,570 --> 00:01:27,610 at gusto naming ipasok na sa pinagsunod-sunod na bahagi, 30 00:01:27,610 --> 00:01:29,750 sa pamamagitan ng paglilipat elemento over. 31 00:01:29,750 --> 00:01:33,470 Kaya dalawang ay ang susunod na unsorted element ng array. 32 00:01:33,470 --> 00:01:36,250 Maliwanag na ito ay kabilang sa harap ng limang, kaya kung ano ang hindi namin gonna gawin 33 00:01:36,250 --> 00:01:41,580 ay isang uri ng hawakan ng dalawang tabi para sa isang segundo, maglipat ng limang higit sa, at pagkatapos ay ipasok ang dalawang 34 00:01:41,580 --> 00:01:43,210 bago limang, kung saan upang dapat pumunta. 35 00:01:43,210 --> 00:01:45,280 At ngayon maaari naming sabihin na ang dalawang ito ay pinagsunod-sunod. 36 00:01:45,280 --> 00:01:48,400 >> Kaya bilang maaari mong makita, na namin lamang sa ngayon tumingin sa dalawang mga elemento ng array. 37 00:01:48,400 --> 00:01:50,600 Hindi namin ay tumingin sa mga pamamahinga sa lahat, ngunit hindi namin 38 00:01:50,600 --> 00:01:54,582 Nakakuha ang mga dalawang mga elemento nakaayos ayon sa paraan ng mekanismo paglilipat. 39 00:01:54,582 --> 00:01:56,410 >> Kaya kami ulitin ang proseso muli. 40 00:01:56,410 --> 00:01:58,850 Hanapin sa mga susunod unsorted element, na isa. 41 00:01:58,850 --> 00:02:04,010 Ni-hold na maliban para sa isang segundo, maglipat ng lahat ng bagay sa loob, at ilagay ang isa 42 00:02:04,010 --> 00:02:05,570 kung saan dapat pumunta. 43 00:02:05,570 --> 00:02:08,110 >> Muli, hindi pa rin, na namin lamang kailanman tumingin sa isa, dalawa, lima. 44 00:02:08,110 --> 00:02:12,480 Hindi namin alam kung ano pa ang darating, ngunit inayos na namin ang mga tatlong mga sangkap. 45 00:02:12,480 --> 00:02:16,030 >> Susunod unsorted elemento ay tatlo, kaya kailangan namin i-set ito sa tabi. 46 00:02:16,030 --> 00:02:18,200 Susubukan naming maglipat ng higit sa kung ano ang aming kailangan na kung saan, sa oras na ito 47 00:02:18,200 --> 00:02:21,820 ay hindi lahat ng bagay tulad ng sa nakaraang dalawang mga kaso, ito lang ang lima. 48 00:02:21,820 --> 00:02:25,440 At pagkatapos ay gagamitin namin stick tatlong in, sa pagitan ng dalawa at ang lima. 49 00:02:25,440 --> 00:02:27,849 >> Anim na ang susunod na unsorted elemento sa array. 50 00:02:27,849 --> 00:02:31,140 At sa katunayan anim ay mas higit sa limang, kaya Hindi namin kahit na kailangan na gawin ang anumang pagpapalit. 51 00:02:31,140 --> 00:02:35,710 Maaari lang namin tak anim mismo sa sa ang katapusan ng pinagsunod-sunod na bahagi. 52 00:02:35,710 --> 00:02:38,270 >> Sa wakas, apat ay ang huling unsorted elemento. 53 00:02:38,270 --> 00:02:42,060 Kaya makikita itinakda namin ito sa tabi, magbago sa paglipas ng ang mga elemento na kailangan namin upang maglipat ng higit sa, 54 00:02:42,060 --> 00:02:43,780 at pagkatapos ay ilagay ang apat na kung saan ito kabilang. 55 00:02:43,780 --> 00:02:46,400 At ngayon, tumingin, na namin ng mga uri ng lahat ng mga elemento. 56 00:02:46,400 --> 00:02:48,150 Pansinin na may pagpapasok uri-uriin, hindi namin ay may 57 00:02:48,150 --> 00:02:50,240 upang bumalik-balik sa buong array. 58 00:02:50,240 --> 00:02:54,720 Nagpunta kami lamang ang buong array isang panahon, at Nilipat namin ang mga bagay 59 00:02:54,720 --> 00:02:59,870 na gusto na namin na nakaranas kami, upang para gumawa nang lugar para sa mga bagong elemento. 60 00:02:59,870 --> 00:03:02,820 >> Kaya kung ano ang pinakamasama kaso senaryo sa uri pagpapasok? 61 00:03:02,820 --> 00:03:05,090 Sa pinakamasama kaso, ang array ay sa reverse order. 62 00:03:05,090 --> 00:03:11,180 Kailangan mong mag-shift ang bawat isa sa mga elemento n hanggang sa n posisyon, lahat ng oras namin 63 00:03:11,180 --> 00:03:12,880 gumawa na ng insertion. 64 00:03:12,880 --> 00:03:15,720 Iyan ay isang pulutong ng paglilipat. 65 00:03:15,720 --> 00:03:18,014 >> Sa pinakamahusay na kaso, ang array ay ganap na ganap na pinagsunod-sunod. 66 00:03:18,014 --> 00:03:20,680 At uri ng tulad ng kung ano ang nangyari may limang at anim sa halimbawa, 67 00:03:20,680 --> 00:03:23,779 kung saan kami maaaring tak lamang ito sa nang hindi na gawin ang anumang paglilipat, 68 00:03:23,779 --> 00:03:24,820 Gusto namin mahalagang gawin iyon. 69 00:03:24,820 --> 00:03:27,560 >> Kung akala mo na ang aming array ay isa sa pamamagitan ng anim, 70 00:03:27,560 --> 00:03:29,900 nais naming magsimula sa pamamagitan ng deklarasyon isa ay pinagsunod-sunod. 71 00:03:29,900 --> 00:03:33,300 Dalawang dumating pagkatapos ng isa upang maaari naming lamang sabihin, OK, na rin ng isa at dalawa ay nakaayos. 72 00:03:33,300 --> 00:03:36,190 Tatlong dumating pagkatapos ng dalawang ito, OK, isa at dalawa at tatlo ay nakaayos. 73 00:03:36,190 --> 00:03:39,590 >> Hindi kami gumagawa ng anumang mga swaps, hindi namin paglipat lamang ito arbitrary linya 74 00:03:39,590 --> 00:03:42,460 pagitan inayos at unsorted na pumunta kami. 75 00:03:42,460 --> 00:03:46,646 Kasing epektibo tulad ng ginawa namin sa halimbawa, paggawa sa mga elemento asul, bilang namin magpatuloy. 76 00:03:46,646 --> 00:03:48,270 Kaya kung ano ang pinakamasama kaso runtime, pagkatapos? 77 00:03:48,270 --> 00:03:51,854 Tandaan, kung kami ay may sa paghahalili sa bawat isa sa ang mga elemento n marahil n posisyon, 78 00:03:51,854 --> 00:03:54,020 sana na nagbibigay sa iyo ng isang ideya na ang pinakamasama kaso 79 00:03:54,020 --> 00:03:57,770 runtime ay Big O ng n squared. 80 00:03:57,770 --> 00:04:00,220 >> Kung ang array ay ganap na ganap inayos, ang lahat ng mayroon kaming gawin 81 00:04:00,220 --> 00:04:04,480 ay tumingin sa bawat solong elemento isang beses, at pagkatapos ay tapos na kami. 82 00:04:04,480 --> 00:04:08,440 Kaya sa pinakamahusay na kaso, ito ay katapusan ng n. 83 00:04:08,440 --> 00:04:09,490 >> Ako Doug Lloyd. 84 00:04:09,490 --> 00:04:11,760 Ito ay CS50. 85 00:04:11,760 --> 00:04:13,119