Beillesztési rendezés

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. november 22-én felülvizsgált verziótól ; az ellenőrzések 20 szerkesztést igényelnek .

Beillesztési rendezés
Beillesztési rendezési példa
célja	Rendezési algoritmus
Adatstruktúra	sor
legrosszabb idő	O( n 2 ) összehasonlítások, cserék
Legjobb idő	O( n ) összehasonlítás, 0 csere
Átlagos idő	O( n 2 ) összehasonlítások, cserék
A memória költsége	O( n ) összesen, O( 1 ) segéd
Médiafájlok a Wikimedia Commons oldalon

A beszúrásos rendezés egy olyan rendezési algoritmus , amelyben a bemeneti sorozat elemeit egyenként átnézik, és minden új bejövő elemet megfelelő helyre helyeznek a korábban rendezett elemek közé [1] . Számítási összetettség - . $O(n^{2})$

Leírás

Az algoritmus bemenete egy számsorozat: . A rendezett számokat kulcsoknak is nevezik . A bemeneti sorozat a gyakorlatban elemekkel ellátott tömbként van ábrázolva . A kimeneten az algoritmusnak vissza kell adnia az eredeti sorozat permutációját , hogy a következő összefüggés teljesüljön [2] . $n$ $a_{1},a_{2},...,a_{n}$ $n$ $a_{{1}}^{{'}},a_{{2}}^{{'}},...,a_{{n}}^{{'}}$ $a_{{1}}^{{'}}\leqslant a_{{2}}^{{'}}\leqslant ...\leqslant a_{{n}}^{{'}}$

Kezdetben a rendezett sorozat üres. Az algoritmus minden lépésében kiválasztásra kerül az egyik bemeneti adatelem, és a már rendezett sorrendben a kívánt pozícióba kerül, amíg a bemeneti adatkészlet ki nem merül. A rendezett sorozat bármely időpontjában az elemek kielégítik az algoritmus kimenetére vonatkozó követelményeket [3] .

Ez az algoritmus felgyorsítható bináris kereséssel, hogy megtalálja az aktuális elem helyét a rendezett részben. A tömb hosszú jobbra tolódásának problémáját a mutatók megváltoztatásával oldjuk meg [4] .

Pszeudokód

A rendezési eljárás bemenete egy tömb , amely a sorozat rendezendő elemeiből áll. megfelel az eredeti tömb méretének. A rendezés nem igényel további memóriát, kivéve egy elem állandó értékét, mivel a permutáció a tömbön belül történik. Az eljárás működése következtében a bemeneti tömbben megjelenik a szükséges kimeneti elemek sorozata [5] . $A[1..n]$ $A[1],A[2],...,A[n]$ $n$ $A.\mathrm {length}$

Algoritmus pszeudokód:

mert j = 2 -től A. hossza do kulcs = A[j] i = j-1 míg (int i >= 0 és A[i] > gomb) nem A[i + 1] = A[i] i = i - 1 vége közben A[i+1] = kulcs vége [5]

ha i = 2 -től n -ig csinálja x = A[i] j = i míg (int j > 1 és A[j-1] > x) igen A[j] = A[j-1] j = j - 1 vége közben A[j] = x vége: [6]

A[0] = - i = 2 esetén n do

\infty

j = i míg (j > 0 és A[j] < A[j - 1]) felcserélik ( A[j], A[j - 1]) j = j - 1 vége, míg vége a következőhöz: [7] [8]

Az utolsó verzióban a cserét x = A[j]; A[j] = A[j-1]; A[j-1] = xa csereművelet képviseli, emiatt kicsit lassabb. A beírt A[0] értéke kisebb, mint a többi elem [8] értéke .

Algoritmuselemzés

Az algoritmus végrehajtási ideje a bemeneti adatoktól függ: minél nagyobb a rendezendő halmaz, annál tovább tart a rendezés. A tömb kezdeti sorrendje is befolyásolja a végrehajtási időt. Az algoritmus futási ideje különböző, azonos méretű bemenetekre a végrehajtandó elemi műveletektől, lépésektől függ [9] .

Az algoritmus minden utasításához megadjuk az időköltséget és az ismétlések számát, ahol a feltétel-ellenőrzések száma a while [10] belső ciklusban : $t_{j}$

A kód	Ár	Visszajátszások
j = 2 esetén A.hossz	$c_{1}$	$n$
kulcs = A[j]	$c_{2}$	$n-1$
i = j - 1	$c_{3}$	$n-1$
miközben i > 0 és A[i] > gomb	$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] = kulcs	$c_{7}$	$n-1$

A beillesztési rendezési algoritmus futási ideje az egyes lépések futási idejének összege [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)$

A legkedvezőbb eset a rendezett tömb. Sőt, minden belső ciklus csak egy iterációból áll, vagyis az összes . Ekkor az algoritmus futási ideje . A futási idő lineárisan függ a bemenő adatok méretétől [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)$

Legrosszabb eset elemzése

