logo

TechCodeview

Lajittelualgoritmit

A Lajittelualgoritmi käytetään tietyn taulukon tai elementtiluettelon järjestämiseen uudelleen elementtien vertailuoperaattorin mukaan. Vertailuoperaattorilla päätetään elementtien uusi järjestys vastaavassa tietorakenteessa.

Esimerkiksi: Alla oleva merkkiluettelo on lajiteltu niiden ASCII-arvojen kasvavaan järjestykseen. Eli merkki, jolla on pienempi ASCII-arvo, sijoitetaan ensimmäiseksi kuin merkki, jolla on korkeampi ASCII-arvo.



Sisällysluettelo

Mitä on lajittelu?

Lajittelu viittaa tietyn taulukon tai elementtiluettelon uudelleenjärjestelyyn elementtien vertailuoperaattorin mukaan. Vertailuoperaattorilla päätetään elementtien uusi järjestys vastaavassa tietorakenteessa. Lajittelu tarkoittaa kaikkien elementtien järjestystä joko nousevaan tai laskevaan järjestykseen.



Lajitteluterminologia:

  • Paikkalajittelu: Paikalla oleva lajittelualgoritmi käyttää jatkuva tila tulosteen tuottamiseksi (muokkaa vain annettua taulukkoa). Se lajittelee luettelon vain muokkaamalla luettelon elementtien järjestystä. Esimerkkejä: valintalajittelu, kuplalajittelu lisäyslajittelu ja kekolajittelu.
  • Sisäinen lajittelu: Sisäinen lajittelu on, kun kaikki tiedot sijoitetaan päämuisti tai sisäinen muisti . Sisäisessä lajittelussa ongelma ei voi viedä syötettä kokonsa yli. Esimerkki: keon lajittelu, kuplalajittelu, valintalajittelu, pikalajittelu, kuorilajittelu, lisäyslajittelu.
  • Ulkoinen lajittelu: Ulkoinen lajittelu on silloin, kun kaikkea lajiteltavaa tietoa ei voida tallentaa muistiin kerralla, lajittelua kutsutaan ulkoiseksi lajitteluksi. Ulkoista lajittelua käytetään valtavaan tietomäärään. Esimerkkejä: Yhdistetty lajittelu, tunnistelajittelu, monivaiheinen lajittelu, neljän nauhan lajittelu, ulkoinen kantaluku jne.
  • Vakaa lajittelu: Kun kaksi samaa dataa näkyy sama Tilaus Lajiteltua dataa muuttamatta niiden sijaintia kutsutaan vakaaksi lajitteluksi. Esimerkkejä: Yhdistetty lajittelu, lisäyslajittelu, kuplalajittelu.
  • Epävakaa lajittelu: Kun kaksi samaa dataa näkyy eri Tilaus lajitetussa datassa sitä kutsutaan epävakaaksi lajitteluksi. Esimerkkejä: Pikalajittelu, Kekolajittelu, Shell-lajittelu .

Lajittelualgoritmien ominaisuudet:

  • Aika monimutkaisuus: Aikamonimutkaisuutta, mittaa, kuinka kauan algoritmin suorittaminen kestää, käytetään lajittelualgoritmien luokitteluun. Lajittelualgoritmin pahimman tapauksen, keskimääräisen ja parhaan tapauksen suorituskykyä voidaan käyttää prosessin aikaisen monimutkaisuuden kvantifiointiin.
  • Tilan monimutkaisuus: Lajittelualgoritmeilla on myös avaruuden monimutkaisuus, joka on algoritmin suorittamiseen tarvittavan muistin määrä.
  • Vakaus: Lajittelualgoritmin sanotaan olevan stabiili, jos samanarvoisten elementtien suhteellinen järjestys säilyy lajittelun jälkeen. Tämä on tärkeää tietyissä sovelluksissa, joissa alkuperäinen yhtäläisten elementtien järjestys on säilytettävä.
  • Paikkalajittelu: Paikalla oleva lajittelualgoritmi on sellainen, joka ei vaadi lisämuistia tietojen lajitteluun. Tämä on tärkeää, kun käytettävissä oleva muisti on rajallinen tai kun tietoja ei voida siirtää.
  • Sopeutumiskyky: Mukautuva lajittelualgoritmi on sellainen, joka hyödyntää datassa jo olemassa olevaa järjestystä suorituskyvyn parantamiseksi.

