Home-theater-designers
L’ordenació per inserció és una tècnica que funciona utilitzant una sublista ordenada i afegint-hi contínuament un valor de la llista sense classificar fins que s’ordena tota la llista.
L’algorisme comença amb el primer element de llista com a subllista ordenada. A continuació, compara el número següent amb el primer. Si és més gran, s’insereix al primer índex. En cas contrari, es deixa al seu índex.
El tercer valor es compara amb els altres dos i després s’insereix a l’índex correcte. Aquest procés continua fins que s'ordena tota la llista.
Una mirada més detallada a la classificació per inserció
És possible que la descripció anterior no tingui sentit per a vosaltres. Un exemple us ajudarà a entendre molt millor.
Suposem que teniu una llista: [39, 6, 2, 51, 30, 42, 7].
L’algoritme identifica 39 com el primer valor de la sublista ordenada. L'avaluació passa a la segona posició.
Relacionat: Programació dinàmica: exemples, problemes comuns i solucions
A continuació, es compara 6 amb 39. Com que 6 és inferior a 39, s’insereix 6 a la primera posició i 39 a la segona. El nou ordre de llista és després que la primera passada sigui ara:
[6, 39, 2, 51, 30, 42, 7]
L’avaluació passa ara a la tercera posició. 2 es compara amb els dos darrers números i després s’insereix a la posició correcta. El nou ordre de llista és després que la segona passada sigui ara:
[2, 6, 39, 51, 30, 42, 7]
Per a la tercera passada, l'ordre de llista és:
[2, 6, 39, 51, 30, 42, 7]
El procés es repeteix fins que s'ordena tota la llista.
Vegeu el diagrama següent que resumeix aquestes operacions:
Anàlisi d’algorismes
La complexitat temporal de l’ordenació per inserció és O (n2), igual que tipus de bombolla . El nombre de comparacions en el pitjor dels casos és la suma de tots els enters de 1 a (n-1), donant una suma quadràtica.
Implementació del codi
El codi Python i Java següent mostra com podeu implementar el mètode Ordena per inserció.
Python:
def insertionSort(mylist):
for step in range(1, len(mylist)):
current_element = mylist[step]
position = step
while position > 0 and mylist[position - 1] > current_element:
mylist[position] = mylist[position - 1]
position = position - 1
mylist[position] = current_elementJava:
void insertionSort(int[] myarray) {
int n = myarray.length;
for (int x = 1; x int key = myarray[x];
int y = x-1;
while ( (y > -1) && ( myarray [y] > key ) ) {
myarray [y+1] = myarray [y];
y--;
}
myarray[y+1] = key;
}
} Millor codificació amb pseudocodi
Els exemples de codi anteriors es van donar sense cap pseudocodi al qual pugueu fer referència per escriure aquest algorisme en altres idiomes. A la majoria de programadors (inclòs l'autor) els agrada executar-se als seus teclats després de dir-los 'xiuxiuejant' sobre com funciona un programa.
Malauradament, aquest enfocament és propens a errors a mesura que la lògica del programa es complica. Com voldríeu pujar de nivell el vostre joc de programació aprenent a utilitzar el pseudocodi?
Compartir Compartir Tweet Correu electrònic Què és el pseudocodi i com us fa un millor desenvolupador?Tens problemes per aprendre a programar? Aprofiteu el codi aprenent el pseudocodi. Però, què és el pseudocodi i pot ajudar realment?
Llegiu a continuació Temes relacionats- Programació
- Java
- Python
- Tutorials de codificació
Jerome és escriptor de personal de MakeUseOf. Cobreix articles sobre programació i Linux. També és un entusiasta de la criptografia i manté sempre al dia la indústria de la criptografia.
Internet és molt dolorósMés de Jerome Davidson
Subscriu-te al nostre butlletí
Uniu-vos al nostre butlletí per obtenir consells tècnics, ressenyes, llibres electrònics gratuïts i ofertes exclusives.
Feu clic aquí per subscriure-us