public static int[] InsertionSort(int vet[]){
    int i, j;
    int value;
    for(i=0;i<vet.length;i++){
         value = vet[i];
         j = i-1;
        while(j>=0&&vet[j]>value){
                 vet[j+1] = vet[j];
                 j = j-1;
        }
    vet[j+1] = value;
    }
return vet;
}

Spiegazione:

Vettore iniziale: 2 - 5 - 8 - 11 - 14 - 9

• 2 - 5 - 8 - 11 - 9 - 14
• 2 - 5 - 8 - 9 - 11 - 14

Nell'esempio sopra riportato ciò che fa l'algoritmo lo vediamo con l'ultimo elemento del vettore: viene eseguito un controllo con l'elemento precedente fino ad arrivare alla giusta posizione. Nel caso peggiore si rivela un pessimo algoritmo, questo dovuto anche perché fino a quando non termina il ciclo for non posso avere la certezza della posizione di un elemento, poiché a ogni iterazione del while è molto probabile che essa vari. Nel caso migliore, invece, risulta ottimale.

public static int[] SelectionSort(int vet[]){
    int i, j;
    int posmin;
    int tmp;
    for(i=0;i<vet.length;i++){
         posmin = i;
         for(j=(i+1);j<vet.length;j++){
              if(vet[j]<vet[posmin]){
                 posmin = j;
              }
         }
    tmp = vet[i];
    vet[i] = vet[posmin];
    vet[posmin] = tmp;
    }
return vet;
}

Spiegazione:

Vettore iniziale: 2 - 1 - 7 - 9 - 0

• 0 - 1 - 7 - 9 - 2
• 0 - 1 - 7 - 9 - 2
  
• 0 - 1 - 2 - 9 - 7
• 0 - 1 - 2 - 7 - 9

In rosso sono segnati i valori che vengono scambiati; il selection non fa altro che individuare l'elemento maggiore e scambiarlo con quello di indice i. A ogni passo l'elemento più a sinistra è già ordinato. Rispetto ai suoi concorrenti, è tutt'altro che un buon algoritmo di ordinamento: sia il caso pessimo che il caso ottimo hanno tempi di esecuzione elevati.

public static int[] BubbleSort(int vet[]){

Spiegazione:


Vettore iniziale: 5 - 2 - 4 - 0 - 8 - 1


• 2 - 5 - 4 - 0 - 8 - 1
• 2 - 4 - 5 - 0 - 8 - 1
• 2 - 4 - 0 - 5 - 8 - 1
• 2 - 4 - 0 - 5 - 8 - 1
  
• 2 - 4 - 0 - 5 - 1 - 8   [ ... ]

Il bubble è chiamato così perché ordina ciascuna coppia di elementi adiacenti. E' un algoritmo di facile comprensione, a discapito della velocità nel caso pessimo. Il codice a sinistra non è quello base, è stato ottimizzato: visto che a ogni iterazione del for più interno l'elemento più a destra è già ordinato, nelle successive iterazioni posso anche non tenere conto di tali elementi. Ovviamente l'esempio riportato sopra è parziale: diventa completo quando il for più esterno termina.

public static int[] QuickSort(int vet[]){
    int sx, dx;
    sx = 0;
    dx = vet.length - 1;
    procedura_quicksort(vet,sx,dx);
    return vet;
}

public static void procedura_quicksort(int vet[], int sx, int dx){
    int i, j;
    int pivot;
    int tmp;
    pivot = vet[(sx + dx) / 2];
    i=sx;
    j=dx;
    while(i<=j){
             while(vet[i] < pivot){
                      i++;
             }
             while(vet[j] > pivot){
                       j--;
             }
             if(i<=j) {
                  if(i<j) {
                  tmp = vet[i];
                  vet[i] = vet[j];
                  vet[j] = tmp;
                  }
             i++;
             j--;
             }
    }
if(sx<j) procedura_quicksort(vet,sx,j);
if(i<dx) procedura_quicksort(vet,i,dx);
}

public static int[] MergeSort(int vet[]){
    procedura_mergesort(vet);
    return vet;
}

public static void procedura_mergesort(int[] vet, int[] VetTmp, int sx, int dx){
    if (sx < dx) {
       int centro = (sx + dx) /2;
       procedura_mergesort (vet, VetTmp, sx, centro);
       procedura_mergesort (vet, VetTmp, centro+1, dx);
       procedura_merge (vet, VetTmp, sx, centro+1, dx);
    }
}

public static void procedura_mergesort(int[] vet){
    int VetTmp [];
    VetTmp = new int [vet.length];
    procedura_mergesort (vet, VetTmp, 0, vet.length-1);
}

public static void procedura_merge(int[] vet, int[] VetAux, int pos_sx, int pos_dx, int PosFine){
    int fine_sx = pos_dx - 1;
    int posAux = pos_sx;
    int x = PosFine - pos_sx + 1;
    while (pos_sx <= fine_sx && pos_dx <= PosFine){
               if ((vet[ pos_sx ])< (vet[pos_dx]))
                   VetAux [posAux++] = vet[pos_sx++];
               else
                   VetAux [posAux++] = vet[pos_dx++];
    }
    while(pos_sx <= fine_sx){
              VetAux [posAux++]=vet[pos_sx++];
    }
    while(pos_dx <= PosFine){
              VetAux [posAux++]=vet[pos_dx++];
     }
     for(int i=0; i<x; i++, PosFine--){
          vet[PosFine]=VetAux[PosFine];
     }
}