Hi ha diversos algorismes bàsics per resoldre el problema d'ordenar una matriu. Un dels més famosos entre ells és el tipus d'inserció. Per la seva claredat i senzillesa, però baixa eficiència, aquest mètode s'utilitza principalment en la programació docent. Us permet entendre els mecanismes bàsics d'ordenació.
Descripció de l'algorisme
L'essència de l'algorisme d'ordenació d'inserció és que es forma un segment correctament ordenat dins de la matriu inicial. Cada element es compara un a un amb la part marcada i s'insereix al lloc correcte. Així, després d'iterar tots els elements, s'alineen en l'ordre correcte.
L'ordre de selecció dels elements pot ser qualsevol, es poden seleccionar arbitràriament o segons algun algorisme. Molt sovint, l'enumeració seqüencial s'utilitza des del principi de la matriu, on es forma un segment ordenat.
L'inici de l'ordenació podria semblar així:
- Agafa el primer element de la matriu.
- Com que no hi ha res amb què comparar-lo, pren l'element tal com s'ha ordenatseqüència.
- Vés al segon element.
- Compareu-lo amb el primer segons la regla d'ordenació.
- Si cal, intercanvia els elements per llocs.
- Preneu els dos primers elements com una seqüència ordenada.
- Vés al tercer element.
- Compareu-lo amb el segon, canvieu-lo si cal.
- Si es fa la substitució, compareu-la amb la primera.
- Preneu tres elements com una seqüència ordenada.
I així successivament fins al final de la matriu original.
Ordenació d'inserció de la vida real
Per a més claredat, val la pena donar un exemple de com s'utilitza aquest mecanisme de classificació a la vida quotidiana.
Agafeu, per exemple, una cartera. Els bitllets de cent, cinc-cents i mil dòlars es troben en desordre al compartiment dels bitllets. Això és un embolic, en una mescla així és difícil trobar immediatament el paper adequat. La matriu de bitllets s'ha d'ordenar.
El primer és un bitllet de 1000 rubles, i immediatament després - 100. Agafem un centenar i el col·loquem al davant. El tercer consecutiu és de 500 rubles, el lloc que li correspon és entre cent i mil.
De la mateixa manera que ordenem les cartes rebudes quan juguem al "Tonto" per facilitar la navegació per elles.
Operadors i funcions auxiliars
El mètode d'ordenació per inserció pren com a entrada una matriu inicial per ordenar, una funció de comparació i, si cal, una funció que determina la regla per enumerar els elements. S'utilitza més sovint al seu llocdeclaració de bucle normal.
El primer element és en si mateix un conjunt ordenat, de manera que la comparació comença des del segon.
L'algorisme utilitza sovint una funció auxiliar per intercanviar dos valors (intercanvi). Utilitza una variable temporal addicional, que consumeix memòria i alenteix una mica el codi.
Una alternativa és desplaçar en massa un grup d'elements i després inserir l'actual a l'espai lliure. En aquest cas, la transició al següent element es produeix quan la comparació ha donat un resultat positiu, que indica l'ordre correcte.
Exemples d'implementació
La implementació específica depèn en gran mesura del llenguatge de programació utilitzat, la seva sintaxi i estructures.
Implementació clàssica de C utilitzant una variable temporal per intercanviar valors:
int i, j, temp; for (i=1; i =0; j--) { if (matriu[j] < temp) trencar; matriu[j + 1]=matriu[j]; matriu[j]=temp; } }
Implementació de PHP:
function insertion_sort(&$a) { per a ($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
Aquí, primer, tots els elements que no coincideixen amb la condició d'ordenació es desplacen cap a la dreta i, a continuació, l'element actual s'insereix a l'espai lliure.
Codi Java utilitzant el bucle while:
public static void insertionSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
El significat general del codi es manté sense canvis: cada element de la matriu es compara seqüencialment amb els anteriors i s'intercanvia amb ells si cal.
Temps d'execució estimat
Òbviament, en el millor dels casos, l'entrada de l'algorisme serà una matriu ja ordenada de la manera correcta. En aquesta situació, l'algoritme simplement haurà de comprovar cada element per assegurar-se que està al lloc correcte sense fer intercanvis. Per tant, el temps d'execució dependrà directament de la longitud de la matriu original O(n).
La pitjor entrada és una matriu ordenada en ordre invers. Això requerirà un gran nombre de permutacions, la funció d'execució dependrà del nombre d'elements al quadrat.
El nombre exacte de permutacions per a una matriu completament no ordenada es pot calcular mitjançant la fórmula:
n(n-1)/2
on n és la longitud de la matriu original. Per tant, caldrien 4950 permutacions per organitzar 100 elements en l'ordre correcte.
El mètode d'inserció és molt eficient per ordenar matrius petites o parcialment ordenades. Tanmateix, no es recomana aplicar-lo a tot arreu a causa de l' alta complexitat dels càlculs.
L'algorisme s'utilitza com a auxiliar en molts altres mètodes d'ordenació més complexos.
Ordenar valors iguals
L'algorisme d'inserció pertany a les anomenades classes estables. Significa,que no intercanvia elements idèntics, sinó que conserva el seu ordre original. En molts casos, l'índex d'estabilitat és important per a una comanda correcta.
L'anterior és un excel·lent exemple visual d'ordenació d'inserció en un ball.
