next up previous contents index
Next: Funzioni ricorsive Up: Ordinare un array Previous: Ordinare un array   Indice   Indice analitico

Selection sort

Il nome del primo algoritmo di ordinamento per array che studiamo è selection sort. Il funzionamento è molto semplice: si scorre l'array da sinistra destra (o dall'alto verso il basso, dipende dal modello mentale che ci siamo costruiti) e si porta in cima l'elemento più piccolo. Semplice no? Vediamo come si può implementare tale algoritmo in C++:

// ex6_3_1.cpp
// selection sort
#include <iostream.h>
#include <stdlib.h>
#include <time.h>

// scambia due interi
void scambia (int& a, int& b) {
  int t = a;
  a = b;
  b = t;
}

// ordina un array di interi da inf a sup
void selectionSort (int v[], int inf, int sup) {
  for (int i = inf; i < sup; i++) {
    int min = i;
    for (int j = i + 1; j < sup; j++)
      if (v[j] < v[min])
        scambia (v[j], v[min]);
  }
}

void stampa (int v[], int inf, int sup) {
  for (int i = inf; i < sup; i++)
    if (i % 5 == 4)
      cout << v[i] << "\n";
    else
      cout << v[i] << "\t";
}

void main() {
  const int N = 20;
  int v[N];
  // inserisce N numeri a caso nel vettore
  srand ( time(0) );
  for (int i = 0; i < N; i++)
    v[i] = rand() % 100 + 1;

  cout << "vettore disordinato:\n";
  stampa (v, 0, N);
  selectionSort (v, 0, N);
  cout << "\nvettore ordinato:\n";
  stampa(v, 0, N);
}

esempio di output:
vettore disordinato:
 58 96 89 15 28
 18 32 87 18 74
 90 7 65 19 93
 75 17 62 68 3

vettore ordinato:
 3 7 15 17 18
 18 19 28 32 58
 62 65 68 74 75
 87 89 90 93 96

Come si vede, con sole 8 righe di codice si riesce ad ordinare un array; si sappia comunque che questo metodo è poco efficiente; il tempo di ordinamento, infatti, cresce circa al quadrato all'aumentare del numero di elementi (cioè se per ordinare un gruppo di dati ci vuole un certo tempo, raddoppiando il numero dei dati, il tempo necessario è almeno quattro volte superiore). Comunque nei nostri futuri esempi utilizzeremo sempre tale metodo, perché facile da capire e da memorizzare, e sufficiente ai nostri scopi; come è ovvio, nei nostri esempi non dovremo mai ordinare un numero di dati tale da potere apprezzare sensibilmente la differenza di tempo di esecuzione tra questo metodo di ordinamento ed un altro, anche molto più efficiente (provando il programma su una macchina con un processore Intel Pentium II, ci vogliono circa 1.5 secondi ad ordinare diecimila interi con il selection sort).


next up previous contents index
Next: Funzioni ricorsive Up: Ordinare un array Previous: Ordinare un array   Indice   Indice analitico
Claudio Cicconetti
2000-09-06