[Pillola][Tutorial] Principali algoritmi di ordinamento in c++

[Slimmy]

Intanto posso postare un paio di algoritmi anche io:

Bubblesort

void bubblesort (int *vett,int len) 
{
	for (int i=len;i>0;i--) 
               {
		for (int j=1;j<i;j++) 
                        {
			if (vett[j]<vett[j-1]) 
                                swap(&vett[j],&vett[j-1]);
		}
	}
}

Bubblesort Modificato

void bubblesort (int *vett,int len) 
{
        int scambiati=0;
	for (int i=len;i>0;i--) 
               {
		for (int j=1;j<i;j++) 
                        {
			if (vett[j]<vett[j-1]) 
                               {
                                swap(&vett[j],&vett[j-1]);
                                scambiati=1;
                         }
		}
                 if (scambiati==0)
                         break;
	}
}

PS: il bubblesort modificato non l'ho provato... ditemi se va..


PPS: lo swap è una banalissima funzione che scambia il contenuto delle variabili.


Spiegazione veloce del bubblesort..
Ho postato due versioni.
La prima è il classico bubblesort.
Ha prestazioni di O(n^2) in tutti i casi.
Cosa fa il bubblesort? ad ogni scorrimento dell'array l'elemento più "pesante" (più grande) arriva in fondo.
Questo lavoro lo fa n volte, dove n è la dimensione dell'array.

Il bubblesort modificato invece introducendo una semplice variabile usata come booleana si interrompe quando l'array è ordinato.
Quest'accorgimento permette di migliorare le prestazioni che nel caso migliore (array già ordinato) arrivano a O(n)

[Eclipse]

grazie slimmy, ecco heapsort e quicksort, ho anche messo la funzione swap che può essere usata col tuo.. appena ho tempo spiego per bene il tutto

///////// HEAPSORT /////////////////////////
void heapify ( int* A , int newnode )
{
  int done=0, dad, temp;
  dad = ( newnode - 1 ) / 2;

  while( dad >= 0 && !done)
  {
    if(A[newnode] > A[dad])
     {
       temp = A[newnode];
       A[newnode]=A[dad];
       A[dad]=temp;
       newnode = dad;
       dad = dad/2;
     }
     else
     done = 1;

  }
}

void heapsort ( int* A, int last )
{
   int i,temp;
   while(last > 0 )
   {
   temp = A[0];
   A[0]=A[last];
   A[last]= temp;
   for(i=0;i<last;i++) heapify(A,i);
   last--;
   }
}
////////////////////////////////////////////////////////////

///////// QUICKSORT ////////////////////////////////////
void swap (int& a, int& b) {
int temp = 0;
	temp = a;
	a = b;
	b = temp;
};

void quicksort (int* A, int left, int right) {
int i = 0, j = 0, pivot = 0;

        i = left;
        j = right;
        pivot = A[(left + right) / 2];
        do {
	        while (A[i] < pivot)
		        i++;
                while (A[j] > pivot )  j--;             
                if (i <= j) {            
		        swap (A[i], A[j]);
	                i++;
	                j--; 
	              };
        }
        while  (!(i > j)); 
        if (left < j)  // Se 'left' è minore di 'j' allora
                quicksort(A, left, j); 
        if (i < right) // Se 'i' è minore di 'right' allora
                quicksort(A, i, right);
};
////////////////////////////////////////////////////////////

per usare l'heapsort si deve prima chiamare heapify dalla fine all'inizio dell'array così:

cout << "\n\nHeapsort\nArray di partenza:\n";
   for (c=0; c<SIZE; c++) {A[c]=array[c]; cout<<A[c]; cout<<" ";}
   for(c=0;c<SIZE;c++) heapify(A,c);
   cout << "\nHeap:\n";
   for (c=0; c<SIZE; c++) {cout<<A[c]; cout<<" ";}
   heapsort(A, SIZE-1);
   cout << "\nArray ordinato:\n";
   for (c=0; c<SIZE; c++) {cout<<A[c]; cout<<" ";}

questo invece per il quicksort

cout << "\n\nQuicksort\nArray di partenza:\n";
   for (c=0; c<SIZE; c++) {A[c]=array[c]; cout<<A[c]; cout<<" ";}
   quicksort(A, 0,SIZE-1);
   cout << "\nArray ordinato:\n";
   for (c=0; c<SIZE; c++) {cout<<A[c]; cout<<" ";}

[Slimmy]

Aggiunto il commento al bubblesort.

Una cosa eclipse..
La tua versione di swap è per c++ perchè usi i reference.
Posto la versione con i puntatori utilizzabile in C ( e nella mia versione di bubblesort!)

void swap(int *a, int *b) 
{
	int temp=*a;
	*a=*b;
	*b=temp;
}