• Ricerca
• Ricerca esaustiva
• Ricerca binaria
• Ordinamento
• Ordinamento per selezione
• Ordinamento per inserimento
• Ordinamento ShellSort

La "ricerca" deve la propria importanza alla necessita', in molte applicazioni (ad esempio nei database), di verificare l'esistenza di determinati elementi (detti chiavi) all'interno di un insieme, o di estrarre tali elementi dall'insieme stesso.
Naturalmente, se l'insieme, su cui deve essere effettuata la ricerca, e' gia' ordinato, le cose si semplificano e si velocizzano. Ecco quindi che si evidenzia lo stretto collegamento fra "problema di ricerca" e "problema di ordinamento".

Per entrambi, fra gli scopi primari, vie' l'efficienza rispetto al tempo di esecuzione. Tale necessita' e' spesso giustificata dalla grande mole di dati gestiti e dalla frequenza di accesso ai dati stessi.

Verranno mostrati  i principali metodi di ricerca ed ordinamento, completi di indicazione sulla complessita' (in termini di tempo di esecuzione) e di codice java che implementa gli algoritmi.
Per semplicita', gli insiemi da ordinare, verranno rappresentati come array di interi presenti in memoria.

Ricerca

I tipi di ricerca presentati sono due:

Ricerca esaustiva, ovvero la ricerca elemento per elemento, fino a trovare quello voluto.
Ricerca binaria, ovvero la ricerca piu' veloce

Viene infine mostrato il codice java che realizza l'algoritmo. La funzione riceve in ingresso un array di interi,
contenente gli elementi, il numero degli elementi nell'array e la chiave di ricerca.

Codice Java - Algoritmo di ricerca esaustiva:

boolean RicercaEsaustiva(int[] Insieme, int NumeroElementi, int Chiave)
{
  int i = 1;
  for (i; (i <= NumeroElementi) && (Chiave != Insieme[i]); i++)
  {}
  if (i > NumeroElementi) return false;
  else return true;
}

