Algorithm:
private static int partition(Comparable
[] a
, int lo
, int hi
)
{
int i
= lo
, j
= hi
+1;
while (true)
{
while (less(a
[++i
], a
[lo
]))
if (i
== hi
) break;
while (less(a
[lo
], a
[--j
]))
if (j
== lo
) break;
if (i
>= j
) break;
exch(a
, i
, j
);
}
exch(a
, lo
, j
);
return j
;
}
public class Quick
{
private static int partition(Comparable
[] a
, int lo
, int hi
)
{ }
public static void sort(Comparable
[] a
)
{
StdRandom
.shuffle(a
);
sort(a
, 0, a
.length
- 1);
}
private static void sort(Comparable
[] a
, int lo
, int hi
)
{
if (hi
<= lo
) return;
int j
= partition(a
, lo
, hi
);
sort(a
, lo
, j
-1);
sort(a
, j
+1, hi
);
}
}
2. Complexity: Proposition. The average number of compares CN to quicksort an array of N distinct keys is ~ 2N lnN (and the number of exchanges is ~ ⅓ N ln N).
