Lisäyslajittelu

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 22. marraskuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 20 muokkausta .

Lisäyslajittelu
Lisäyslajitteluesimerkki
tarkoitus	Lajittelualgoritmi
Tietorakenne	joukko
pahin aika	O( n 2 ) vertailut, vaihdot
Paras aika	O( n ) vertailua, 0 vaihtoa
Keskimääräinen aika	O( n 2 ) vertailut, vaihdot
Muistin hinta	O( n ) yhteensä, O( 1 ) apu
Mediatiedostot Wikimedia Commonsissa

Lisäyslajittelu on lajittelualgoritmi , jossa syöttösekvenssin elementit käydään läpi yksitellen ja jokainen uusi saapuva elementti sijoitetaan sopivaan paikkaan aiemmin järjestettyjen elementtien joukossa [ 1] . Laskennallinen monimutkaisuus - . $O(n^{2})$

Kuvaus

Algoritmin syöte on numerosarja: . Lajiteltuja numeroita kutsutaan myös avaimiksi . Syöttösekvenssi on käytännössä esitetty taulukkona elementeillä. Lähdössä algoritmin on palautettava alkuperäisen sekvenssin permutaatio , jotta seuraava relaatio toteutuu [2] . $n$ $a_{1},a_{2},...,a_{n}$ $n$ $a_{{1}}^{{'}},a_{{2}}^{{'}},...,a_{{n}}^{{'}}$ $a_{{1}}^{{'}}\leqslant a_{{2}}^{{'}}\leqslant ...\leqslant a_{{n}}^{{'}}$

Aluksi lajiteltu sarja on tyhjä. Algoritmin jokaisessa vaiheessa valitaan yksi syötetietoelementeistä ja sijoitetaan haluttuun kohtaan jo lajiteltuun sekvenssiin, kunnes syöttötietojoukko on käytetty loppuun. Elementit täyttävät missä tahansa vaiheessa lajiteltua sekvenssiä algoritmin ulostulolle asetetut vaatimukset [3] .

Tätä algoritmia voidaan nopeuttaa käyttämällä binäärihakua löytääksesi nykyisen elementin sijainnin lajitetussa osassa. Ongelma taulukon pitkästä siirtymisestä oikealle ratkaistaan vaihtamalla osoittimia [4] .

Pseudokoodi

Lajitteluproseduurin syöte on taulukko , joka koostuu lajittelevista sekvenssin elementeistä . vastaa alkuperäisen taulukon kokoa. Lajittelu ei vaadi lisämuistia, paitsi vakioarvon yhdelle elementille, koska permutaatio suoritetaan taulukon sisällä. Proseduurin toiminnan seurauksena tarvittava elementtien lähtösekvenssi ilmestyy syöttötaulukkoon [5] . $A[1..n]$ $A[1],A[2],...,A[n]$ $n$ $A.\mathrm {length}$

Algoritmin pseudokoodi:

j = 2 - A. pituus do avain = A[j] i = j-1 kun taas (int i >= 0 ja A[i] > näppäin) do A[i + 1] = A[i] i = i - 1 lopettaa hetkeksi A[i+1] = avain loppu [5]

i = 2 - n do x = A[i] j = i kun taas (int j > 1 ja A[j-1] > x) tekevät A[j] = A[j-1] j = j - 1 lopettaa hetkeksi A[j] = x loppu [6]

A[0] = - kun i = 2 - n do

\infty

j = i kun taas (j > 0 ja A[j] < A[j - 1]) vaihtavat ( A[j], A[j - 1]) j = j - 1 loppu ja loppu [7] [8]

Viimeisessä versiossa vaihtoa x = A[j]; A[j] = A[j-1]; A[j-1] = xedustaa swap-toiminto, minkä vuoksi se on hieman hitaampi. Syötetyn A[0]:n arvo on pienempi kuin muiden elementtien [8] arvo .

Algoritmianalyysi

Algoritmin suoritusaika riippuu syöttötiedoista: mitä suurempi lajiteltava joukko, sitä kauemmin lajittelu kestää. Myös taulukon alkuperäinen järjestys vaikuttaa suoritusaikaan. Algoritmin ajoaika samankokoisille eri tuloille riippuu suoritettavista perusoperaatioista tai vaiheista [9] .

