Sortare prin inserare

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 22 noiembrie 2019; verificările necesită 20 de modificări .

Sortare prin inserare
Exemplu de sortare prin inserare
scop	Algoritm de sortare
Structură de date	matrice
cel mai rău moment	O( n 2 ) comparații, schimburi
Cel mai bun timp	O( n ) comparații, 0 schimburi
Timp mediu	O( n 2 ) comparații, schimburi
Costul memoriei	O( n ) total, O( 1 ) auxiliar
Fișiere media la Wikimedia Commons

Sortarea prin inserție este un algoritm de sortare în care elementele secvenței de intrare sunt examinate unul câte unul, iar fiecare element nou de intrare este plasat într-un loc potrivit printre elementele ordonate anterior [ 1] . Complexitatea computațională - . $O(n^{2})$

Descriere

Intrarea algoritmului este o succesiune de numere: . Numerele sortate sunt numite și chei . Secvența de intrare este în practică reprezentată ca o matrice cu elemente. La ieșire, algoritmul trebuie să returneze o permutare a secvenței originale , astfel încât următoarea relație să fie satisfăcută [2] . $n$ $a_{1},a_{2},...,a_{n}$ $n$ $a_{{1}}^{{'}},a_{{2}}^{{'}},...,a_{{n}}^{{'}}$ $a_{{1}}^{{'}}\leqslant a_{{2}}^{{'}}\leqslant ...\leqslant a_{{n}}^{{'}}$

Inițial, secvența sortată este goală. La fiecare pas al algoritmului, unul dintre elementele de date de intrare este selectat și plasat în poziția dorită în secvența deja sortată până când setul de date de intrare este epuizat. În orice moment al secvenței sortate, elementele îndeplinesc cerințele pentru ieșirea algoritmului [3] .

Acest algoritm poate fi accelerat prin utilizarea căutării binare pentru a găsi locația elementului curent în partea sortată. Problema cu o deplasare lungă a matricei la dreapta este rezolvată prin schimbarea pointerilor [4] .

Pseudocod

Intrarea în procedura de sortare este un tablou format din elementele secvenței care trebuie sortate. corespunde dimensiunii matricei originale. Sortarea nu necesită memorie suplimentară, cu excepția unei valori constante pentru un element, deoarece permutarea este efectuată în cadrul matricei. Ca rezultat al funcționării procedurii, secvența de ieșire necesară a elementelor apare în tabloul de intrare [5] . $A[1..n]$ $A[1],A[2],...,A[n]$ $n$ $A.\mathrm {lungime}$

Pseudocod algoritm:

pentru j = 2 la A. lungime do cheie = A[j] i = j-1 în timp ce (int i >= 0 și A[i] > cheie) do A[i + 1] = A[i] i = i - 1 sfârşitul în timp ce A[i+1] = cheie sfârșitul [5]

pentru i = 2 la n do x = A[i] j = i în timp ce (int j > 1 și A[j-1] > x) fac A[j] = A[j-1] j = j - 1 sfârşitul în timp ce A[j] = x se încheie pentru [6]

A[0] = - pentru i = 2 la n do

\infty

j = i în timp ce (j > 0 și A[j] < A[j - 1]) schimbă ( A [j], A[j - 1]) j = j - 1 se încheie în timp ce se încheie pentru [7] [8]

În ultima versiune, schimbul x = A[j]; A[j] = A[j-1]; A[j-1] = xeste reprezentat de operația de swap, motiv pentru care este puțin mai lent. Valoarea A[0] introdusă este mai mică decât orice valoare a celorlalte elemente [8] .

Analiza algoritmului

Timpul de execuție al algoritmului depinde de datele de intrare: cu cât setul de sortat este mai mare, cu atât va dura mai mult pentru sortare. Ordinea inițială a matricei afectează și timpul de execuție. Timpul de rulare al algoritmului pentru diferite intrări de aceeași dimensiune depinde de operațiile elementare, sau pașii, care trebuie efectuate [9] .

Pentru fiecare instrucțiune a algoritmului, introducem costul de timp și numărul de repetări, unde este numărul de verificări ale condițiilor în bucla internă while [10] : $t_{j}$

Codul	Preț	Reluări
pentru j = 2 la A.lungime	$c_{1}$	$n$
cheie = A[j]	$c_{2}$	$n-1$
i = j - 1	$c_{3}$	$n-1$
în timp ce tasta i > 0 și A[i] >	$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] = cheie	$c_{7}$	$n-1$

Timpul de rulare al algoritmului de sortare prin inserare este suma timpilor de rulare ai fiecărui pas [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)$

