Java

Algoritmi di ordinameto

Quando si ha un vettore di elementi non ordinati, si può ricorrere all'uso degli algoritmi di ordinamento.

Esistono diversi tipi di algoritmi di ordinamento:

  • Bubble sort
  • Seletion sort
  • Inserition sort
  • Merge sort

Il Bubble sort, ordinamento a bolle, consiste nel ordinare gli elementi del vettore confrontandoli uno ad uno, per poi ordinarli nel modo crescente o decrescente

for(int i = 0; i < array.length; i++) {
boolean flag = false;
for(int j = 0; j < array.length-1; j++) {

     if(array[j]>array[j+1]) {
      int k = array[j];
      array[j] = array[j+1];
      array[j+1] = k;
      flag=true;

Il Selection sort, alla base di questo algoritmo c'è l'idea di trovare all'interno del vettore l'elemnto più piccolo e scambiarlo con quello che occupa la posizione che questo deve andare ad occupare.

Quindi possiamo dire che alla prima iterazione il valore più piccolo del vettore viene scambiato di posizione con il valore che occupa in quel momento la prima posizione, ovviamente se questo non è già il più piccolo.

for(int i = 0; i < array.length-1; i++) {
int minimo = i; //Partiamo dall' i-esimo elemento
for(int j = i+1; j < array.length; j++) {

//Qui avviene la selezione, ogni volta
//che nell' iterazione troviamo un elemento piú piccolo di minimo
//facciamo puntare minimo all' elemento trovato
        if(array[minimo]>array[j]) {
       minimo = j;
}
}

//Se minimo e diverso dall' elemento di partenza
//allora avviene lo scambio
       if(minimo!=i) {
       int k = array[minimo];
       array[minimo]= array[i];
       array[i] = k;
}
}


L' Inseretion sort è un ordinamento che si basa sull'inserzione, ovvero nell'inserire gli elementi uno dopo l'altro, un pò come se si ordinassero delle schede numerate che sono impilate disordinatamente o delle carte da gioco.


for(int i = 1; i < array.length; i++) {
int x = i;
int j = i-1;
for(; j >= min; j--) {

    //Scambiamo l'elemento in posizione x fino a quando non raggiunge
   //la posizione corretta nel sotto-vettore, cioé quando
   //non é verificata piú questa condizione
    if(array[j]>array[x]) {
    int k = array[x];
    array[x] = array[j];
     array[j] = k;
      x = j; //La sua nuova posizione nel sotto-vettore
     } else break; //Significa che l'i-esimo elemento è nella sua giusta posizione
    //quindi possiamo terminare l' iterazione
}
}

Il Merge sort, ordinamento per fusione, è un algoritmo ricorsivo. Questo metodo si basa sul procedimento Divide et Impera, che consiste nel divedere un problema in tanti sotto problemi in modo che questi diventino a mano a mano più semplici da risolvere.

In un primo momento il vettore viene diviso in due parti che a loro volta vengono nuovamente divise in due e così via fino ad ottenere elementi singoli e possono essere trattati più semplicemente; poi questi elementi vengono di nuovo uniti fino ad ottenere di nuovo il numero di elementi che componevano il vettore di partenza ma questa volta ordinato.

Comment Stream