Algoritmu kārtošana: uzziniet, kāpēc jums nevajadzētu izmantot pakalpojumu Bubblesort

Atklāšana: Jūsu atbalsts palīdz vietnei darboties! Mēs nopelnām nodošanas maksu par dažiem pakalpojumiem, kurus mēs iesakām šajā lapā.


Vai esat kādreiz domājis, kā dators sakārto lietas? Noklikšķinot uz pogas A-Z programmā Excel, kas īsti notiek?

Datori sakārto sarakstus, ievērojot procedūras, kuras sauc par “šķirošanas algoritmiem”. Algoritms ir instrukciju kopums, ko mehāniski var ievērot atkal un atkal. Pastāv vairāki dažādi kārtošanas algoritmi – dažādas procedūras sarakstu sakārtošanai pareizajā secībā. Katrā no tām ir savas stiprās un vājās puses.

Šeit ir vispopulārākie šķirošanas algoritmi.

Burbulis kārtot

Burbuļu kārtošana ir neefektīvs, bet vienkāršs algoritms. To praksē izmanto reti, taču to ir viegli saprast.

Burbuļu kārtošana darbojas, salīdzinot secīgus elementu pārus sarakstā. Pirmais un otrais elements tiek salīdzināts, pēc tam otrais un trešais, tad trešais un ceturtais utt., Izmantojot sarakstu. Pēc katra salīdzināšanas divi elementi tiek apmainīti, ja tie nav pareizi. Pēc vienas iterācijas lielākais elements būs “sakrājies” saraksta beigās. Šī procedūra tiek atkārtota atkal un atkal, līdz saraksts tiek kārtots.

Divvirzienu variantā salīdzinājumus veic pārmaiņus uz priekšu caur sarakstu un pēc tam atpakaļ caur sarakstu. Tādējādi katrā saraksta galā palielinās sakārtota sadaļa. To sauc arī par “kokteiļu kratītāja veidu”.

Kad lietot burbuļu kārtošanu

Nekad, izņemot kā demonstrāciju.

Papildinformācija par burbuļu kārtošanu

  • Burbuļu kārtošanas skaidrojums no algoritma ar parauga kodu;
  • Burbuļu kārtošanas algoritms, kas kodēts vairāk nekā 100 dažādās programmēšanas valodās;
  • Burbuļu kārtojums ilustrēts ar Legos;
  • Burbuļu kārtojums ilustrēts ar ungāru tautas dejām.

Ievietošanas kārtošana

Ievietošanas kārtība ir tā, kā vairums cilvēku intuitīvi šķiro lietas manuāli – piemēram, kad alfabētiski izmanto papīrus. Tas ietver katra elementa, savukārt, pārvietošanu pareizajā vietā jau sakārtotā porcijā.

Pirmais saraksta elements tiek uzskatīts par “sakārtotu”. Tad tiek ņemts vērā otrais elements. Ja tas ir lielāks nekā elements pirms tā, tas atrodas pareizajā vietā un ietilpst sadaļā “sakārtots”. Pretējā gadījumā tas tiek pārvietots par vienu slotu atpakaļ un salīdzināts ar elementu, kas atrodas aiz tā. Elements turpina virzīties atpakaļ, līdz tas atrodas pareizajā vietā sakārtotajā saraksta daļā. Pēc tam šo procedūru atkārto ar trešo, ceturto, piekto elementu utt.

Kad lietot ievietošanas kārtošanu

Ievietošanas kārtošana parasti ir ātrākais risinājums nelielu sarakstu (10 vai mazāk elementu) šķirošanai, un tas vismaz atbilstoši darbojas vidēja lieluma sarakstos. Tomēr lielākos komplektos tas var kļūt pārmērīgi lēns.