Cel mai favorabil caz este o matrice sortată. În plus, toate buclele interioare constau dintr-o singură iterație, adică pentru toate . Atunci timpul de rulare al algoritmului va fi . Timpul de rulare depinde liniar de dimensiunea datelor de intrare [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)$

Analiza celui mai rău caz

Cel mai rău caz este o matrice sortată în ordine inversă. În acest caz, fiecare element nou este comparat cu toate din secvența sortată. Aceasta înseamnă că toate buclele interioare constau din j iterații, adică pentru toate . Atunci timpul de rulare al algoritmului va fi: $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\right)+c_{5}{\frac {n(n-1)}{2}}+c_{6}{\frac {n(n-1)}{2 } }+c_{7}(n-1)=O(n^{2})$ .

Timpul de rulare este o funcție pătratică a mărimii datelor de intrare [13] .

Analiza medie a cazului

Pentru a analiza cazul mediu, trebuie să calculați numărul mediu de comparații necesare pentru a determina poziția următorului element. Când adăugați un element nou, este necesară cel puțin o comparație, chiar dacă elementul este în poziția corectă. Al-lea element care trebuie adăugat poate ocupa una dintre poziții. Presupunând intrări aleatorii, noul element este la fel de probabil să ajungă în orice poziție [14] . Numărul mediu de comparații pentru a introduce elementul --lea [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+ unu }}$

Pentru a estima timpul mediu de rulare pentru n elemente, trebuie să însumăm [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)\aprox {\frac {n^{2}-n}{4}}+(n-1)-(\ln(n)-1)=O(n^{2})$

Complexitatea temporală a algoritmului este . Cu toate acestea, datorită factorilor constanți și a termenilor de ordin mai mic, un algoritm de ordin de creștere mai mare poate rula mai rapid pe intrări mici decât un algoritm de ordin de creștere mai mic [17] . $O(n^{2})$

Vezi și

Note

↑ Knut D. E. 5.2 Sortare internă // Arta programarii. Volumul 3. Sortarea și căutarea = The Art of Computer Programming. Volumul 3. Sortare și căutare / ed. V. T. Tertyshny (cap. 5) și I. V. Krasikov (cap. 6). - Ed. a II-a. - Moscova: 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 Sortarea după inserții // Arta programarii. Volumul 3. Sortarea și căutarea = The Art of Computer Programming. Volumul 3. Sortare și căutare / ed. V. T. Tertyshny (cap. 5) și I. V. Krasikov (cap. 6). - Ed. a II-a. - Moscova: Williams, 2007. - T. 3. - 832 p. — ISBN 5-8459-0082-1 .
↑ 1 2 Cormen, 2013 , p. 39-40.
↑ N. Wirth. Algoritmi și structuri de date. - M. : DMK Press, 2010. - S. 74. - 272 p. - ISBN 987-5-94074-584-6.
↑ Skiena S. Algoritmi. Ghid de dezvoltare. - al 2-lea. - Sankt Petersburg. : 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.

Literatură

Aho A. V., Hopcroft D. E., Ulman D. D. Data structures and algorithms = Data structures and algorithms / Ed. A. A. Minko. - M. : Williams, 2000. - S. 231. - ISBN 5-8459-0122-7 .
Knut D. E. 5.2.1 Sortarea după inserții // Arta programarii. Volumul 3. Sortarea și căutarea = The Art of Computer Programming. Volumul 3. Sortare și căutare / ed. V. T. Tertyshny (cap. 5) și I. V. Krasikov (cap. 6). - Ed. a II-a. - Moscova: Williams, 2007. - T. 3. - 832 p. — ISBN 5-8459-0082-1 .
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. 2.1. Sortare prin inserare // Algoritmi: construcție și analiză = Introducere în algoritmi / Ed. I. V. Krasikova. - Ed. a 3-a. - M. : Williams, 2013. - S. 38-45. — ISBN 5-8459-1794-8 .
McConnell J. Fundamentals of Modern Algorithms = Analysis of Algorithms: An Active Learning Approach / Ed. S. K. Lando. - M . : Technosfera, 2004. - S. 72-76. — ISBN 5-94836-005-9 .

Link -uri

Algoritmi de sortare
Teorie	Complexitate O notație Relația de comandă Sortați tipuri durabil Intern Extern
schimb valutar	bule Agitând Piticii Rapid Pieptene Sortare par-impar Pe bit
Alegere	Alegere Piramidal Neted
inserții	inserții shella copac
fuziune	fuziune
Fara comparatii	Socoteală bloc
hibrid	introsort Timsort
Alte	Topologic retelelor biton
nepractic	Bogosort Soiul de ciudăţeni clătită încet