1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include<stdio.h>
#include<stdlib.h>
// Procedura per lo scambio dei valori tra due variabili
void swap (int *a, int *b) {
int tmp;
tmp=*a;
*a=*b;
*b=tmp;
}
void qSort(int *v, int first, int last){
int i,j,pivot;
if (first<last) {
// Partenza: i parte dal primo elemento del vettore, j dall'ultimo
i = first; j = last;
// Il pivot è l'elemento medio del vettore
pivot = v[(first + last)/2];
do {
// Finché l'elemento generico i-esimo a sinistra del pivot
// è minore del pivot, incrementa i
while (v[i] < pivot) i++;
// Finché l'elemento generico j-esimo a destra del pivot
// è maggiore del pivot, decrementa j
while (v[j] > pivot) j--;
// Altrimenti, scambia tra loro l'elemento i-esimo e quello j-esimo
if (i <= j) {
swap(&v[i], &v[j]);
i++, j--;
}
} while (i <= j); // Cicla finché i e j non si incontrano
// Richiama il quick sort sul primo sottovettore
qSort(v, first, j);
// Richiama il quick sort sul secondo sottovettore
qSort(v, i, last);
}
}
int main() {
int *v;
int i,n;
printf ("Quanti elementi vuoi inserire nell'array? ");
scanf ("%d",&n);
v = (int*) malloc(n*sizeof(int));
for (i=0; i<n; i++) {
printf ("Elemento n.%d: ",i+1);
scanf ("%d",&v[i]);
}
qSort (v,v[0],v[n]);
printf("Vettore ordinato:");
for (i=0; i<n; i++)
printf ("%d,",v[i]);
free(v);
return 0;
}
|
