GeeksforGeeks

Tässä artikkelissa käsittelemme eri lajittelutekniikoiden tärkeitä ominaisuuksia, kuten niiden monimutkaisuutta, vakautta ja muistirajoituksia. Ennen tämän artikkelin ymmärtämistä sinun tulisi ymmärtää eri lajittelutekniikoiden perusteet (Katso : Lajittelutekniikat).

Aikakompleksisuuden analyysi –
Olemme käsitelleet eri lajittelutekniikoiden parhaan, keskimääräisen ja pahimman tapauksen monimutkaisuutta mahdollisine skenaarioineen.

Vertailuun perustuva lajittelu –
Vertailuun perustuvassa lajittelussa joukon elementtejä verrataan toisiinsa lajitellun joukon löytämiseksi.

• Bubble sort ja Insertion sort –
  Keskimääräinen ja huonoimman tapauksen aikakompleksisuus: n^2
  Parhaan tapauksen aikakompleksisuus: n kun joukko on jo lajiteltu.
  Pahin tapaus: kun array on käänteisesti lajiteltu.
• Selection sort –
  Parhaan, keskimääräisen ja pahimman tapauksen aikakompleksisuus: n^2, joka on riippumaton datan jakaumasta.
• Merge sort –
  Paras, keskimääräinen ja pahin tapaus aikakompleksisuus: nlogn, joka on riippumaton datan jakautumisesta.
• Heap sort –
  Paras, keskimääräinen ja pahin tapaus aikakompleksisuus: nlogn, joka on riippumaton datan jakautumisesta.
• Pikalajittelu –
  Se on jaa ja hallitse -lähestymistapa, jossa on rekurenssisuhde:

   T(n) = T(k) + T(n-k-1) + cn

  Pahin tapaus: Kun joukko on lajiteltu tai käänteisesti lajiteltu, jakoalgoritmi jakaa joukon kahteen osajoukkoon, joissa on 0 ja n-1 elementtiä. Näin ollen,

  T(n) = T(0) + T(n-1) + cnSolving this we get, T(n) = O(n^2)

  Paras tapaus ja keskimääräinen tapaus: Keskimäärin jakoalgoritmi jakaa joukon kahteen yhtä suureen osajoukkoon. Siksi,

  T(n) = 2T(n/2) + cnSolving this we get, T(n) = O(nlogn)

Vertailemattomaan lajitteluun perustuva lajittelu –
Vertailemattomaan lajitteluun perustuvassa lajittelussa joukon elementtejä ei verrata toisiinsa lajitellun joukon löytämiseksi.

• Radix-lajittelu –
  Paras, keskimääräinen ja pahimman tapauksen aikakompleksisuus: nk, jossa k on matriisin alkioiden maksimilukumäärä.