Arī ievietošanas kārtošana darbojas labi, pat lielās kopās, ja saraksts jau lielākoties ir kārtots. Tas padara to ideāli piemērotu mantoto cilvēku sakārtoto datu tīrīšanai vai izmantošanai kopā ar citiem šķirošanas algoritmiem. Piemēram, parasti sāk ar ātru kārtošanu un pēc dažām iterācijām pāriet uz ievietošanas kārtošanu.

Papildinformācija par ievietošanu Kārtot

  • Ievietošanas kārtošanas skaidrojums un kodēšanas vingrinājums Khan Academy;
  • Ievietošanas kārtošanas algoritms, kas kodēts gandrīz 100 dažādās programmēšanas valodās;
  • Ievietošanas kārtojums ilustrēts ar putuplasta kausiem un stāstījis Hārvardas CS students;
  • Ievietošanas kārtība ilustrēta ar ungāru tautas dejām.

Kaudzes kārtot

Kaudzes kārtība ir divdaļīga kārtība, kas izmanto bināru kaudzes datu struktūru kā starpposma turētāju saraksta elementiem..

Binārā kaudze ir koka struktūra, kurā katrā mezglā ir līdz diviem bērna mezgliem. Lielākais elements ir koka augšpusē. Katrs bērna mezgls ir mazāks nekā tā vecāku mezgls. Tas nozīmē, ka kaudzes veidošanas process daļēji sakārto sarakstu. Kad kaudze ir uzbūvēta, lielāko elementu noņem un ievieto sakārtotajā masīvā – pēc tam lielāko no atlikušās kaudzes utt..

Kad lietot kaudzes kārtošanu

Vidēji kaudzes šķirne nodrošina labu sniegumu. Turklāt tā sliktākā gadījuma scenārijs ir daudz labāks nekā gandrīz jebkura cita algoritma sliktākā scenārija scenārijs. Tāpēc to bieži izmanto ar lielām un izkliedētām datu kopām.

Vairāk informācijas par Heap Sort

  • Detalizēts kaudzes kārtojums no CS profesora Kentas štatā;
  • Kaudzes un kaudzes kārtošanas video lekcija no MIT;
  • Lai iegūtu padziļinātu izpratni par kaudzēm un kaudzēm, skatiet šo piecu daļu video sēriju.

Apvienot Kārtot

Divu jau sakārtotu sarakstu apvienošana jaunā, jau sakārtotā sarakstā ir samērā vienkārša: salīdziniet katra pirmā elementu un ievietojiet mazāko jaunajā sarakstā, atkārtojiet. Tas ir apvienošanas veida pamats.

Lai sāktu apvienošanu, saraksts tiek sadalīts 1 elementa “sarakstu” komplektā. Pēc tam šo sarakstu pāri tiek apvienoti 2 elementu sarakstos, kurus pēc tam apvieno 4 elementu sarakstos un tā tālāk, līdz viss saraksts atkal tiek apvienots kopā.

Kad izmantot apvienošanas kārtošanu

Saplūšana ir ļoti efektīva. Vienīgā problēma ir tā, ka apvienošanas kārtošanai parasti ir nepieciešams pietiekami daudz aktīvās atmiņas (RAM), lai sarakstu turētu divreiz. Tādēļ noteiktos apstākļos tas var kļūt neiespējams.

Vairāk informācijas par sapludināšanu

  • Merge Sort no Khan Academy ir lieliska sešu daļu nodarbība, kurā iekļauti programmēšanas vingrinājumi;
  • Merge Sort kodēts vairāk nekā 80 dažādās programmēšanas valodās;
  • Apvienot kārtošanu ar vācu tautas deju nodrošina deju rutīnu, demonstrējot šķirošanas algoritmu.

Ātrā kārtošana

Ātrā kārtošana nav ļoti intuitīva. Tas tomēr ir ļoti efektīvs.

