Rūšiavimo algoritmai: sužinokite, kodėl neturėtumėte naudoti „Bubblesort“

Atskleidimas: Jūsų palaikymas padeda išlaikyti svetainę! Mes uždirbame siuntimo mokestį už kai kurias paslaugas, kurias rekomenduojame šiame puslapyje.


Ar kada susimąstėte, kaip kompiuteris sutvarko daiktus? Kai „Excel“ spustelėsite mygtuką A – Z, kas iš tikrųjų vyksta?

Kompiuteriai sąrašus rūšiuoja laikydamiesi procedūrų, vadinamų „rūšiavimo algoritmais“. Algoritmas – tai instrukcijų rinkinys, kurio galima mechaniškai laikytis toliau ir daugiau. Yra keli skirtingi rūšiavimo algoritmai – skirtingos sąrašų sudarymo tvarkos tvarka. Kiekvienas iš jų turi savo stipriąsias ir silpnąsias puses.

Čia pateikiami populiariausi rūšiavimo algoritmai.

Burbulas Rūšiuoti

Burbulas yra neefektyvus, tačiau paprastas algoritmas. Tai retai naudojama praktikoje, tačiau lengvai suprantama.

Burbulas rūšiuojamas palyginant vienas po kito einančių elementų poras sąraše. Lyginamas pirmasis ir antrasis elementai, tada antrasis ir trečiasis, tada trečiasis ir ketvirtasis ir tt per sąrašą. Po kiekvieno palyginimo du elementai keičiami, jei jie netinkami. Po vienos iteracijos didžiausias elementas „išsipūs“ iki sąrašo pabaigos. Ši procedūra kartojama vėl ir vėl, kol sąrašas bus rūšiuojamas.

Dviejų krypčių variante palyginimai atliekami pakaitomis į priekį per sąrašą ir po to atgal per sąrašą. Tai padidina rūšiuotą skyrių kiekviename sąrašo gale. Tai taip pat vadinama „kokteilių purtyklių rūšiavimu“.

Kada naudoti rūšiavimą burbule

Niekada, išskyrus demonstravimą.

Daugiau informacijos apie burbulų rūšiavimą

  • Burbulo rūšiavimo paaiškinimas iš algoritmo su pavyzdžio kodu;
  • „Bubble Sort Algorithm“, užkoduotas daugiau nei 100 skirtingų programavimo kalbų;
  • Burbulas Rūšiuoti iliustruotas su Legos;
  • „Bubble Sort“ iliustruotas vengrų liaudies šokiais.

Įterpimas Rūšiuoti

Įterpimo rūšiavimas yra tai, kaip dauguma žmonių intuityviai rūšiuoja dalykus rankiniu būdu, pavyzdžiui, kai abėcėlę gamina. Tai apima kiekvieno elemento, savo ruožtu, perkėlimą į tinkamą vietą jau surūšiuotoje dalyje.

Pirmasis sąrašo elementas laikomas „rūšiuotu“. Tada svarstomas antrasis elementas. Jei jis yra didesnis nei elementas prieš jį, jis yra tinkamoje vietoje ir yra „rūšiuojamo“ skyriaus dalis. Priešingu atveju jis perkeliamas atgal per vieną angą ir lyginamas su elementu, esančiu už jo. Elementas juda atgal, kol yra tinkamoje padėtyje rūšiuotoje sąrašo dalyje. Tada ši procedūra pakartojama su trečiuoju, ketvirtuoju, penktuoju elementu ir pan.

Kada naudoti rūšiavimo įterpimą

Įterpimo rūšiavimas paprastai yra greičiausias sprendimas rūšiuoti mažus sąrašus (10 ar mažiau elementų) ir jis bent jau tinkamai vykdomas vidutinio dydžio sąrašuose. Tačiau didesniuose rinkiniuose jis gali tapti nepaprastai lėtas.