A legrosszabb eset egy fordított sorrendben rendezett tömb. Ebben az esetben minden új elem összehasonlításra kerül a rendezett sorrendben szereplő összes elemmel. Ez azt jelenti, hogy minden belső hurok j iterációból áll, azaz minden . Ekkor az algoritmus futási ideje a következő lesz: $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\jobbra)+c_{5}{\frac {n(n-1)}{2}}+c_{6}{\frac {n(n-1)}{2 } }+c_{7}(n-1)=O(n^{2})$ .

A futási idő a bemeneti adatok méretének négyzetes függvénye [13] .

Átlagos esetelemzés

Az átlagos eset elemzéséhez ki kell számítania a következő elem helyzetének meghatározásához szükséges összehasonlítások átlagos számát. Új elem hozzáadásakor legalább egy összehasonlítás szükséges, még akkor is, ha az elem a megfelelő pozícióban van. A hozzáadandó elem az egyik pozíciót elfoglalhatja. Véletlenszerű bemeneteket feltételezve az új elem ugyanannyira valószínű, hogy bármely pozícióba kerül [14] . Az összehasonlítások átlagos száma a -edik elem beszúrásához [15] : $én$ $i+1$ $én$

$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+ one }}$

Az n elem átlagos futási idejének becsléséhez össze kell adni [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-\sum _{i=1}^{n-1}\left({\frac {1}{i+1}}\right)$

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

Az algoritmus időbonyolultsága . Az állandó tényezők és az alacsonyabb sorrendű feltételek miatt azonban egy magasabb növekedési sorrendű algoritmus gyorsabban futhat kis bemeneteken, mint egy alacsonyabb növekedési sorrendű algoritmus [17] . $O(n^{2})$

Lásd még

Jegyzetek

↑ Knut D. E. 5.2 Belső rendezés // A programozás művészete. 3. kötet. Rendezés és keresés = The Art of Computer Programming. 3. kötet. Rendezés és keresés / szerk. V. T. Tertysnij (5. fejezet) és I. V. Krasikov (6. fejezet). - 2. kiadás - Moszkva: Williams, 2007. - T. 3. - 832 p. — ISBN 5-8459-0082-1 .
↑ Kormen, 2013 , p. 38.
↑ Kormen, 2013 , p. 39.
↑ Knut D. E. 5.2.1 Beszúrások szerinti rendezés // A programozás művészete. 3. kötet. Rendezés és keresés = The Art of Computer Programming. 3. kötet. Rendezés és keresés / szerk. V. T. Tertysnij (5. fejezet) és I. V. Krasikov (6. fejezet). - 2. kiadás - Moszkva: Williams, 2007. - T. 3. - 832 p. — ISBN 5-8459-0082-1 .
↑ 1 2 Cormen, 2013 , p. 39-40.
↑ N. Wirth. Algoritmusok és adatstruktúrák. - M. : DMK Press, 2010. - S. 74. - 272 p. - ISBN 987-5-94074-584-6.
↑ Skiena S. Algoritmusok. Fejlesztési útmutató. - 2. - Szentpétervár. : BHV-Petersburg, 2014. - S. 137. - 720 p. - ISBN 978-5-9775-0560-4 .
↑ 1 2 Aho, 2000 , p. 237.
↑ Kormen, 2013 , p. 47.
↑ Kormen, 2013 , p. 48.
↑ Kormen, 2013 , p. 48-49.
↑ Kormen, 2013 , p. 49.
↑ Kormen, 2013 , p. 49-50.
↑ McConnell, 2004 , p. 74.
↑ McConnell, 2004 , p. 75.
↑ McConnell, 2004 , p. 75-76.
↑ Kormen, 2013 , p. 51.

Irodalom

Aho A. V., Hopcroft D. E., Ulman D. D. Data structures and algorithms = Data structures and algorithms / Szerk. A. A. Minko. - M. : Williams, 2000. - S. 231. - ISBN 5-8459-0122-7 .
Knut D. E. 5.2.1 Rendezés beszúrások szerint // A programozás művészete. 3. kötet. Rendezés és keresés = The Art of Computer Programming. 3. kötet. Rendezés és keresés / szerk. V. T. Tertysnij (5. fejezet) és I. V. Krasikov (6. fejezet). - 2. kiadás - Moszkva: Williams, 2007. - T. 3. - 832 p. — ISBN 5-8459-0082-1 .
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. 2.1. Beillesztési rendezés // Algoritmusok: felépítés és elemzés = Introduction to Algorithms / Szerk. I. V. Krasikova. - 3. kiadás - M. : Williams, 2013. - S. 38-45. — ISBN 5-8459-1794-8 .
McConnell J. A modern algoritmusok alapjai = Analysis of Algorithms: An Active Learning Approach / Szerk. S. K. Lando. - M . : Technosfera, 2004. - S. 72-76. — ISBN 5-94836-005-9 .

Linkek

Rendezési algoritmusok
Elmélet	Bonyolultság O jelölés Rendelési viszony Típusok rendezése fenntartható Belső Külső
Csere	buborék Keverés Törpék Gyors Fésű Rendezés páros-páratlan Bitenként
Választás	Választás Piramis alakú Sima
Betétek	Betétek shella fa
egyesülés	egyesülés
Nincs összehasonlítás	Számolás Blokk
hibrid	introsort Timsort
Egyéb	Topológiai hálózatok biton
nem praktikus	Bogosort Stooge fajta palacsinta lassú