Diferència clau: ordenació d'inserció vs ordenació de selecció
L'ordenació per inserció i l'ordenació per selecció són dos algorismes d'ordenació utilitzats per ordenar una col·lecció de dades. De vegades cal ordenar les dades en un ordre concret. Els algorismes d'ordenació són mecanismes per ordenar un conjunt de dades. En l'ordenació, les dades s'ordenen segons un ordre numèric o lexicogràfic. Si les dades s'ordenen correctament, seria fàcil cercar dades més ràpidament. Si els números de telèfon d'una guia telefònica no estan ordenats, seria difícil trobar un número de telèfon específic. De la mateixa manera, si les paraules del diccionari no estan ordenades alfabèticament, seria molt difícil trobar paraules. Per tant, la classificació és útil a la vida diària. En informàtica, hi ha algorismes d'ordenació per ordenar una col·lecció de dades. Dos d'aquests algorismes són l'ordenació per inserció i l'ordenació per selecció. L'ordenació per inserció és l'algorisme d'ordenació que ordena la matriu desplaçant els elements un per un. L'ordenació de selecció és l'algorisme d'ordenació que troba l'element més petit de la matriu i intercanvia l'element amb la primera posició, després troba el segon element més petit i l'intercanvia amb l'element de la segona posició i continua el procés fins que s'ordena tota la matriu.. La diferència clau entre l'ordenació per inserció i l'ordenació per selecció és que l'ordenació per inserció compara dos elements alhora, mentre que l'ordenació per selecció selecciona l'element mínim de tota la matriu i l'ordena.
Què és l'ordenació d'inserció?
L'ordenació per inserció és un algorisme d'ordenació basat en comparacions al lloc. En aquest mètode, la matriu es cerca pas a pas. Els elements no ordenats es mouen i s'insereixen a la subllista ordenada de la matriu. L'algorisme d'ordenació d'inserció es pot explicar amb l'exemple següent.
Per exemple, pren la matriu inicial com a 77, 33, 44, 11, 88. En aquest algorisme d'ordenació, el primer pas és seleccionar l'element actual.
L'element actual és 77. L'element actual es compara amb tots els elements del costat esquerre. El 77, és el primer element i no hi ha elements al costat esquerre. L'índex de la posició actual és 0.
Llavors, l'índex de la posició actual s'incrementa en 1. Ara l'índex és 1 i l'element actual és 33. Quan es compara amb l'element de l'esquerra, és més petit que 77. Aleshores, aquests dos valors s'intercanvien. Ara 33 és a l'índex 0 i 77 a l'índex1.
Ara la matriu és 33, 77, 44, 11, 88.
Un altre cop, l'índex s'incrementa. L'índex és 2 i l'element actual és 44. Es compara amb els elements del costat esquerre. 44 és menor que 77. Per tant, aquests dos valors s'intercanvien. Ara la matriu és 33, 44, 77, 11, 88. Cal comparar tots els elements de l'esquerra. Per tant, el 44 es compara amb el 33. El 33 és més petit que el 44. Per tant, aquests elements no s'han de canviar.
Ara la matriu és 33, 44, 77, 11, 88.
Un altre cop, l'índex s'incrementa. L'índex és 3 i l'element actual és 11. Es compara amb tots els elements de l'esquerra. 11 és menys de 77, de manera que aquests dos s'intercanvien. Ara la matriu és 33, 44, 11, 77, 88. Quan es comparen 11 i 44, 11 és menys que 44. Per tant, aquests dos s'intercanvien. Ara les matrius són 33, 11, 44, 77, 88. De nou, 11 es compara amb 33. 11 és menor que 33, de manera que aquests dos valors s'intercanvien.
Ara la matriu és 11, 33, 44, 77, 88.
Incrementar l'índex farà que l'índex sigui 4. El valor és 88. És superior a 77. Per tant, no cal canviar-lo. Finalment, la matriu ordenada és 11, 33, 44, 77, 88.
Figura 01: exemple d'ordenació d'inserció
La implementació de l'ordenació d'inserció és com l'anterior. La matriu inicial era 77, 33, 44, 11, 88. Després d'ordenar, dóna la sortida 11, 33, 44, 77, 88.
Què és l'ordenació de selecció?
L'ordenació per selecció és un algorisme d'ordenació basat en comparacions al lloc. Les matrius es divideixen en seccions. La part ordenada es troba a l'extrem esquerre. La part no ordenada es troba a l'extrem dret. En primer lloc, s'ha de trobar el valor més petit. A continuació, s'intercanvia amb l'element esquerre. Ara aquest element es troba a la matriu ordenada. Aquest procés continua movent el límit de la matriu sense ordenar d'un element cap a la dreta. L'algorisme d'ordenació de selecció es pot explicar amb l'exemple següent.
Per exemple, pren la matriu inicial com a 77, 33, 44, 11, 88, 22. En aquest algorisme d'ordenació, es troba el més petit de la matriu. L'element més petit és 11. S'intercanvia amb l'element de l'índex 0 de la matriu.
Ara la matriu és 11, 33, 44, 77, 88, 22.
L'element més petit es troba a l'índex 0, de manera que ara s'ordena 11. De la resta d'elements, el més petit és 22. S'intercanvia amb l'element d'índex 1st.
Ara la matriu és 11, 22, 44, 77, 88, 33.
Els elements 11 i 22 ja estan ordenats. De la resta, el valor més petit és 33. S'intercanvia amb l'element d'índex 2nd.
Ara la matriu és 11, 22, 33, 77, 88, 44.
Els elements 11, 22 i 33 ja estan ordenats. De la resta, el valor més petit és 44. S'intercanvia amb l'element d'índex 3rd.
Ara la matriu és 11, 22, 33, 44, 88, 66.
Els elements 11, 22, 33, 44 ja estan ordenats. Els elements restants són 88 i 66. L'element 66 s'intercanvia amb l'element d'índex 4th.
Ara la matriu és 11, 22, 33, 44, 66, 88.
És la matriu ordenada mitjançant l'algorisme d'ordenació de selecció.
Figura 02: Exemple d'ordenació de selecció
La implementació de l'ordenació d'inserció és com l'anterior. La matriu inicial era 77, 33, 44, 11, 88. Després d'ordenar, dóna la sortida 11, 33, 44, 77, 88.
Quina semblança hi ha entre l'ordenació per inserció i l'ordenació per selecció?
Tant l'ordenació per inserció com l'ordenació per selecció són algorismes d'ordenació
Quina diferència hi ha entre l'ordenació per inserció i l'ordenació per selecció?
Ordenació d'inserció vs. Ordenació de selecció |
|
| L'ordenació per inserció és l'algorisme d'ordenació que ordena la matriu desplaçant els elements un per un. | L'ordenació per selecció és l'algorisme d'ordenació que troba l'element més petit de la matriu i intercanvia l'element amb la primera posició, després troba el segon element més petit i l'intercanvia amb l'element de la segona posició i continua el procés fins a tota la matriu està ordenada. |
| procés | |
| L'ordenació d'inserció és ordenar la subllista comparant dos elements fins que s'ordena tota la matriu. | L'ordenació de selecció selecciona l'element mínim i l'intercanvia amb la primera posició, torneu a seleccionar el mínim per a la resta i canvieu-lo a la segona posició i continua aquest procés fins al final. |
| Estabilitat | |
| L'ordenació d'inserció és un algorisme d'ordenació estable. | L'ordenació per selecció no és un algorisme d'ordenació estable. |
Resum: ordenació d'inserció vs ordenació de selecció
De vegades és necessari ordenar les dades. En informàtica, hi ha algorismes per ordenar les dades. Aquest article parla dels dos algorismes d'ordenació que són l'ordenació per inserció i l'ordenació per selecció. L'ordenació per inserció és l'algorisme d'ordenació que ordena la matriu desplaçant els elements un per un. L'ordenació de selecció és l'algorisme d'ordenació que troba l'element més petit de la matriu i intercanvia l'element amb la primera posició, després troba el segon element més petit i l'intercanvia amb l'element de la segona posició i continua el procés fins que s'ordena tota la matriu.. La diferència entre l'ordenació per inserció i l'ordenació per selecció és que l'ordenació per inserció compara dos elements alhora, mentre que l'ordenació per selecció selecciona l'element mínim de tota la matriu i l'ordena.
Descarregueu el PDF d'Ordenació d'inserció vs Ordenació de selecció
Podeu descarregar la versió PDF d'aquest article i utilitzar-la per a finalitats fora de línia segons la nota de citació. Baixeu la versió PDF aquí: Diferència entre l'ordenació d'inserció i l'ordenació de selecció
