Quick Sort è un altro algoritmo per ordinare gli elementi di una lista (array,collection). In questo metodo un array a[1],...,a[n] si ordina selezionando un valore dell array come elemento chiave.
Poi scambiamo di posto il primo elemento dell'array con la chiave, così che la chiave occupi il primo posto nell array. Troviamo in questo modo il posto giusto per la chiave. Il posto giusto e quallo nella quale tutti gli elementi alla sua sinistra sono più piccoli e tutti quelli alla sua destra sono più grandi. Per ottenere la giusta posizione per la chiave, scorriamo la lista in tutte e due le direzioni usando gli indici i e j . Se la
lista che vogliamo ordinare ha indice che vanno da m ad n inizializziamo i all'inidice m+1 dove m è l'indice della chiave.
L'indice i viene incrementato finché non troviamo un'elemento alla posizione i che è più grande della chiave. Nello stesso modo inizializziamo j e n e lo decrementiamo finché non troviamo un'elemento con un valore minore di quella della chiave.
In seguito controlliamo se i e j si sono incrociati(j<i).Se no scambiamo di posto l'elemento chiave al indice m con quello nell posto j. Questo porta l'elemento chiave nella posizione j ,e abbiamo che gli elementi alla sua sinistra sono piu piccoli di lui, e quelli a destra più grandi. Possiamo dividere la lista in due sottoliste.
La prima sottolista è composta dagli elementi con indice m fino all'indice (j-1), e la secondo lista consiste dagli elementi con indice (j+1) fino all'indice n. Poi ripetiamo il procedimento che abbiamo fatto sopra in ciascuna delle sottoliste.
Scelta della chiave
Un altro problema è quello della scelta della chiave(key).Possiamo scegliere uno qualunque. La scelta dell primo elemento non è sempre la migliore.Di solito si sceglie un elemento vicino alla metà della lista.
Quindi la nostra funzione posizione_chiave() sara:
int posizione_chiave(int i, int j){
return ((i+j)/2);
}
Un altro modo molto più efficiente per scegliere la posizione della chiave è quella di usare un random number generator.
void qsort(int list[],int m,int n)
{
int key,i,j,k;
if( m < n)
{
k = posizione_chiave(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(&list[m],&list[j]);
qsort(list[],m,jl);
qsort(list[],j+1,n);
}
}
questa è la funzione che realizza il nostro algoritmo.
k - posizione della chiave.
m - inizio della lista
n - indice finale della lista
scegliamo la posizione della nostra chiave
mettiamo la nostra chiave come primo
elemento
inizializziamo gli indici.
questo loop
scorre tutti gli elementi alla sua
sinistra, per trovare un elemento che è più
grande della chiave.
scorre tutti gli elementi alla sua destra, per
trovare un elemento che e più piccolo della
chiave.
se gli indici non si sono incrociati
scambiamo di posto gli elementi i e j
creiamo due nuove sottoliste e
applichiamo a loro lo stesso algoritmo
quick sort.
quick_sort.c
#include <stdio.h>
#define MAX 10
/******************************************************************
* la funzione swap realizza lo scambio dei elementi****
*******************************************************************/
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
/*****************************************************************
** date come input due interi questa funzione **********
** calcola laposizione della chiave **********************
*****************************************************************/
int posizione_chiave(int i,int j )
{
return((i+j) /2);
}
/****************************************************************
*** questo funzione realiza l'algoritmo dell *************
*** quick sort, prende come input una lista ************
*** l'inizio e la fine di questa lista e' lo ordina *********
****************************************************************/
void qsort(int list[],int m,int n)
{
int key,i,j,k; //key -- valore della chiave, k-- posizione della chiave
if( m < n)
{
k = posizione_chiave(m,n); // trova la posizione della chiave
swap(&list[m],&list[k]); // scambia la chiave con il primo elemento
key = list[m]; // della lista
i = m+1; // inizializziamo gli indici secondo
j = n; // l'algoritmo
while(i <= j)
{
while((i <= n) && (list[i] <= key)) // controlla gli elementi a destra
i++; // della chiave
while((j >= m) && (list[j] > key)) // controlla gli elementi a sinistra
j--; // della chiave
if( i < j) // se gli indici non si incrociano scambiamo il
swap(&list[i],&list[j]); // posto dei elementi "i" e "j"
}
swap(&list[m],&list[j]); // creiamo due sotto liste
qsort(list,m,j-1); // e applichiamo l'algoritmo alle due sotto liste
qsort(list,j+1,n);
}
}
/******************************************************************
** la funzione readList legge dalla tastiera(stdin) *******
** un array di lungezza n ************************************/
void readlist(int list[],int n)
{
int i;
printf("Inserire gli elementi\n");
for(i=0;i<n;i++)
scanf("%d",&list[i]); //funzione per prendere dall stdin dei charatteri
}
/****************************************************************
** la funzione printlist, data un array di lungezza n ***
** lo stampa in stdout *************************************
****************************************************************/
void printlist(int list[],int n)
{
int i;
printf("Gli elementi della lista sono: \n");
for(i=0;i<n;i++){
printf("%d\t",list[i]);
}
printf("\n");
}
void main()
{
int list[MAX], n;
printf("Enter the number of elements in the list max = 10\n");
scanf("%d",&n);
readlist(list,n);
printf("The list before sorting is:\n");
printlist(list,n);
qsort(list,0,n-1);
printf("\nThe list after sorting is:\n");
printlist(list,n);
}
You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near '' at line 1
.gif){kind=small}
.gif){kind=small}
