Java Reference
In-Depth Information
Now we can telescope:
()
N
1
TN
TN
1
(
-
)
2
N
1
=
+
-------------
---------------------
-------------
+
N
+
TN
1
(
-
)
TN
2
(
-
)
2
=
+
---------------------
---------------------
----
N
N
1
-
(8.9)
TN
2
(
-
)
TN
3
(
-
)
2
N
1
=
+
---------------------
---------------------
-------------
N
1
-
N
2
-
-
…
T
2
()
3
T
1
()
2
2
-----------
=
-----------
+
---
If we add all the equations in Equation 8.9, we have
()
N
1
TN
T
1
()
2
1
1
1
1
N
1
⎛
⎞
-------------
=
+
2
++ + +
…
-----------
---
---
----
-------------
⎝
⎠
+
+
(8.10)
1
1
1
N
1
5
⎛
⎞
=
21
+++ +
…
-
---
---
-------------
---
⎝
⎠
+
=
ON
(
log
)
The last line in Equation 8.10 follows from Theorem 5.5. When we multiply
both sides by
We use the fact
that the
N
th har-
monic number is
O
( log
N
)
.
N
1
+
, we obtain the final result:
TN
()
=
ON N
(
log
)
(8.11)
8.6.3
picking the pivot
Now that we have established that quicksort will run in
O
(
N
log
N
) time on
average, our primary concern is to ensure that the worst case does not occur.
By performing a complex analysis, we can compute the standard deviation
of quicksort's running time. The result is that, if a single random permuta-
tion is presented, the running time used to sort it will almost certainly be
close to the average. Thus we must see to it that degenerate inputs do not
result in bad running times. Degenerate inputs include data that have
already been sorted and data that contain only
N
completely identical ele-
ments. Sometimes it is the easy cases that give algorithms trouble.
Search WWH ::
Custom Search