Įterpimo rūšiavimas taip pat gerai veikia, net ir dideliais rinkiniais, jei sąrašas jau dažniausiai yra rūšiuojamas. Tai daro jį idealiu atveju norint išvalyti senuosius žmonių surūšiuotus duomenis arba naudoti kartu su kitais rūšiavimo algoritmais. Pavyzdžiui, įprasta pradėti nuo greito rūšiavimo, o po kelių iteracijų pereiti prie rūšiavimo įterpimo.

Daugiau informacijos apie įdėjimą Rūšiuoti

  • Įterpimas Rūšiuoti paaiškinimo ir kodavimo užduotis Khan akademijoje;
  • Įterpimo rūšiavimo algoritmas, užkoduotas beveik 100 skirtingų programavimo kalbų;
  • Įterpimas Rūšiuoti iliustruotas polistirolo putplasčio taurėmis ir aprašytas Harvardo CS studento;
  • Įterpimas Rūšiuoti iliustruotas vengrų liaudies šokiais.

Rūšiuoti pagal krūvą

Krūvių rūšiavimas yra dviejų dalių rūšiavimas, kuris naudoja dvejetainę krūvos duomenų struktūrą kaip tarpinį elementą sąrašo elementuose..

Dvejetainis krūva yra medžio struktūra, kurioje kiekvienas mazgas turi iki dviejų vaiko mazgų. Didžiausias elementas yra medžio viršuje. Kiekvienas vaiko mazgas yra mažesnis nei jo pirminis mazgas. Tai reiškia, kad krūvos kūrimo procesas iš dalies sutvarko sąrašą. Pastačius krūvą, didžiausias elementas pašalinamas ir sudedamas į surūšiuotą masyvą – tada didžiausias iš likusių krūvos ir pan..

Kada naudoti rūšiavimą pagal krūvas

Vidutiniškai krūvos rūšys suteikia gerų rezultatų. Be to, blogiausias scenarijus yra daug geresnis nei blogiausias scenarijus beveik bet kuriam kitam algoritmui. Todėl jis dažnai naudojamas su dideliais ir paskirstytais duomenų rinkiniais.

Daugiau informacijos apie „Heap Sort“

  • Išsamus „Heap Sort“ paaiškinimas iš CS profesoriaus Kento valstijoje;
  • „MIT“ ir „Heaps Sort Video“ paskaita iš MIT;
  • Norėdami išsamiau suprasti krūvas ir krūvas, skaitykite šioje penkių dalių vaizdo serijoje.

Sujungti Rūšiuoti

Sujungti du jau surūšiuotus sąrašus į naują, jau surūšiuotą sąrašą yra gana paprasta: palyginkite pirmąjį kiekvieno elementą ir įdėkite mažesnį į naują sąrašą, pakartokite. Tai yra suliejimo rūšies pagrindas.

Norėdami pradėti rūšiavimą, sąrašas yra padalintas į 1 elemento „sąrašų“ rinkinį. Tada šių sąrašų poros sujungiamos į 2 elementų sąrašus, kurie vėliau sujungiami į 4 elementų sąrašus ir tt, kol visas sąrašas vėl sujungiamas.

Kada naudoti „Merge Sort“

Rūšiuoti sujungimus yra labai efektyvu. Vienintelė problema yra ta, kad sujungimo rūšiavimui paprastai reikia pakankamai aktyviosios atminties (RAM), kad sąrašą būtų galima laikyti du kartus. Todėl tam tikromis aplinkybėmis tai gali tapti neįmanoma.

Daugiau informacijos apie „Merge Sort“

  • „Merge Sort“ iš Khano akademijos yra puiki šešių dalių pamoka, į kurią įtraukti programavimo pratimai;
  • „Merge Sort“ koduota per 80 skirtingų programavimo kalbų;
  • „Merge Sort“ su vokiečių liaudies šokiais suteikia šokių rutiną, parodantį rūšiavimo algoritmą.

Greitas rūšiavimas

Greitas rūšiavimas nėra labai intuityvus. Tačiau jis yra labai efektyvus.