Pirmais ātras kārtošanas solis ir šarnīra elementa atlasīšana. Tas var būt jebkurš saraksta elements. Pēc tam visas vērtības, kas ir lielākas par šarnīru, tiek novietotas aiz tā, savukārt visas vērtības, kas ir mazākas par tām, kuras ievietotas pirms tā. Tādējādi tiek izveidoti divi nodalījumi, kas nav sakārtoti, bet ir savstarpēji pareizi. Šī pati procedūra tiek veikta katrā nodalījumā, pēc tam katrā apakšnodalījumā utt. Kad nodalījumi sasniedz viena elementa lielumu katrs, saraksts tiek sakārtots.

Kad lietot ātro kārtošanu

Ātrā šķirošana ir viens no populārākajiem šķirošanas algoritmiem praktiskai lietošanai. Vidējais ātrums ir ļoti ātrs. Tomēr sliktākais scenārijs (kas dabisko datu kopās notiek reti) kļūst problemātisks ar ļoti lielām kopām.

Papildinformācija par ātro kārtošanu

  • Ātrā kārtošana kodēta vairāk nekā 100 programmēšanas valodās;
  • Ātrā kārtošana, izskaidrojot ar blokiem no Hārvardas CS-50 klases;
  • Ātrās kārtošanas pamācībai no konsultāciju punkta ir daudz detaļu, parauga kods un animēti attēli.

Vispārējie šķirošanas algoritma resursi

  • Datu struktūra – šķirošanas paņēmieni ir ļoti detalizēta sērija no Tutorials Point;
  • Algoritmu kārtošanai ir jebkura veida vizualizācijas dažādos apstākļos – jūs pat varat skatīties, kā dažādi algoritmi sacenšas viens ar otru;
  • 15 algoritmu kārtošana 6 minūtēs ir aizraujoša video vizualizācija;
  • Kārtot kārtošana ir video, kas pēta datorizētas šķirošanas problēmu;
  • Kā izklausās dažādi šķirošanas algoritmi, ir neticami “audibilizācijas” video, kas vairākus šķirošanas algoritmus pārvērš skaņā.

Kopsavilkums

Lielākoties, programmējot, ja jums ir nepieciešams kaut kas triviāls sakārtots – īss vērtību masīvs, datu kolonna -, jūs vienkārši izmantosit jebkuru metodi vai funkciju, kas iebūvēta jūsu programmēšanas valodā vai iecienītajā bibliotēkā..

Bet, strādājot pie lielām datu lietojumprogrammām, ir svarīgi padomāt par to, kā algoritma izvēle ietekmēs jūsu sistēmas veiktspēju. Turklāt šķirošanas algoritmi ir būtisks datorzinātnes aspekts, un tie būtu labi jāsaprot ikvienam, kas strādā izstrādes vai programmēšanas jomā.

Turpmākie lasījumi un resursi

Mums ir vairāk ceļvežu, mācību materiālu un infografiku, kas saistīti ar kodēšanu un attīstību:

  • C ++ izstrādātāju resursi: viena no populārākajām programmēšanas valodām, piemērota lielākajai daļai lietojumprogrammu.
  • Unicode ievads un resursi: uzziniet visu par rakstzīmju kodēšanu.
  • MantisBT ievads un resursi: MantisBT ir viena no populārākajām kļūdu izsekošanas programmām.

Kāds kods jums jāiemācās?

Neizpratnē par to, kādā programmēšanas valodā jums vajadzētu iemācīties iekļūt? Iepazīstieties ar mūsu infografiku. Kāds kods jums jāiemācās? Tajā aplūkoti ne tikai dažādu valodu aspekti, bet arī sniegti atbildes uz svarīgiem jautājumiem, piemēram, “Cik daudz naudas es nopelnīšu Java programmēšanai iztikai?”

Kāds kods jums jāiemācās?
Kāds kods jums jāiemācās?

Jeffrey Wilson Administrator
Sorry! The Author has not filled his profile.
follow me
    Like this post? Please share to your friends:
    Adblock
    detector
    map