Cloud with rain
.:G
G:.
0 and 1 serie, black on white
pulled card
myjsp.feelinglinux.com
ver. 1.1.9-4
Hallo, welcome to my world.
Here you can find some stuff about computer science.
<<< Enjoy your visit! >>>
0 and 1 serie, white on black

Informatica di base: ordinamento e ricerca

        Scritto: Giansante Gabriele, 2001     

- Ricerca
- Ricerca esaustiva
- Ricerca binaria
- Ordinamento
- Ordinamento per selezione
- Ordinamento per inserimento
- Ordinamento ShellSort
I problemi di ordinamento e ricerca sono importanti e strettamente collegati fra loro.

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
Il codice e' pseudo-java, comunque non testato praticamente.

Ricerca esaustiva

La ricerca esaustiva e' il tipo di ricerca piu' banale. In pratica, dato un insieme di elementi sul quale sia possibile definire un ordinamento, si scandiscono tutti gli elementi fino a trovare quello cercato, oppure fino alla fine dell'insieme. Nel primo caso, l'algoritmo restituisce il valore "vero", per indicare che l'elemento e' stato trovato. Nel secondo caso, invece, l'algoritmo restituisce il valore booleano "falso", per indicare che l'elemento non e' stato trovato.
La complessita' asintotica dell'algoritmo, rispetto al tempo di esecuzione, e' O(n).

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;
}


Ricerca binaria

Un criterio di ricerca notevole e' la ricerca binaria.
Dato un insieme di elementi ordinato, in modo crescente, l'algoritmo prende l'elemento centrale e lo confronta con la chiave. Se la chiave e' maggiore, allora si ripete lo stesso passo sulla meta' superiore degli elementi. Se invece la chiave e' minore, allora si passa alla meta' inferiore. Il tutto procede finche' non si arriva ad avere un solo elemento che puo' essere o meno quello cercato. Se l'elemento e' quello voluto, allora l'algoritmo restituisce il valore booleano "vero". Altrimenti, il valore booleano restituito e' "falso".
La complessita' asintotica dell'algoritmo, rispetto al tempo di esecuzione, e' O(log(n)).
Per maggiore chiarezza, vediamo l'applicazione dell'algoritmo alla sequenza (2,4,5,6,7,8,10) con chiave "5":
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)
Gli elementi tratteggiati sono quelli su cui agisce volta per volta l'algoritmo. Evidenziato in verde c'e' il valore centrale della porzione di elementi.

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

I tipi di ordinamento presentati sono tre:
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')
Il codice e' pseudo-java, comunque non testato praticamente.

Ordinamento per selezione

L' ordinamento per selezione e' uno dei piu' semplici.
Dato un insieme di elementi, su cui sia possibile definire un ordinamento, da ordinare, l'algoritmo prende quello con valore piu' basso e lo scambia con l'elemento al primo posto nell'inseme (es. 10,6,2,7,5,4,8 => 2,6,10,7,5,4,8 : e' stato scambiato il 2 perche' elemento con valore piu' basso).
Lo stesso procedimento viene applicato all'insieme formato dagli elementi successivi al primo (es. 2,6,10,7,5,4,8 => 2,4,10,7,5,6,8 : il valore piu' basso era il 4, che e' stato scambiato col primo degli elementi rimasti).
Si continua cosi' finche' l'insieme rimanente non contiene un solo elemento.
Alla fine, l'insieme risulta ordinato in modo crescente. L'ordine e' sicuro perche' per costruzione vengono considerati elementi sempre non decrescenti (crescenti o uguali). E' facile ricavare il metodo per ottenere un ordinamento decrescente.
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) gia' introdotta:
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
La complessita' e' alta perche' vanno contati anche i confronti da eseguire per la ricerca del valore minimo nell'insieme rimasto.

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;
    }
  }


Ordinamento per inserimento

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
La complessita' e' alta perche' vanno contati anche le operazioni per riordinare i primi "i" elementi.

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;
    }
  }


Ordinamento ShellSort

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)
Il primo confronto avviene fra 6 e 5, il secondo fra 7 ed 1, il terzo fra 8 e 6.
Una volta finiti i confronti (devono avvenire uno dopo l'altro, mai contemporaneamente), si diminuisce l'incremento e si ricomincia con il nuovo.
L'ultimo incremento usabile, avente valore 1, porta all'ordinamento definitivo e corretto dell'array.
Pubblicita'

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)
La complessita' asintotica dell'algoritmo, rispetto al tempo di esecuzione, e' O(n^1/2) (radice di n).
Vediamo, per esempio, l'ordinamento della sequenza (5,7,8,1,2,4,3).
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;
          }
        }
      }
    }
  }

Hai trovato utile questo articolo?
Aiutami a condividerlo o metti un "mi piace".
Grazie mille!


Gli strumenti di condivisione (Google+, Facebook) sono visibili in alto a destra solo dopo aver accettato la policy di utilizzo dei cookie per questo sito.
FAQ - Come faccio a cambiare la mia scelta?

 

Strumenti (myjsp.feelinglinux.com)
Gioco: allenamento con la tastiera Strumenti di codifica/decodifica URI (%-encoding) e Base64 Strumenti di calcolo online per IP e Reti
QUIZ GAME
Quiz game

Cerca @myjsp.feelinglinux.com

Pubblicita'