[MUSIC nagpe-play] 

DOUG LLOYD: So-uuri ay isa pang algorithm maaari naming gamitin upang ayusin ang isang array. Ang ideya sa likod ng algorithm na ito ay upang bumuo ng iyong pinagsunod-sunod array sa lugar, paglilipat mga elemento sa labas ng ang paraan na ikaw ay pupunta, upang gumawa ng room. Ito ay bahagyang naiiba mula sa pagpili ng uri o bubble uri, halimbawa, kung saan na nag-aayos kami ng mga lokasyon, kung saan ginagawa namin swaps. 

Sa kasong ito kung ano kami talaga ginagawa ay sliding elemento sa ibabaw, sa labas ng paraan. Paano gumagana ang algorithm na ito magtrabaho sa pseudocode? Well sabihin lang mang sabihin na ang unang elemento ng array ay inayos. Kami ay gusali na ito sa lugar. 

Kami ay gonna pumunta ang isang elemento sa isang panahon at bumuo ng mga ito, at kaya ang unang bagay na nakikita namin ay isang array isang elemento. At sa pamamagitan ng kahulugan, ang isang isang element ng array ay inayos. 

Pagkatapos ay magpapadala kami ulitin ang prosesong ito until-- ipapakita namin ulitin ang mga sumusunod na proseso hanggang ang lahat ng mga elemento ay nakaayos. Hanapin sa mga susunod unsorted elemento at ipasok ito sa ang pinagsunod-sunod na bahagi, sa pamamagitan ng paglilipat ng mga kinakailangang bilang ng mga elemento sa labas ng paraan. Sana ito visualization ay makakatulong sa iyong makita kung ano mismo ang nangyayari sa mga uri pagpapasok. 

Kaya muli, narito ang aming buong unsorted array, lahat ng mga elemento na nakalagay sa red. At sundin ang mga hayaan mga hakbang ng aming pseudocode. Ang unang bagay na ginagawa namin, ay tinatawag naming ang unang elemento ng array, pinagsunod-sunod. Kaya hindi namin lamang gonna sabihin limang, ngayon ikaw ay nakaayos. 

Pagkatapos namin tumingin sa mga susunod na unsorted elemento ng array at gusto naming ipasok na sa pinagsunod-sunod na bahagi, sa pamamagitan ng paglilipat elemento over. Kaya dalawang ay ang susunod na unsorted element ng array. Maliwanag na ito ay kabilang sa harap ng limang, kaya kung ano ang hindi namin gonna gawin ay isang uri ng hawakan ng dalawang tabi para sa isang segundo, maglipat ng limang higit sa, at pagkatapos ay ipasok ang dalawang bago limang, kung saan upang dapat pumunta. At ngayon maaari naming sabihin na ang dalawang ito ay pinagsunod-sunod. 

Kaya bilang maaari mong makita, na namin lamang sa ngayon tumingin sa dalawang mga elemento ng array. Hindi namin ay tumingin sa mga pamamahinga sa lahat, ngunit hindi namin Nakakuha ang mga dalawang mga elemento nakaayos ayon sa paraan ng mekanismo paglilipat. 

Kaya kami ulitin ang proseso muli. Hanapin sa mga susunod unsorted element, na isa. Ni-hold na maliban para sa isang segundo, maglipat ng lahat ng bagay sa loob, at ilagay ang isa kung saan dapat pumunta. 

Muli, hindi pa rin, na namin lamang kailanman tumingin sa isa, dalawa, lima. Hindi namin alam kung ano pa ang darating, ngunit inayos na namin ang mga tatlong mga sangkap. 

Susunod unsorted elemento ay tatlo, kaya kailangan namin i-set ito sa tabi. Susubukan naming maglipat ng higit sa kung ano ang aming kailangan na kung saan, sa oras na ito ay hindi lahat ng bagay tulad ng sa nakaraang dalawang mga kaso, ito lang ang lima. At pagkatapos ay gagamitin namin stick tatlong in, sa pagitan ng dalawa at ang lima. 

Anim na ang susunod na unsorted elemento sa array. At sa katunayan anim ay mas higit sa limang, kaya Hindi namin kahit na kailangan na gawin ang anumang pagpapalit. Maaari lang namin tak anim mismo sa sa ang katapusan ng pinagsunod-sunod na bahagi. 

Sa wakas, apat ay ang huling unsorted elemento. Kaya makikita itinakda namin ito sa tabi, magbago sa paglipas ng ang mga elemento na kailangan namin upang maglipat ng higit sa, at pagkatapos ay ilagay ang apat na kung saan ito kabilang. At ngayon, tumingin, na namin ng mga uri ng lahat ng mga elemento. Pansinin na may pagpapasok uri-uriin, hindi namin ay may upang bumalik-balik sa buong array. Nagpunta kami lamang ang buong array isang panahon, at Nilipat namin ang mga bagay na gusto na namin na nakaranas kami, upang para gumawa nang lugar para sa mga bagong elemento. 

Kaya kung ano ang pinakamasama kaso senaryo sa uri pagpapasok? Sa pinakamasama kaso, ang array ay sa reverse order. Kailangan mong mag-shift ang bawat isa sa mga elemento n hanggang sa n posisyon, lahat ng oras namin gumawa na ng insertion. Iyan ay isang pulutong ng paglilipat. 

Sa pinakamahusay na kaso, ang array ay ganap na ganap na pinagsunod-sunod. At uri ng tulad ng kung ano ang nangyari may limang at anim sa halimbawa, kung saan kami maaaring tak lamang ito sa nang hindi na gawin ang anumang paglilipat, Gusto namin mahalagang gawin iyon. 

Kung akala mo na ang aming array ay isa sa pamamagitan ng anim, nais naming magsimula sa pamamagitan ng deklarasyon isa ay pinagsunod-sunod. Dalawang dumating pagkatapos ng isa upang maaari naming lamang sabihin, OK, na rin ng isa at dalawa ay nakaayos. Tatlong dumating pagkatapos ng dalawang ito, OK, isa at dalawa at tatlo ay nakaayos. 

Hindi kami gumagawa ng anumang mga swaps, hindi namin paglipat lamang ito arbitrary linya pagitan inayos at unsorted na pumunta kami. Kasing epektibo tulad ng ginawa namin sa halimbawa, paggawa sa mga elemento asul, bilang namin magpatuloy. Kaya kung ano ang pinakamasama kaso runtime, pagkatapos? Tandaan, kung kami ay may sa paghahalili sa bawat isa sa ang mga elemento n marahil n posisyon, sana na nagbibigay sa iyo ng isang ideya na ang pinakamasama kaso runtime ay Big O ng n squared. 

Kung ang array ay ganap na ganap inayos, ang lahat ng mayroon kaming gawin ay tumingin sa bawat solong elemento isang beses, at pagkatapos ay tapos na kami. Kaya sa pinakamahusay na kaso, ito ay katapusan ng n. 

Ako Doug Lloyd. Ito ay CS50.