Quick sort
void quick_sort (int a[],int l, int r) {
int i, j,v, t;
if (r>l) {
v=a[rl]; //L’elemento “pivot” è quello più a dx
i=l-1; j=r; // i scorre da sx a dx; j da dx a sx
for (;;) {
while ( a[++i]<v);
while ( a[--j]>v);
if (i>=j) break;
t=a[i]; a[i]=a[j]; a[j]=t;
//Scambia gli
//elementi i e j
}
t=a[i]; a[i]=a[r]; a[r]=t;//Sistema l’elemento “pivot”
quick_sort (a, l, i-1);
quick_sort (a, i+1, r);
}
}
i=>j?
i=>j
NO!
Scambio Scambio a[i]
a[i] e a[j] e a[r] r
Quick sort
r>l
l
1
15
3
2
47
47
1
5
i
j
a[i] < v
NO
1
4
temp
a[j] > v?
NO
a[j] > v
pivot
4
v
chiamata ricorsiva
quick_sort (a, l, i-1);
l
3
i-1
1
2
quick_sort (a, i+1, r);
i+1
5
r
7
r>l
l
r
13
13
2
23
i=>j?
NO!
Scambio
a[i] e a[j]
while ( a[++i]<v);
j
i
pivot
1
2
temp
2
v
while ( a[--j]>v);
i=>j?
SI!
Scambio a[i] e a[r]
chiamata ricorsiva
quick_sort (a, l, i-1);
Valore uguale
FINE
quick_sort (a, i+1, r);
Valore uguale
FINE