[java] insertion sort

[Lucked]

ciao a tutti...mi servirebbe vedere/capire come funx. questo algoritmo.

Siti, esempi e brevi spiegazioni sono le benvenute

[tato83]

Se mi dai la tua mail ti mando delle diapositive sugli algoritmi di ordinamento.....ciao

[unomichisiada]

void InsertionSort(Record lista[],int n)
{
	int i,j;
   Record prossimo;//l'elemnto di separazione tra i due sottoarray
   for(i=1;i<n;i++)
   {
   	prossimo=lista[i];   
   	for(j=i-1;j>=0&&Confronta(prossimo,lista[j])<0;j--)
      	lista[j+1]=lista[j];   
      lista[j+1]=prossimo;
   }
}

E' lo stesso metodo usato dai giocatori a carte per ordinarle.
Si artiziona l'array in due,gli elemnti non ordianati (a destra)e quelli già ordinati (a sinistra).inizialmente l'array degli ordinati contiene un solo elemento (uno solo è un array ordinato),poi si prende il secondo e lo si inserisce al suo posto nell'array degli ordinati che a questo punto si espande di uno.Ovviamente per trovare la giusta posizione in cui inserirlo bisoga fare una serie di confronti e scambi.Alla fine ti resta il sottoarray di destra vuoto ed hai finito.
l'algoritmo ha una complessità nel caso perggiore O(n^2).é facile capire che il caso peggiore è l'array ordinato all'inverso.Nel caso migliore (array già ordinato) esegue solo n passi (n =lunghezza arrya).
Non c'è molto altro da dire.

[unomichisiada]

Ah l'algoritmo te l'ho postato in C anche se il titolo del 3d riporta Java,spero non sia un problema.tanto la comprensione dell'algoritmo non dipende dal linguaggio

[Lucked]

Si ho visto..va benissimo, ringrazio entrambi per adesso...