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ă - .
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] .
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] .
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] .
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 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] .
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] :
Codul | Preț | Reluări |
---|---|---|
pentru j = 2 la A.lungime | ||
cheie = A[j] | ||
i = j - 1 | ||
în timp ce tasta i > 0 și A[i] > | ||
A[i+1] = A[i] | ||
i = i - 1 | ||
A[i+1] = cheie |
Timpul de rulare al algoritmului de sortare prin inserare este suma timpilor de rulare ai fiecărui pas [11] : .
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] .
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:
.
Timpul de rulare este o funcție pătratică a mărimii datelor de intrare [13] .
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] :
Pentru a estima timpul mediu de rulare pentru n elemente, trebuie să însumăm [16] :
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] .
Algoritmi de sortare | |
---|---|
Teorie | Complexitate O notație Relația de comandă Sortați tipuri durabil Intern Extern |
schimb valutar | |
Alegere | |
inserții | |
fuziune | |
Fara comparatii | |
hibrid | |
Alte | |
nepractic |