Raða reiknirit: Lærðu af hverju þú ættir ekki að nota Bubblesort

Birting: Stuðningur þinn hjálpar til við að halda vefnum í gangi! Við þénum tilvísunargjald fyrir sumar þjónusturnar sem við mælum með á þessari síðu.


Hefur þú einhvern tíma velt því fyrir þér hvernig tölva setur hlutina í röð? Þegar þú smellir á A-Z hnappinn í Excel, hvað er raunverulega að gerast?

Tölvur raða listum eftir eftirfarandi aðferðum sem kallast „flokkunaralgrím.“ Reiknirit er sett af leiðbeiningum sem hægt er að fylgja aftur og aftur, vélrænt. Það eru til nokkrar mismunandi flokkunaralgrím – mismunandi aðferðir til að setja lista í rétta röð. Hver og einn hefur styrkleika og veikleika.

Hér eru vinsælustu flokkunaralgrímin.

Bubble Sort

Kúlaflokkurinn er óhagkvæmur, en einfaldur reiknirit. Það er sjaldan notað í reynd, en það er auðvelt að skilja það.

Bubble sort virkar með því að bera saman röð par af þáttum á lista. Fyrri og annar þátturinn er borinn saman, síðan annar og þriðji, síðan þriðji og fjórði og svo framvegis í gegnum listann. Eftir hver samanburð er skipt um tvo þætti ef þeir eru ekki í lagi. Eftir eina endurtekningu mun stærsti þátturinn hafa „bubblað upp“ til loka listans. Þessi aðferð er endurtekin aftur og aftur þar til listinn er flokkaður.

Í tvístefndu afbrigði er samanburður gerður til skiptis fram í gegnum listann og síðan afturábak í gegnum listann. Þetta vex flokkaður hluti á hvorum enda listans. Þetta er líka kallað „kokteilhristarinn.“

Hvenær á að nota Bubble Sort

Aldrei, annað en til sýnikennslu.

Meiri upplýsingar um Bubble Sort

  • Bubble Sort skýring frá reikniritinu, með dæmi um kóða;
  • Reiknirit kúla flokkað á yfir 100 mismunandi forritunarmálum;
  • Bubble Sort myndskreytt með Legos;
  • Bubble Sort myndskreytt með ungverskum þjóðdansleik.

Innsetning Raða

Flokkun innsetningar er hvernig fólk flokkar hlutina innsæi handvirkt – til dæmis þegar stafrófsröð er skrifuð. Það felur í sér að færa hvern þátt, aftur á móti, á sinn rétta stað innan þegar flokkaðs hluta.

Fyrsti þáttur listans er talinn „flokkaður.“ Þá er annar þátturinn talinn. Ef það er stærra en frumefnið á undan, þá er það á réttum stað og er hluti af „raða“ hlutanum. Annars er það fært aftur einn rauf aftur og borið saman við frumefnið á bak við það. Atriðið heldur áfram að snúa aftur þangað til það er í réttri stöðu innan flokkaðs hluta listans. Þessi aðferð er síðan endurtekin með þriðja, fjórða, fimmta hlutanum og svo framvegis.

Hvenær á að nota Innsetning Raða

Flokkun innsetningar er venjulega fljótlegasta lausnin til að flokka litla lista (10 eða færri þættir) og skilar að minnsta kosti nægilega vel á meðalstórum listum. Það getur þó orðið óheyrilega hægt í stærri settum.

Flokkun innsetningar gengur einnig vel, jafnvel í stórum settum, ef listinn er þegar aðallega flokkaður. Þetta gerir það tilvalið til að hreinsa úr arði sem er flokkað af mönnum eða nota í tengslum við aðrar flokkunaralgrím. Til dæmis er algengt að byrja með skjótan flokkun og skipta síðan yfir í innsetningarröðun eftir nokkrar endurtekningar.

Meiri upplýsingar um innsetningu Raða

  • Innsetning Raða útskýringu og kóðunaræfingu í Khan Academy;
  • Innsetning Raða reiknirit kóðað á næstum 100 mismunandi forritunarmál;
  • Innsetning Raða myndskreytt með styrofoam bollum og frásögn Harvard CS námsmanns;
  • Innsetning Sort myndskreytt með ungverskum þjóðdansleik.

Heap Sort

Heap sort er tvískipt tegund sem notar tvöfaldan hrúga gagnaskipulag sem milligönguhafa fyrir þætti á listanum.

Tvöfaldur hrúga er trébygging þar sem hver hnútur hefur allt að tvo hnúta barna. Stærsti þátturinn er efst á trénu. Hver hnút fyrir börn er minni en foreldri hnút hans. Þetta þýðir að ferlið við að byggja upp hrúgu raðar listanum að hluta. Þegar hrúga er byggð er stærsti þátturinn fjarlægður og settur í flokkaða röðina – þá stærsta hrúgan sem eftir er og svo framvegis.

Hvenær á að nota Heap Sort

Að meðaltali skilar hrúgurinn góðum árangri. Að auki er versta atburðarásin mun betri en versta fallmyndin fyrir næstum því hvaða önnur reiknirit sem er. Það er því oft notað með stórum og dreifðum gagnasöfnum.