Kullekin algoritmin käskylle esittelemme aikakustannukset ja toistojen lukumäärän, missä on ehtotarkistusten määrä while [10] -sisäsilmukassa : $t_{j}$

Koodi	Hinta	Toistoja
kun j = 2 - A.pituus	$c_{1}$	$n$
avain = A[j]	$c_{2}$	$n-1$
i = j - 1	$c_{3}$	$n-1$
kun i > 0 ja A[i] > näppäin	$c_{4}$	$\sum _{{j=2}}^{n}t_{j}$
A[i+1] = A[i]	$c_{5}$	$\sum _{{j=2}}^{n}(t_{j}-1)$
i = i - 1	$c_{6}$	$\sum _{{j=2}}^{n}(t_{j}-1)$
A[i+1] = avain	$c_{7}$	$n-1$

Lisäyslajittelualgoritmin ajoaika on kunkin vaiheen ajoaikojen summa [11] : . $T(n)=c_{1}n+c_{2}(n-1)+c_{3}(n-1)+c_{4}\sum _{{j=2}}^{n}t_ {j}+c_{5}\sum _{{j=2}}^{n}(t_{j}-1)+c_{6}\sum _{{j=2}}^{n}( t_{j}-1)+c_{7}(n-1)$

Edullisin tapaus on lajiteltu matriisi. Lisäksi kaikki sisäiset silmukat koostuvat vain yhdestä iteraatiosta, eli kaikille . Tällöin algoritmin ajoaika on . Ajoaika riippuu lineaarisesti syötetyn datan koosta [12] . $t_{j}=1$ $j$ $T(n)=(c_{1}+c_{2}+c_{3}+c_{4}+c_{7})n-(c_{2}+c_{3}+c_{4 }+c_{7})=O(n)$

Pahimman tapauksen analyysi

Pahin tapaus on matriisi, joka on lajiteltu käänteiseen järjestykseen. Tässä tapauksessa jokaista uutta elementtiä verrataan kaikkiin lajiteltuun sekvenssiin. Tämä tarkoittaa, että kaikki sisäiset silmukat koostuvat j-iteraatioista, eli kaikille . Sitten algoritmin ajoaika on: $t_{j}=j$ $j$

$T(n)=c_{1}n+c_{2}(n-1)+c_{3}(n-1)+c_{4}\sum _{{j=2}}^{n}j +c_{5}\sum _{{j=2}}^{n}(j-1)+c_{6}\sum _{{j=2}}^{n}(j-1)+c_ {7}(n-1)$

$T(n)=c_{1}n+c_{2}(n-1)+c_{3}(n-1)+c_{4}\left({\frac {n(n+1) ) )}{2}}-1\oikea)+c_{5}{\frac {n(n-1)}{2}}+c_{6}{\frac {n(n-1)}{2 } }+c_{7}(n-1)=O(n^{2})$ .

Ajoaika on neliöfunktio syötetyn datan koosta [13] .

Keskimääräinen tapausanalyysi

Keskimääräisen tapauksen analysoimiseksi sinun on laskettava seuraavan elementin sijainnin määrittämiseen tarvittavien vertailujen keskimääräinen määrä. Uutta elementtiä lisättäessä vaaditaan vähintään yksi vertailu, vaikka elementti olisi oikeassa paikassa. Lisättävä elementti voi olla jollakin paikasta. Jos oletetaan satunnaisia syötteitä, uusi elementti päätyy yhtä todennäköisesti mihin tahansa paikkaan [14] . Keskimääräinen vertailujen lukumäärä -: nnen elementin lisäämiseksi [15] : $i$ $i+1$ $i$

$T_{i}={\frac {1}{i+1}}\left(\sum _{p=1}^{i}p+i\right)={\frac {1}{i +1}}\left({\frac {i(i+1)}{2}}+i\right)={\frac {i}{2}}+1-{\frac {1}{i+ yksi }}$

Arvioiksesi n elementin keskimääräisen käyntiajan sinun on laskettava yhteen [16] :

$T(n)=\sum _{i=1}^{n-1}T_{i}=\sum _{i=1}^{n-1}\left({\frac {i} {2}}+1-{\frac {1}{i+1}}\right)=\sum _{i=1}^{n-1}{\frac {i}{2}}+\sum _{i=1}^{n-1}1-\summa _{i=1}^{n-1}\vasen({\frac {1}{i+1}}\oikea)$

