Selitettävien algoritmien lajittelu

Lajittelualgoritmit ovat joukko ohjeita, jotka ottavat taulukon tai luettelon syötteeksi ja järjestävät kohteet tiettyyn järjestykseen.

Lajittelut ovat yleisimmin numeerisessa muodossa tai aakkosjärjestyksessä (kutsutaan leksikografiseksi), ja ne voivat olla nousevassa (AZ, 0-9) tai laskevassa (ZA, 9-0) järjestyksessä.

Miksi algoritmien lajittelu on tärkeää

Koska lajittelu voi usein vähentää ongelman monimutkaisuutta, se on tärkeä tietojenkäsittelytieteen algoritmi. Näillä algoritmeilla on suoria sovelluksia algoritmien, tietokantaalgoritmien, jakamis- ja valloitusmenetelmien, tietorakenteen algoritmien ja monien muiden hakemiseen.

Joitakin yleisiä lajittelualgoritmeja

Joitakin yleisimpiä lajittelualgoritmeja ovat:

  • Valinta Lajittele
  • Kuplalajittelu
  • Lisälajittelu
  • Yhdistä lajittelu
  • Nopea lajittelu
  • Kasa Lajittele
  • Laskeminen Lajittelu
  • Radix Lajittele
  • Lajittele kauha

Lajittelualgoritmin luokitus

Lajittelualgoritmit voidaan luokitella seuraavien parametrien perusteella:

  1. Perustuu vaihtojen tai inversioiden lukumäärään Tämä on kuinka monta kertaa algoritmi vaihtaa elementit syötteen lajittelemiseksi. Selection Sortvaatii vähimmäismäärän vaihtosopimuksia.
  2. Perustuu vertailumäärään Tämä on kuinka monta kertaa algoritmi vertaa elementtejä syötteen lajittelemiseksi. Big-O-merkintää käyttämällä yllä luetellut lajittelualgoritmiesimerkit vaativat ainakin O(nlogn)vertailuja parhaassa tapauksessa ja O(n^2)vertailuja pahimmassa tapauksessa useimpien lähtöjen osalta.
  3. Rekursioon tai ei-rekursioon perustuva Jotkut lajittelualgoritmit, kuten esimerkiksi Quick Sort, käyttävät rekursiivisia tekniikoita syötteen lajittelussa. Muut lajittelualgoritmit, kuten Selection Sorttai Insertion Sort, käyttävät ei-rekursiivisia tekniikoita. Lopuksi jotkut lajittelualgoritmit, kuten Merge Sort, käyttävät sekä rekursiivisia että ei-rekursiivisia tekniikoita syötteen lajittelussa.
  4. Perustuu vakauslajittelualgoritmien sanotaan olevan, stablejos algoritmi ylläpitää elementtien suhteellista järjestystä yhtä suurilla avaimilla. Toisin sanoen kaksi ekvivalenttia elementtiä pysyy järjestyksessä samassa järjestyksessä kuin ne olivat syötteessä.
  5. Insertion sort, Merge Sort, Ja Bubble Sortovat stabiileja
  6. Heap Sorteivätkä Quick Sortole vakaita
  7. Perustuu ylimääräiseen tilantarpeeseen Lajittelualgoritmien sanotaan olevan, in placejos ne edellyttävät jatkuvaa O(1)ylimääräistä tilaa lajittelua varten.
  8. Insertion sortja Quick-sortovat in placelajittelevia, kun siirrämme elementtejä pivotin ympärillä, emmekä oikeastaan ​​käytä erillistä taulukkoa, jota EI tapahdu yhdistämislajittelussa, jossa syötteen koko on varattava etukäteen, jotta lähtö tallennetaan lajittelun aikana.
  9. Merge Sorton esimerkki out placelajittelusta, koska se vaatii ylimääräistä muistitilaa sen toiminnoille.

Paras mahdollinen ajan monimutkaisuus vertailupohjaiseen lajitteluun

Kaikkien vertailupohjaisten lajittelualgoritmien on tehtävä vähintään nLog2n-vertailuja syötetaulukon lajittelemiseksi, ja Heapsort- ja yhdistämislajittelu ovat asymptoottisesti optimaalisia vertailulajeja.Tämä voidaan helposti todistaa piirtämällä päätöspuukaavio.