Lajittelualgoritmien sovellukset:

  • Hakualgoritmit: Lajittelu on usein ratkaiseva vaihe hakualgoritmeissa, kuten binäärihaussa, kolmihaussa, jossa tiedot on lajiteltava ennen tietyn elementin etsimistä.
  • Tiedonhallinta: Tietojen lajittelu helpottaa etsimistä, hakemista ja analysointia.
  • Tietokannan optimointi: Tietojen lajittelu tietokantoihin parantaa kyselyn suorituskykyä.
  • Koneoppiminen: Lajittelua käytetään tietojen valmisteluun koneoppimismalleja varten.
  • Tietojen analysointi: Lajittelu auttaa tunnistamaan tietojoukkojen mallit, trendit ja poikkeamat. Sillä on tärkeä rooli tilastoanalyysissä, taloudellisessa mallintamisessa ja muilla tietopohjaisilla aloilla.
  • Käyttöjärjestelmät: Lajittelualgoritmeja käytetään käyttöjärjestelmissä tehtäviin, kuten tehtävien ajoitukseen, muistin hallintaan ja tiedostojärjestelmän järjestämiseen.

Lajittelualgoritmien perusteet:

  • Johdatus lajittelutekniikoihin – Tietorakenteen ja algoritmin opetusohjelmat
  • Lajittelualgoritmin sovellukset, edut ja haitat
  • Mikä on tosielämän esimerkki lajittelusta?
  • Mikä on lajittelu DSA:ssa | Lajittelu merkitys

Lajittelualgoritmit:

Kirjaston toteutukset:

Helppoja ongelmia lajittelussa:

  • Lajittele elementit taajuuden mukaan
  • Lajittele 0:n, 1:n ja 2:n joukko
  • Lajittele eri koneisiin tallennetut numerot
  • Lajittele taulukko aaltomuodossa
  • Tarkista, menevätkö kaksi väliä päällekkäin tietyn intervallijoukon kesken
  • Kuinka lajitella päivämäärät C/C++:ssa?
  • Merkkijonojen lajittelu kuplalajittelulla
  • Etsi alueen puuttuvat elementit
  • Lajittele joukko asetettujen bittien määrän mukaan
  • Lajittele parilliset elementit kasvavaan ja parittomat laskevaan järjestykseen
  • Lajittele taulukko, kun kaksi puolikasta on lajiteltu
  • Isojen kokonaislukujen lajittelu
  • Lajittele linkitetty luettelo 0:sta, 1:stä ja 2:sta

Keskikokoiset lajitteluongelmat:

  • Käänteismäärä taulukossa yhdistämislajittelua käyttämällä
  • Etsi Minimipituus lajittelematon alitaulukko, joka lajittelee koko taulukon
  • Lajittele lähes lajiteltu (tai K-lajiteltu) taulukko
  • Lajittele n numeroa välillä 0 - n^2 - 1 lineaarisessa ajassa
  • Lajittele taulukko toisen taulukon määrittämän järjestyksen mukaan
  • Etsi piste, jossa maksimivälit menevät päällekkäin
  • Etsi permutaatio, joka aiheuttaa yhdistämislajittelun pahimman tapauksen
  • Lajittele parien vektorit nousevaan järjestykseen C++:ssa
  • Vähimmäisvaihdot, jotta kaksi taulukkoa ovat identtisiä
  • Suklaan jakeluongelma
  • Permutoi kaksi taulukkoa siten, että jokaisen parin summa on suurempi tai yhtä suuri kuin K
  • Ryhmälajittelu Negatiivisten numeroiden taulukon lajittelemiseksi
  • Lajittele matriisi kaikin tavoin kasvavassa järjestyksessä
  • Muunna taulukko pelkistettyyn muotoon käyttämällä parien vektoria
  • Pienin ero Tripletti kolmesta taulukosta
  • Tarkista, onko mahdollista lajitella taulukko vierekkäisten sallittujen ehdollisen vaihtamisen avulla

Vaikeita ongelmia lajittelussa:

  • Etsi taulukon jokaisen elementin ylittäjämäärä
  • Laske erilliset esiintymät osasekvenssiksi
  • Laske osajoukkojen (tai osajonojen) vähimmäismäärä peräkkäisillä numeroilla
  • Valitse k taulukkoelementtiä siten, että maksimi- ja minimierot minimoidaan
  • Vähimmäisvaihto, joka tarvitaan binääripuun muuntamiseen binäärihakupuuksi
  • K:s pienin alkio luonnollisista luvuista joidenkin kokonaislukujen poistamisen jälkeen
  • Kahden elementin taajuuden maksimiero siten, että elementti, jolla on suurempi taajuus, on myös suurempi
  • Vähimmäisswapit permutoidun taulukon saavuttamiseksi enintään 2 paikan vaihdolla vasemmalle
  • Selvitä, onko mahdollista tehdä taulukon elementeistä samanlaisia ​​yhdellä ulkoisella numerolla
  • Lajittele taulukko annetun yhtälön soveltamisen jälkeen
  • Tulosta merkkijonojen joukko lajiteltuna kopioimatta merkkijonoa toiseen

Pikalinkit:

  • 'Harjoitteluongelmat' lajittelussa
  • Lajittelun 'tietokilpailut'.

Suositus:

  • Opi tietorakenne ja algoritmit | DSA opetusohjelma