$T(n)\noin {\frac {n^{2}-n}{4}}+(n-1)-(\ln(n)-1)=O(n^{2})$

Algoritmin aikamonimutkaisuus on . Vakiotekijöiden ja alhaisempien järjestysehtojen vuoksi korkeampi kasvujärjestysalgoritmi voi kuitenkin toimia nopeammin pienillä syötteillä kuin alhaisempi kasvujärjestysalgoritmi [17] . $O(n^{2})$

Katso myös

Muistiinpanot

↑ Knut D. E. 5.2 Sisäinen lajittelu // Ohjelmoinnin taito. Osa 3. Lajittelu ja haku = The Art of Computer Programming. Osa 3. Lajittelu ja haku / toim. V. T. Tertyshny (luku 5) ja I. V. Krasikov (luku 6). - 2. painos - Moskova: Williams, 2007. - T. 3. - 832 s. — ISBN 5-8459-0082-1 .
↑ Kormen, 2013 , s. 38.
↑ Kormen, 2013 , s. 39.
↑ Knut D. E. 5.2.1 Lajittelu lisäysten mukaan // Ohjelmoinnin taito. Osa 3. Lajittelu ja haku = The Art of Computer Programming. Osa 3. Lajittelu ja haku / toim. V. T. Tertyshny (luku 5) ja I. V. Krasikov (luku 6). - 2. painos - Moskova: Williams, 2007. - T. 3. - 832 s. — ISBN 5-8459-0082-1 .
↑ 1 2 Cormen, 2013 , s. 39-40.
↑ N. Wirth. Algoritmit ja tietorakenteet. - M. : DMK Press, 2010. - S. 74. - 272 s. - ISBN 987-5-94074-584-6.
↑ Skiena S. Algoritmit. Kehittämisopas. - 2. - Pietari. : BHV-Petersburg, 2014. - S. 137. - 720 s. - ISBN 978-5-9775-0560-4 .
↑ 1 2 Aho, 2000 , s. 237.
↑ Kormen, 2013 , s. 47.
↑ Kormen, 2013 , s. 48.
↑ Kormen, 2013 , s. 48-49.
↑ Kormen, 2013 , s. 49.
↑ Kormen, 2013 , s. 49-50.
↑ McConnell, 2004 , s. 74.
↑ McConnell, 2004 , s. 75.
↑ McConnell, 2004 , s. 75-76.
↑ Kormen, 2013 , s. 51.

Kirjallisuus

Aho A. V., Hopcroft D. E., Ulman D. D. Tietorakenteet ja algoritmit = Data structures and algorithms / Toim. A. A. Minko. - M. : Williams, 2000. - S. 231. - ISBN 5-8459-0122-7 .
Knut D. E. 5.2.1 Lajittelu lisäysten mukaan // Ohjelmoinnin taito. Osa 3. Lajittelu ja haku = The Art of Computer Programming. Osa 3. Lajittelu ja haku / toim. V. T. Tertyshny (luku 5) ja I. V. Krasikov (luku 6). - 2. painos - Moskova: Williams, 2007. - T. 3. - 832 s. — ISBN 5-8459-0082-1 .
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. 2.1. Lisäyslajittelu // Algoritmit: rakentaminen ja analyysi = Algoritmien perustelu / Ed. I. V. Krasikova. - 3. painos - M. : Williams, 2013. - S. 38-45. — ISBN 5-8459-1794-8 .
McConnell J. Modernien algoritmien perusteet = Algoritmien analyysi: Active Learning Approach / Toim. S. K. Lando. - M . : Technosfera, 2004. - S. 72-76. — ISBN 5-94836-005-9 .

Linkit

Lajittelualgoritmit
Teoria	Monimutkaisuus O merkintä Tilaussuhde Lajittele tyypit kestävää Sisäinen Ulkoinen
Vaihto	kupla Sekoitetaan Kääpiöt Nopeasti Kampa Lajittelu parillinen-pariton Bitittain
Valinta	Valinta Pyramidin muotoinen Sileä
insertit	insertit shella puu
fuusio	fuusio
Ei vertailuja	Laskenta lohko
hybridi	introsort Timsort
muu	Topologinen verkkoja bitonia
epäkäytännöllistä	Bogosort Stooge lajittelu pannukakku hidas