• Count-lajittelu –
  Paras, keskimääräinen ja pahimman tapauksen aikakompleksisuus: n+k, jossa k on count-matriisin koko.
  Keskusteltujen vertailuun perustuvien tekniikoiden joukosta vain yhdistämislajittelu on outplaced-tekniikka, koska se vaatii ylimääräisen matriisin lajiteltujen alimatriisien yhdistämiseen.
  Keskusteltujen ei-vertailuun perustuvien tekniikoiden joukosta kaikki ovat outplaced-tekniikoita. Counting sort käyttää laskentamäärää ja Bucket sort käyttää hash-taulukkoa massojen lajitteluun.

  Online/Offline-tekniikka –
  Lajittelutekniikkaa pidetään Online-tekniikkana, jos se voi ottaa vastaan uutta dataa menettelyn ollessa käynnissä eli lajittelun aloittamiseen ei tarvita täydellistä dataa.
  Keskusteltujen vertailuun perustuvien tekniikoiden joukosta vain Insertion Sort täyttää tämän kelpoisuusehdot sen käyttämän taustalla olevan algoritmin vuoksi, ts. se käsittelee matriisia (ei vain elementtejä) vasemmalta oikealle, ja jos uusia elementtejä lisätään oikealle, se ei vaikuta meneillään olevaan operaatioon.

  Vakaa/epävakaa tekniikka –
  Lajittelutekniikka on vakaa, jos se ei muuta samanarvoisten elementtien järjestystä.
  Vertailuun perustuvista tekniikoista bubble-lajittelu (bubble sort), insertion-lajittelu (insertion sort) ja merge-lajittelu (merge sort) ovat vakaana pidettäviä tekniikoita. Valintalajittelu on epästabiili, koska se voi muuttaa samanarvoisten elementtien järjestystä. Tarkastellaan esimerkiksi joukkoa 4, 4, 1, 3.

  Ensimmäisessä iteraatiossa pienin löydetty elementti on 1 ja se vaihdetaan 4:n kanssa 0:nteen paikkaan. Näin ollen 4:n järjestys suhteessa 1. kohdassa olevaan 4:ään muuttuu. Vastaavasti quick sort ja heap sort ovat myös epästabiileja.

  Ei vertailuun perustuvista tekniikoista Counting sort ja Bucket sort ovat stabiileja lajittelutekniikoita, kun taas radix sortin stabiilius riippuu taustalla olevasta algoritmista, jota käytetään lajitteluun.

  Lajittelutekniikoiden analyysi :

  • Kun matriisi on melkein lajiteltu, voidaan suosia insertion sorttia.
  • Kun syötteen järjestys ei ole tiedossa, suositaan merge sorttia, koska sen pahimman tapauksen aikakompleksisuus on nlogn ja se on myös stabiili.
  • Kun matriisi on lajiteltu, insertion- ja bubble-lajittelulla saavutetaan n:n kompleksisuus, mutta quick-lajittelun avulla saavutetaan n ^2:n kompleksisuus.

  Que – 1. Mikä lajittelualgoritmi vie vähiten aikaa, kun kaikki syötemäärän elementit ovat identtisiä? Tarkastellaan lajittelualgoritmien tyypillisiä toteutuksia.
  (A) Insertion Sort
  (B) Heap Sort
  (C) Merge Sort
  (D) Selection Sort

  Ratkaisu: Kuten käsiteltiin, lisäyslajittelun monimutkaisuus on n, kun syöttöjoukko on jo lajiteltu.

  Que – 2. Tarkastellaan Quicksort-algoritmia. Oletetaan, että on olemassa menettely pivot-alkion löytämiseksi, joka jakaa listan kahteen alalistaan, joista kumpikin sisältää vähintään viidenneksen elementeistä. Olkoon T(n) n elementin lajitteluun tarvittavien vertailujen lukumäärä. Tällöin (GATE-CS-2012)
  (A) T(n) <= 2T(n/5) + n
  (B) T(n) <= T(n/5) + T(4n/5) + n
  (C) T(n) <= 2T(4n/5) + n
  (D) T(n) <= 2T(n/2) + n

  Ratkaisu: Ratkaisu: Pikalajittelun monimutkaisuus voidaan kirjoittaa seuraavasti:

  T(n) = T(k) + T(n-k-1) + cn

  Kuten kysymyksessä annetaan, yksi lista sisältää 1/5 kaikista alkioista. Siksi toisessa listassa on 4/5 kokonaisalkioista. Asettamalla arvot saadaan:

  T(n) = T(n/5) + T(4n/5) + cn, mikä vastaa vaihtoehtoa (B).

  Aika- ja tilakompleksisuuden vertailutaulukko :

  

  Lajittelualgoritmi	Aikakompleksisuus			Tilakompleksisuus
  	Paras tapaus	Keskimääräinen Case	Worst Case	Worst Case
  Bubble Sort	Ω(N)	Θ(N2)	O(N2)	O(N2)	O(1)
  Valintalajittelu	Ω(N2)	Θ(N2)	O(N2)	O(1)
  Lajittelu sisäkkäin	Ω(N)	Θ(N2)	O(N2)	O(1)
  Sekoituslajittelu	Ω(N log N)	Θ(N log N)	O(N log N)	O(N)
  Heap Sort	Ω(N log N)	Θ(N log N)	O(N log N)	O(1)
  Pikalajittelu	Ω(N log N)	Θ(N log N)	O(N2)	O(N log N)	O(N log N)
  Lajittelu	Lajittelu O(N log N)	Θ(N k)	O(N k)	O(N + k)
  Count Sort	Ω(N + k)	Θ(N + k)	O(N + k)	O(N + k)