Algoritmi in pillole: bubble sort

Animazione dell'algoritmo di Bubble sort da wikipedia

Animazione dell'algoritmo di ordinamento bubble sort da wikipedia

L'algoritmo controlla ogni coppia di elementi adiacenti  e li scambia se non sono ordinati. L'algoritmo procede così fino a quando non ci sono più scambi da fare. 

pseudocodice:

"per i che varia da 0 a N-1
   per j che varia da N-1 a i+1
      se l'elemento j è minore dell'elemento j-1
        allora scambia l'elemento j con l'elemento j-1"

Codice:

void bubblesort(int v[], int n) {
  int i=0,j,temp;
  int scambio = FALSE;
  do {
    scambio=FALSE;
    for (j=n-1;j>i;j--)
      if (v[j]<v[j-1]) {
        temp=v[j];
        v[j]=v[j-1];
        v[j-1]=temp;
        scambio=TRUE;
      }
      i=i+1;
    } while(i<n-1 && scambio);
}

La complessità computazionale asintotica è O(n^2).
Caso peggiore: array ordinato in senso inverso - T. esec. prop. a n^2
Caso migliore: array già ordinato                     - T. esec. prop. a n

Algoritmi in pillole C: ordinamento con insertion sort

Animazione dell'algoritmo Insertion sort da Wikipedia

Se l'ordine desiderato è quello crescente,  l'algoritmo parte dall'ipotesi che l'array da ordinare sia composto da un primo elemento ordinato e una seconda parte "disordinata". Esamina quindi il primo elemento disordinato confrontandolo con tutti gli elementi "ordinati". Ad ogni confronto, se l'elemento disordinato è minore di quello ordinato si "inserisce", da qui il nome dell'algoritmo, l'elemento disordinato al posto di quello ordinato, scambiandoli di posto. Al termine di questa fase si avrà una parte ordinata composta da due elementi e una parte disordinata composta da N-2 elementi. L'algoritmo continua ad esaminare la parte disordinata fino alla fine dell'array.

Pseudocodice:

"per i che varia da 1 a N
   per j che varia da i a 0
     se l'elemento j è minore dell'elemento i allora
       scambia l'elemento i con l'elemento j"

Codice:

void insertSort(int * ar, int  n)
{
  int  i, j, temp;
  for (i = 1; i < n; t++){
    j = i;
    while( (j > 0) && (ar[j] < ar[j - 1] )) {
      temp = ar[j];
      ar[j] = ar[j - 1];
      ar[j - 1] = temp;
      j--;
    }
  }
}

La complessità computazionale asintotica è O(n^2).

Caso peggiore: array ordinato in senso inverso - T. esec. prop. a n^2
Caso migliore: array già ordinato                      - T. esec. prop. a n

Algoritmi in pillole C: ordinamento con selection sort

Selection sort animata da wikipedia

Se l'ordine desiderato è quello crescente,  l'algoritmo "seleziona" il valore più piccolo dell‟array di n elementi e lo scambia con quello al primo posto. Successivamente, "seleziona" il più piccolo tra gli n-1 elementi rimasti e lo scambia con quello al secondo posto, e così via fino a che non rimane un solo elemento, l'ultimo e il più grande. 

pseudocodice:

"per i che varia da 1 a  N   per j che varia da i+1 a N       se l'elemento j è minore dell'elemento i allora          scambia i con j"

Codice:

void selectionsort(int v[], int n){
 int i,j,min,temp;
 for (i=0;i<n-1;i++) {
   min=i;
   for (j=i+1;j<n;j++)
     if (v[j]<v[min]) min=j;
   temp=v[i];
   v[i]=v[min];
   v[min]=temp;
 }
}

La complessità computazionale asintotica è O(n^2).
Caso peggiore: array ordinato in senso inverso - T. esec. prop. a n^2
Caso migliore: array già ordinato                     - T. esec. prop. a n^2