2,4,5,6,7,8,10 => 2,4,5,6,7,8,10  (6 e' superiore a 5)
2,4,5,6,7,8,10 => 2,4,5,6,7,8,10  (4 e' inferiore a 5)

Viene infine mostrato il codice java che realizza l'algoritmo. La funzione riceve in ingresso un array di interi,
contenente gli elementi, il numero degli elementi nell'array e la chiave di ricerca. Per comodita' viene usata un'implementazione ricorsiva.

Codice Java - Algoritmo di ricerca binaria:

  //Alto e' la parte verso i valori piu' grandi, mentre Basso e'
  //la parte verso i valori piu' piccoli.
  boolean RB(int[] Insieme, int Basso, int Alto, int Chiave)
  {
    if (Alto < Basso)
    {
      //Se sono qui, significa che l'elemento non e' stato trovato.
      return false;
    }
    else
    {
      //Calcolo il nuovo centro.
      int i = Math.round((Alto + Basso) / 2);
      if (Insieme[i] > Chiave)
      {
        //Chiave minore dell'elemento centrale => meta' inferiore
        return RB(Insieme, Basso, i - 1, Chiave);
      }
      else
      {
        //Chiave maggiore dell'elemento centrale => meta' superiore
        if (Insieme[i] < Chiave) return RB(Insieme, i + 1, Alto, Chiave);
        else return true; //Trovato: Chiave = Elemento
      }
    }
  }

  //Funzione che lancia la ricerca
  boolean RicercaBinaria(int[] Insieme, int NumeroElementi, int Chiave)
  {
    //Inizio ricorsione: i limiti in cui cercare corrispondono ai limiti dell'array.
    return RB(Insieme,1,NumeroElementi,Chiave);
  }

Ordinamento per selezione
Ordinamento per inserimento
Ordinamento Shell, ovvero uno dei piu' veloci ed in certe condizioni comparabile con il QuickSort (di cui non si parlera')

10,6,2,7,5,4,8 => 2,6,10,7,5,4,8
2,6,10,7,5,4,8 => 2,4,10,7,5,6,8
2,4,10,7,5,6,8 => 2,4,5,7,10,6,8
2,4,5,7,10,6,8 => 2,4,5,6,10,7,8
2,4,5,6,10,7,8 => 2,4,5,6,7,10,8
2,4,5,6,7,10,8 => 2,4,5,6,7,8,10

Viene infine mostrato il codice java che realizza l'algoritmo. La funzione riceve in ingresso un array di interi, contenente i valori da ordinare, ed il numero degli elementi nell'array.

Codice Java - Algoritmo di ordinamento per selezione:

  void OrdinamentoSelezione(int[] Insieme, int NumeroElementi)
  {
    int i = 1;
    for (i; i < NumeroElementi; i++)
    {
      int k = i;
      int Elemento = Insieme[i];
      //Il primo elemento fra quelli rimasti e' stato gia' messo in "Elemento",
      //quindi parto da i+1.
      int j = i + 1;
      //Cerca l'elemento piu' piccolo fra quelli rimasti.
      for (j; j <= NumeroElementi; j++)
      {
        if (Insieme[j] < Elemento)
        {
          k = j;
          Elemento = Insieme[j];
        }
      }
      //Effettua lo scambio fra il primo elemento di quelli rimasti e quello 
      //piu' piccolo trovato in precedenza.
      Insieme[k] = Insieme[i];
      Insieme[i] = Elemento;
    }
  }

Dato un insieme di elementi, su cui sia possibile definire un ordinamento, l'algoritmo scandisce progressivamente l'insieme a partire dal secondo elemento fino ad arrivare all'ultimo. Ogni elemento di posizione "i", all'interno dell'insieme, viene inserito in ordine nell'insieme formato dagli elementi dalla posizione 1 alla i.
E' da notare che, per la costruzione dell'algoritmo, per ogni "i", gli elementi di posizione "1,...,(i-1)" sono gia' ordinati.
Un esempio di iterazione e' il seguente: "i=4"; 3,9,32,5,7,8,3=>3,5,9,32,7,8,3   Il trattino sotto indica l'elemento puntato da "i". Nella sequenza risultato il valore di "i" e' stato incrementato al valore successivo.
Alla fine, l'insieme risulta ordinato in modo crescente.
La complessita' asintotica dell'algoritmo, rispetto al tempo di esecuzione, e' O(n^2).
Per maggiore chiarezza, vediamo l'applicazione dell'algoritmo alla sequenza (10,6,2,7,5,4,8):

i=2; 10,6,2,7,5,4,8 => 6,10,2,7,5,4,8
i=3; 6,10,2,7,5,4,8 => 2,6,10,7,5,4,8
i=4; 2,6,10,7,5,4,8 => 2,6,7,10,5,4,8
i=5; 2,6,7,10,5,4,8 => 2,5,6,7,10,4,8
i=6; 2,5,6,7,10,4,8 => 2,4,5,6,7,10,8
i=7; 2,4,5,6,7,10,8 => 2,4,5,6,7,8,10

Viene infine mostrato il codice java che realizza l'algoritmo. La funzione riceve in ingresso un array di interi,
contenente i valori da ordinare, ed il numero degli elementi nell'array.

Codice Java - Algoritmo di ordinamento per inserimento:

  void OrdinamentoInserimento(int[] Insieme, int NumeroElementi)
  {
    int i = 2;
    for (i; i <= NumeroElementi; i++)
    {
      int Elemento = Insieme[i];
      //L'elemento va posizionato fra i primi i-1 elementi.
      int j = i - 1;
      //Sposta verso l'alto tutti gli elementi piu' grandi di quello da inserire.
      for (j; (j > 0) && (Elemento < Insieme[j]); j--)
      {
        Insieme[j + 1] = Insieme[j];
      }
      //Effettua l'inserimento dell'elemento.
      Insieme[j + 1] = Elemento;
    }
  }

Il metodo Shellsort non e' molto semplice ma abbastanza efficiente.
Dato un insieme di elementi, su cui sia possibile definire un ordinamento, l'algoritmo si basa sul concetto di incremento, cioe' di distanza fra gli elementi da confrontare (in termini di differenza degli indici di posizione). A partire dal primo elemento, vengono confrontati quello selezionato e quello a distanza n (con n pari all'incremento) nell'array da ordinare (verra' considerato un array di interi, per semplicita'). Se il primo elemento (indice piu' basso) e' maggiore del secondo (indice piu' alto), allora i due elementi vengono scambiati e si passa al confronto successivo.
Ad esempio, con un incremento pari a 5, si evidenziano con lo stesso "stile grafico" i seguenti elementi relativi ai primi 3 confronti:

6,7,8,2,4,5,1,6,3,7,4,0,1

1         6               (incremento = 6-1 = 5)

Come si puo' vedere dalla descrizione dell'algoritmo, non e' stato posto alcun vincolo ne' sulla scelta dell'incremento iniziale, ne' sulla scelta riguardante la dimensione della diminuzione di tale incremento: i due valori sono arbitrari.
Prima di dare alcune linee guida sulla scelta degli incrementi, bisogna osservare che sono due le ipotesi di partenza da soddisfare. La prima riguarda l'incremento massimo da usare: non deve essere maggiore della dimensione dell'array diminuita di 1, altrimenti si supererebbero i limiti dell'array stesso.
La seconda ipotesi prevede la non esistenza di incrementi con valore minore di 1.
Ecco, quindi, come manipolare gli incrementi. Come incremento iniziale, di solito si prende il valore "n div 2" dove n e' la dimensione dell'array. Si possono considerare anche valori piu' bassi, ma si rischierebbe di raggiungere un ordinamento finale solo parziale. Se si fosse sicuri del non verificarsi dei "casi peggiori", allora risulterebbe piu' efficiente considerare, inizialmente, valori inferiori ad "n div 2".
Piu' o meno vale lo stesso discorso per la variazione dell'incremento nelle fasi di ordinamento. Si e' piu' sicuri con diminuzioni unitarie, ma si possono usare criteri differenti.
L'algoritmo presentato alla fine, diminuiscel'incremento del valore "i div 2" dove i e' quello precedente.
Un ordinamento finale corretto lo si ottiene con sicurezza, e per tutte le combinazioni di numeri nell'array, con valore iniziale "n div 2" e diminuzioni unitarie. Per convincersi della cosa, si puo' provare ad ordinare una sequenza del tipo

(n,n-1,n-2,...,3,2,1)

incremento = 7 div 2 = 3
5,7,8,1,2,4,3
1,7,8,5,2,4,3
1,2,8,5,7,4,3
1,2,4,5,7,8,3
1,2,4,3,7,8,5
incremento = 3-1 = 2
1,2,4,3,7,8,5
...
1,2,4,3,7,8,5
1,2,4,3,5,8,7
incremento = 2-1 =1
1,2,4,3,5,8,7
...
1,2,4,3,5,8,7
1,2,3,4,5,8,7
...
1,2,3,4,5,8,7
1,2,3,4,5,7,8

Infine, ecco il codice java che realizza l'algoritmo. La funzione riceve in ingresso un array di interi,
contenente i valori da ordinare, ed il numero degli elementi nell'array. L'algoritmo, per funzionare prevede un funzionamento leggermente diverso da quanto descritto: effettua confronti anche indietro, per uno stesso incremento, in modo da ottenere un ordinamento finale corretto.

Codice Java - Algoritmo di ordinamento shellsort:

  void OrdinamentoShell(int[] Insieme, int NumeroElementi)
  {
    //Calcolo dell'incremento
    int Incremento = NumeroElementi / 2;
    //Ciclo di diminuzione degli incrementi
    for ( Incremento; Incremento > 0; Incremento = Incremento / 2)
    {
      int i = Incremento + 1;
      //Andamento normale dei confronti per un fissato incremento.
      for ( i; i <= NumeroElementi; i++)
      {
        int j = i - Incremento;
        //Eseguo confronti all'indietro
        for ( j; j > 0; j = j - Incremento)
        {
          int k = j + Incremento;
          if (Insieme[j] <= Insieme[k])
          {
            j = 0;
          }
          else
          {
            //Scambio
            int app = Insieme[j];
            Insieme[j] = Insieme[k];
            Insieme[k] = app;
          }
        }
      }
    }
  }