Meiri upplýsingar um Heap Sort

  • Ítarlegar skýringar á hrúga frá CS prófessor við Kent State;
  • Heaps and Heap Sort Video Fyrirlestur frá MIT;
  • Til að fá ítarlegan skilning á hrúga og hrúgslagi, sjá þessa fimm hluta myndaseríu.

Sameina Raða

Það er tiltölulega einfalt að sameina tvo þegar raða lista í nýjan lista sem þegar er flokkaður: berðu saman fyrsta þáttinn í hverjum og settu smærri inn á nýja listann, endurtaktu. Þetta er grundvöllur fyrir sameiningarflokkinn.

Til að hefja tegund sameiningar er listi skipt í safn með „1 lista“. Síðan eru pör af þessum listum sameinaðir í tveggja þátta lista, sem síðan eru sameinaðir í 4 frumefnalista, og svo framvegis þar til allur listinn er sameinaður saman aftur..

Hvenær á að nota Sameina raða

Sameina tegund er mjög duglegur. Eina vandamálið er að sameiningarflokkur þarf venjulega nægt virkt minni (RAM) til að halda listanum tvisvar. Það getur því orðið óframkvæmanlegt við vissar kringumstæður.

Meiri upplýsingar um Sameina raða

  • Merge Sort frá Khan Academy er frábær sex hluta kennslustund með forritunaræfingum innifalin;
  • Sameina Raða kóðað á yfir 80 mismunandi forritunarmálum;
  • Merge Sort with German Folk Dance býður upp á dansvenju sem sýnir fram á flokkunaralgrímið.

Fljótur raða

Fljótleg tegund er ekki mjög leiðandi. Það er hins vegar mjög duglegur.

Fyrsta skrefið í fljótlegri gerð er að velja snúningsþátt. Þetta getur verið hvaða þáttur sem er á listanum. Næst eru öll gildi sem eru hærri en snúningurinn sett á eftir henni, á meðan öll gildi minni en eru sett á undan henni. Þetta skapar tvær skipting sem er ekki flokkuð, en eru í réttu sambandi hvert við annað. Sama málsmeðferð er gerð á hverri skipting, síðan á hverri undirdeild og svo framvegis. Þegar skiptingin nær einni stærð hver er listinn flokkaður.

Hvenær á að nota flokks raða

Quick sort er ein vinsælasta flokkunaralgrímið til hagnýtingar. Meðalhraði er mjög hratt. Versta atburðarásin (sem gerist sjaldan í náttúrulegum gagnasöfnum) verður erfið við mjög stór mengi.

Meiri upplýsingar um Quick Sort

  • Quick Sort kóðað á yfir 100 forritunarmál;
  • Fljótur raða útskýrt með blokkum úr CS-50 flokki Harvard;
  • Flýtiritunarleiðbeiningar frá leiðbeiningapunkti eru með mikið af smáatriðum, sýnishornskóða og hreyfimyndum.

Almennar heimildir um flokkun reiknirits

  • Uppbygging gagna – Flokkunartækni er mjög ítarleg röð frá Tutorials Point;
  • Raða reiknirit hefur sjón af öllu tagi, við mismunandi aðstæður – þú getur jafnvel horft á mismunandi reiknirit kapphlaupa hver við annan;
  • 15 Raða reiknirit á 6 mínútum er heillandi myndbandsmyndun;
  • Að komast í flokkun er myndband þar sem vandamálið með tölvutæku flokkun er kannað;
  • Hvað mismunandi raða reiknirit hljóð eins og er ótrúlegt “audibilization” vídeó sem þýðir nokkrar flokka reiknirit í hljóð.

Yfirlit

Oftast þegar þú forritar, ef þú þarft eitthvað smávægilegt flokkað – stutta gildagildi, dálk gagna – munt þú bara nota hvaða aðferð eða aðgerð sem er innbyggð á forritunarmálið þitt eða uppáhaldssafnið.

En þegar unnið er að stórum gagnaforritum er mikilvægt að hugsa um hvernig val þitt á algrími mun hafa áhrif á afköst kerfisins. Fyrir utan það eru flokkunaralgrímur grundvallaratriði í tölvunarfræði og ættu allir að vinna vel að þróun eða forritun..

Frekari upplestur og úrræði

Við höfum fleiri handbækur, námskeið og infografics sem tengjast forritun og þróun:

  • C ++ Hönnuðir auðlindir: eitt vinsælasta forritunarmálið, gott fyrir flestar tegundir af forritum.
  • Unicode kynning og auðlindir: læra allt um kóðun stafa.
  • MantisBT Kynning og auðlindir: MantisBT er eitt vinsælasta forrit fyrir villuleiðbeiningar.

Hvaða kóða ætti að læra?

Ruglaður um hvaða forritunarmál þú ættir að læra að kóða á? Skoðaðu infographic okkar, hvaða kóða ættir þú að læra? Það fjallar ekki aðeins um mismunandi þætti tungumálsins, það svarar mikilvægum spurningum eins og „Hve miklum peningum mun ég græða á forritun á Java?“

Hvaða kóða ættirðu að læra?
Hvaða kóða ætti að læra?

Jeffrey Wilson Administrator
Sorry! The Author has not filled his profile.
follow me