Pirmasis greito rūšiavimo žingsnis yra šarnyro elemento pasirinkimas. Tai gali būti bet kuris sąrašo elementas. Po to visos vertės, didesnės už šerdesą, dedamos po ja, o visos vertės, mažesnės nei dedamos prieš jį. Tai sukuria du skaidinius, kurie nėra rūšiuojami, bet yra teisingi vienas kito atžvilgiu. Ta pati procedūra atliekama kiekviename skaidinyje, po to kiekviename skirsnyje ir pan. Kai skaidiniai pasiekia po vieną elementą, sąrašas rūšiuojamas.

Kada naudoti greitą rūšiavimą

Greitas rūšiavimas yra vienas iš populiariausių rūšiavimo algoritmų praktiniam naudojimui. Vidutinis greitis yra labai greitas. Tačiau blogiausias scenarijus (kuris natūralių duomenų rinkiniuose pasitaiko retai) tampa problemiškas naudojant labai didelius rinkinius.

Daugiau informacijos apie greitą rūšiavimą

  • Greitas rūšiavimas užkoduotas daugiau nei 100 programavimo kalbų;
  • Greitas rūšiavimas paaiškinamas naudojant blokus iš Harvardo CS-50 klasės;
  • Greito rūšiavimo vadovėlis iš „Tutorials Point“ turi daug detalių, pavyzdžio kodą ir animuotus vaizdus.

Bendrieji rūšiavimo algoritmo ištekliai

  • Duomenų struktūra – rūšiavimo metodai yra labai išsami „Tutorials Point“ serija;
  • Rūšiavimo algoritmai turi bet kokio pobūdžio vizualizacijas skirtingomis sąlygomis – jūs netgi galite žiūrėti, kaip skirtingi algoritmai lenktyniauja vienas su kitu;
  • 15 algoritmų rūšiavimo per 6 minutes yra žavinga vaizdo vizualizacija;
  • „Rūšiavimas“ yra vaizdo įrašas, kuriame nagrinėjama kompiuterinio rūšiavimo problema;
  • Kaip skamba skirtingi rūšiavimo algoritmai, yra neįtikėtinas „audibilizacijos“ vaizdo įrašas, paverčiantis kelis rūšiavimo algoritmus garsu.

Santrauka

Programavimo metu, jei jums reikia kažkokio nereikšmingo rūšiavimo – trumpo reikšmių masyvo, duomenų stulpelio -, jūs tiesiog naudosite bet kurį metodą ar funkciją, įtaisytą jūsų programavimo kalboje ar mėgstamiausioje bibliotekoje..

Tačiau dirbant su didelėmis duomenų programomis svarbu galvoti apie tai, kaip algoritmo pasirinkimas paveiks jūsų sistemos našumą. Be to, rūšiavimo algoritmai yra pagrindinis informatikos aspektas ir turėtų būti gerai suprantami visiems, dirbantiems kuriant ar programuojant..

Tolesni skaitymai ir šaltiniai

Turime daugiau vadovų, vadovėlių ir infografijų, susijusių su kodavimu ir plėtra:

  • „C ++“ kūrėjų ištekliai: viena iš populiariausių programavimo kalbų, tinkama daugumai programų.
  • „Unicode“ įvadas ir šaltiniai: sužinokite viską apie simbolių kodavimą.
  • „MantisBT“ įvadas ir šaltiniai: „MantisBT“ yra viena iš populiariausių klaidų stebėjimo programų.

Kokį kodą turėtumėte išmokti?

Nesuprantate, kokią programavimo kalbą turėtumėte išmokti koduoti? Peržiūrėkite mūsų infografiką, kokį kodą turėtumėte išmokti? Jame ne tik aptariami skirtingi kalbų aspektai, bet ir atsakoma į svarbius klausimus, tokius kaip: „Kiek uždirbsiu„ Java “programavimui pragyvenimui?“

Kokį kodą turėtumėte išmokti?
Kokį kodą turėtumėte išmokti?

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