Ordinamenti ingenui

di

Due elementi

Scambiare i valori contenuti nell’array v alle posizioni a e b

void SCAMBIA(double v[], int a, int b)
{
   double temp=v[a];
   v[a]=v[b];
   v[b]=temp;
}

Ordinare un array di due elementi

if(v[0] > v[1])
   SCAMBIA(v, 0, 1);

oppure…

if(v[0] > v[1])
{
   double temp=v[0];
   v[0]=v[1];
   v[1]=temp;
}

Ordinare un sottoarray di due elementi

if(v[pos] > v[pos+1])
   SCAMBIA(v, pos, pos+1);

Bubble sort

Una passata su tutte le n-1 coppie, all’interno di un array, provoca lo spostamento in alto della bolla più grande

for(int j=0; j < v.length-1; j++)
   if(v[j] > v[j+1])
      SCAMBIA(v, j, j+1);

Cioè l’elemento più grande si trova in ultima posizione alla fine della passata.

N passate, sulle n-1 coppie, ordinano sicuramente l’array

void BUBBLESORT(double v[])
{
   int n=v.length;
   for(int i=0; i < n; i++)
      for(int j=0; j < n-1; j++)
         if(v[j] > v[j+1])
            SCAMBIA(v, j, j+1);
}

In realtà sono necessarie al massimo n-1 passate su n-i coppie

void BUBBLESORT(double v[])
{
   int n=v.length;
   for(int i=0; i < n-1; i++)
      for(int j=0; j < n-i-1; j++)
         if(v[j] > v[j+1])
            SCAMBIA(v, j, j+1);
}

Selection sort

Si può individuare il valore minimo nell’array e scambiarlo con il valore alla posizione 0 (in questo modo l’elemento alla posizione 0 occupa il posto che gli spetta…)

int posMin=0;
for(int j=1; j < n; j++)
   if(v[j] < v[posMin])
      posMin=j;
SCAMBIA(v, 0, posMin);

Ripetendo la stessa operazione con il sottovettore

  • da 1 a n-1
  • da 2 a n-1
  • ...
  • da n-2 a n-1

sarà al suo posto l'elemento alla posizione

  • 1
  • 2
  • ...
  • n-2

L'elemento alla posizione n-1 occuperà necessariamente l'unico posto rimasto...

void SELESORT(double v[])
{
   int n=v.length;
   for(int i=0; i < n-1; i++)
   {
      int posMin=i;
      for(int j=i+1; j < n; j++)
         if(v[j] < v[posMin])
            posMin=j;
      SCAMBIA(v, i, posMin);
   }
}