Algoritmi – Quicksort

Il QuickSort ordina una lista usando il principio del divide et impera. Nell’algoritmo del quicksort la lista da ordinare viene divisa in due sotto-liste, le sotto-liste vengono ordinate ricorsivamente fintanto che tutta la lista è ordinata.

I passi fondamentali dell’algoritmo del QuickSort sono i seguenti:

Scegliamo un elemento chiave nella lista e chiamiamolo pivot.
Riordiniamo la lista usando la regola che tutti gli elementi più piccoli del pivot vengano messi prima di esso e tutti gli elementi più grandi vengano posizionati dopo. Dopo il partizionamento il pivot si troverà nella sua posizione finale.
Ricorsivamente riordiniamo le due sotto liste: la prima con gli elementi minori e l’altra con quelli maggiori del pivot.

Questa è l’implementazione in C dell’algoritmo del QuickSort:
#include
#include

void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}

int choose_pivot(int i,int j )
{
return((i+j) /2);
}

void quicksort(int list[],int m,int n)
{
int key,i,j,k;
if( m < n)
{
k = choose_pivot(m,n);
swap(&list[m],&list[k]);
key = list[m];
i = m+1;
j = n;
while(i <= j)
{
while((i <= n) && (list[i] <= key)) i++; while((j >= m) && (list[j] > key))
j–;
if( i < j)
swap(&list[i],&list[j]);
}
// swap two elements
swap(&list[m],&list[j]);
// recursively sort the lesser list
quicksort(list,m,j-1);
quicksort(list,j+1,n);
}
}
void printlist(int list[],int n)
{
int i;
for(i=0;i<n;i++)
printf(“%d\t”,list[i]);
}

void main()
{
const int MAX_ELEMENTS = 10;
int list[MAX_ELEMENTS];

int i = 0;

// generate random numbers and fill them to the list
for(i = 0; i < MAX_ELEMENTS; i++ ){
list[i] = rand();
}
printf(“The list before sorting is:\n”);
printlist(list,MAX_ELEMENTS);

// sort the list using quicksort
quicksort(list,0,MAX_ELEMENTS-1);

// print the result
printf(“The list after sorting using quicksort algorithm:\n”);
printlist(list,MAX_ELEMENTS);