Algoritmo di ordinamento sto fondendo! :(

[Mazza2]

uff.... mi sapete segnalare una classe che qualcuno ha gia' fatto che mi ordina un certo numero di int dal piu' alto al + basso (o anke viceversa)?

thanks

[paplo]

Ti propongo 3 algoritmi di ordinamento ...

Insertion sort (complessità O(n^2))
Quick sort (complessità O(n*logn))
Quinsort (booo)

//////// Insertion sort
public static int[] InsertionSort(int [] lista) {
for( int j = 1; j < lista.length; j++ ) {
int key = lista[ j ];
int i = j-1;
while( (i >= 0) && (lista[ i ] > key) ) {
lista[ i+1 ] = lista[ i ];
i = i-1;
}
lista[ i+1 ] = key;
}
return lista;
}


///////// Quick sort
public static int part (int[] lista, int a, int z)
{
int scambio;

//-------------------------------------------------------------
// Si assume che a sia inferiore a z.
//-------------------------------------------------------------
int i = a + 1;
int cf = z;

//-------------------------------------------------------------
// Inizia il ciclo di scansione dell'array.
//-------------------------------------------------------------
while (true)
{
while (true)
{
//-----------------------------------------------------
// Sposta i a destra.
//-----------------------------------------------------
if ((lista[i] > lista[a]) || (i >= cf))
{
break;
}
else
{
i++;
}
}
while (true)
{
//-----------------------------------------------------
// Sposta cf a sinistra.
//-----------------------------------------------------
if (lista[cf] <= lista[a])
{
break;
}
else
{
cf--;
}
}

if (cf <= i)
{
//-----------------------------------------------------
// è avvenuto l'incontro tra i e cf.
//-----------------------------------------------------
break;
}
else
{
//-----------------------------------------------------
// Vengono scambiati i valori.
//-----------------------------------------------------
scambio = lista[cf];
lista[cf] = lista[i];
lista[i] = scambio;

i++;
cf--;
}
}
//-------------------------------------------------------------
// A questo punto lista[a..z] è stata ripartita e cf è la
// collocazione di lista[a].
//-------------------------------------------------------------
scambio = lista[cf];
lista[cf] = lista[a];
lista[a] = scambio;

//-------------------------------------------------------------
// A questo punto, lista[cf] è un elemento (un valore) nella
// giusta posizione.
//-------------------------------------------------------------
return cf;
}

//-----------------------------------------------------------------
static int[] QuickSort (int[] lista, int a, int z)
{
int cf;

if (z > a)
{
cf = part (lista, a, z);
QuickSort (lista, a, cf-1);
QuickSort (lista, cf+1, z);
}

//-------------------------------------------------------------
// In Java, gli array sono oggetti, e come tali vengono passati
// per riferimento. Qui si restituisce ugualmente un
// riferimento all'array ordinato.
//-------------------------------------------------------------
return lista;
}


///////// Quinsort
public static int[] QuinsSort(int[] lista,int m){
int a=0;
int z=lista.length-1;
QuinsSort(lista,a,z,m);
return lista;
}
static int[] QuinsSort(int[] lista, int a, int z, int m){
int lenght=(z-a)+1;
if (lenght <= m){
InsertionSort(lista, a,z);
}
else{
int cf=part(lista, a,z) ;
QuinsSort(lista, a, cf-1,m);
QuinsSort(lista ,cf+1,z,m);
}
return lista;
}


public static int part (int[] lista, int a, int z)
{
int scambio;

//-------------------------------------------------------------
// Si assume che a sia inferiore a z.
//-------------------------------------------------------------
int i = a + 1;
int cf = z;

//-------------------------------------------------------------
// Inizia il ciclo di scansione dell'array.
//-------------------------------------------------------------
while (true)
{
while (true)
{
//-----------------------------------------------------
// Sposta i a destra.
//-----------------------------------------------------
if ((lista[i] > lista[a]) || (i >= cf))
{
break;
}
else
{
i++;
}
}
while (true)
{
//-----------------------------------------------------
// Sposta cf a sinistra.
//-----------------------------------------------------
if (lista[cf] <= lista[a])
{
break;
}
else
{
cf--;
}
}

if (cf <= i)
{
//-----------------------------------------------------
// è avvenuto l'incontro tra i e cf.
//-----------------------------------------------------
break;
}
else
{
//-----------------------------------------------------
// Vengono scambiati i valori.
//-----------------------------------------------------
scambio = lista[cf];
lista[cf] = lista[i];
lista[i] = scambio;

i++;
cf--;
}
}
//-------------------------------------------------------------
// A questo punto lista[a..z] è stata ripartita e cf è la
// collocazione di lista[a].
//-------------------------------------------------------------
scambio = lista[cf];
lista[cf] = lista[a];
lista[a] = scambio;

//-------------------------------------------------------------
// A questo punto, lista[cf] è un elemento (un valore) nella
// giusta posizione.
//-------------------------------------------------------------
return cf;
}

//-----------------------------------------------------------------


public static int[] InsertionSort(int[] lista,int a,int z) {

for( int j = 1+a; j < z+1; j++ ) {
int key = lista[ j ];
int i = j-1;
while( (i >= a) && (lista[ i ] > key) ) {
lista[ i+1 ] = lista[ i ];
i = i-1;
}
lista[ i+1 ] = key;
}
return lista;
}



Ciao,
Paplo

[recoil]

mi spieghi dove hai trovato il quinsort???
non l'ho mai sentito nominare...

come complessità dovrebbe essere simile al quicksort perché quando viene usato l'insertion sort questo è eseguito in O(m^2) che è pur sempre una costante.

[paplo]

il quinsort è il nome che ho dato all'algoritmo che il prof. ci ha chiesto di implementare.

in poche parole ... per vettori di lunghezza minore di m arrestare l'esecuzione di quicksort ed aggiungere un'unica chiamata finale ad insertionsort.

la complessità non me la ricordo e adesso non ho proprio voglia di pensarci visto che domandi ho l'esame di algoritmi e strutture dati!

Ciao,
Paplo