?? s_qui.htm
字號:
<html>
<head>
<title>Quicksort</title>
</head>
<body bgcolor="#ffffff">
<p align=right>
<a href="s_man.htm" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_man.htm" target="_top"><img src="c_man.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/c_man.gif" width=74 height=19 border=0></a>
</p>
<h1>Quicksort</h1>
Although the shell sort algorithm is significantly better than
insertion sort, there is still room for improvement. One of the
most popular sorting algorithms is quicksort. Quicksort executes
in <b><i>O</i></b>(<i>n</i> lg <i>n</i>) on average, and
<b><i>O</i></b>(<i>n</i><sup>2</sup>) in the worst-case. However,
with proper precautions, worst-case behavior is very unlikely.
Quicksort is a non-stable sort. It is not an in-place sort as
stack space is required. For further reading, consult
<a href="javascript:if(confirm('http://www.amazon.com/exec/obidos/ISBN=0262031418/none01A/ \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://www.amazon.com/exec/obidos/ISBN=0262031418/none01A/'" tppabs="http://www.amazon.com/exec/obidos/ISBN=0262031418/none01A/" target="_top">Cormen [1990]</a>.
<h2>Theory</h2>
The quicksort algorithm works by partitioning the array to be
sorted, then recursively sorting each partition. In <i>Partition</i>
(Figure 2-3),
one of the array elements is selected as a pivot
value. Values smaller than the pivot value are placed to the
left of the pivot, while larger values are placed to the right.
<p>
<center>
<p><a name="Fig2-3"></a>
<table border cellspacing=0 cellpadding=3>
<caption align=bottom> <h3>Figure 2-3: Quicksort Algorithm</h3> </caption>
<tr><td>
<pre>
<b>int function</b> <i>Partition</i> (<b>Array</b> <i>A</i>, <b>int</b> <i>Lb</i>, <b>int</b> <i>Ub</i>);
<b>begin</b>
<b>select</b> a <i>pivot</i> from <i>A</i>[<i>Lb</i>]...<i>A</i>[<i>Ub</i>];
<b>reorder</b> <i>A</i>[<i>Lb</i>]...<i>A</i>[<i>Ub</i>] such that:
all values to the left of the <i>pivot</i> are <= pivot
all values to the right of the <i>pivot</i> are >= pivot
<b>return</b> <i>pivot</i> position;
<b>end;</b>
<b>procedure</b> <i>QuickSort</i> (<b>Array</b> <i>A</i>, <b>int</b> <i>Lb</i>, <b>int</b> <i>Ub</i>);
<b>begin</b>
<b>if</b> <i>Lb</i> < <i>Ub</i> <b>then</b>
<i>M</i> = <i>Partition</i> (<i>A</i>, <i>Lb</i>, <i>Ub</i>);
<i>QuickSort</i> (<i>A</i>, <i>Lb</i>, <i>M</i> - 1);
<i>QuickSort</i> (<i>A</i>, <i>M</i> + 1, <i>Ub</i>);
<b>end;</b>
</pre>
</table>
</center>
<p>
In Figure 2-4(a),
the pivot selected is 3. Indices are run
starting at both ends of the array.
One index starts on the left
and selects an element that is larger than the pivot,
while another index starts on the right and selects an element
that is smaller than the pivot.
In this case, numbers 4 and 1 are selected.
These elements are then exchanged, as is shown in
Figure 2-4(b).
This process repeats until all elements to the left of the pivot <= the pivot,
and all elements to the right of the pivot are >= the pivot.
<i>QuickSort</i> recursively sorts the two subarrays,
resulting in the array shown in Figure 2-4(c).
<center>
<h3><a name="Fig2-4">
<img src="s_fig24.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_fig24.gif" vspace=5 width=319 height=242><br>
Figure 2-4: Quicksort Example</a>
</h3>
</center>
As the process proceeds, it may be necessary to move the pivot so
that correct ordering is maintained. In this manner, <i>QuickSort</i>
succeeds in sorting the array. If we're lucky the pivot selected
will be the median of all values, equally dividing the
array. For a moment, let's assume that this is the case. Since
the array is split in half at each step, and <i>Partition</i> must
eventually examine all <i>n</i> elements, the run time is
<b><i>O</i></b>(n lg <i>n</i>).
<p>
To find a pivot value, <i>Partition</i> could simply select the first
element (<i>A</i>[<i>Lb</i>]). All other values would be compared to the pivot
value, and placed either to the left or right of the pivot as
appropriate. However, there is one case that fails miserably.
Suppose the array was originally in order. <i>Partition</i> would
always select the lowest value as a pivot and split the array
with one element in the left partition, and <i>Ub</i> - <i>Lb</i> elements in
the other. Each recursive call to quicksort would only diminish
the size of the array to be sorted by one. Therefore <i>n</i> recursive
calls would be required to do the sort, resulting in a
<b><i>O</i></b>(<i>n</i><sup>2</sup>) run
time. One solution to this problem is to randomly select an item
as a pivot. This would make it <i>extremely</i> unlikely that
worst-case behavior would occur.
<h2>Implementation</h2>
An
<a href="javascript:if(confirm('http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_qui.txt \n\nThis file was not retrieved by Teleport Pro, because it is linked too far away from its Starting Address. If you increase the in-domain depth setting for the Starting Address, this file will be queued for retrieval. \n\nDo you want to open it from the server?'))window.location='http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_qui.txt'" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_qui.txt">ANSI-C implementation</a>
for quicksort is included.
<b>Typedef T</b> and comparison operator
<b>compGT</b> should be altered to reflect the data stored in the array.
Several enhancements have been made to the basic quicksort
algorithm:
<ul>
<li> The center element is selected as a pivot in <b>partition</b>. If
the list is partially ordered, this will be a good choice. Worst-case
behavior occurs when the center element happens to be the
largest or smallest element each time <b>partition</b> is invoked.
<li> For short arrays, <b>insertSort</b> is called. Due to recursion and
other overhead, quicksort is not an efficient algorithm to use on
small arrays. Consequently, any array with fewer than 12 elements is
sorted using an insertion sort. The optimal cutoff value is not
critical and varies based on the quality of generated code.
<li> Tail recursion occurs when the last statement in a function is
a call to the function itself. Tail recursion may be replaced by
iteration, resulting in a better utilization of stack space.
This has been done with the second call to <i>QuickSort</i> in Figure 2-3.
<li>After an array is partitioned, the smallest partition is
sorted first. This results in a better utilization of stack
space, as short partitions are quickly sorted and dispensed with.
</ul>
Also included is an
<a href="javascript:if(confirm('http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_qsort.txt \n\nThis file was not retrieved by Teleport Pro, because it is linked too far away from its Starting Address. If you increase the in-domain depth setting for the Starting Address, this file will be queued for retrieval. \n\nDo you want to open it from the server?'))window.location='http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_qsort.txt'" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_qsort.txt">ANSI-C implementation</a>,
of <i>qsort</i>, a standard C library function usually implemented with
quicksort. Recursive calls were
replaced by explicit stack operations.
Table 2-1, shows timing statistics and stack utilization before and after the
enhancements were applied.
<center>
<p><a name="Tbl2-1"></a>
<table border cellspacing=0 cellpadding=3>
<caption align=bottom><h3>Table 2-1: Effect of Enhancements on Speed and Stack Utilization</h3></caption>
<tr><th rowspan=2>count</th><th colspan=2>time (µs)</th><th colspan=2>stacksize</th></tr>
<tr><th>before</th><th>after</th><th>before</th><th>after</th></tr>
<tr align=right><td>16</td><td>103</td><td>51</td><td>540</td><td>28</td></tr>
<tr align=right><td>256</td><td>1,630</td><td>911</td><td>912</td><td>112</td></tr>
<tr align=right><td>4,096</td><td>34,183</td><td>20,016</td><td>1,908</td><td>168</td></tr>
<tr align=right><td>65,536</td><td>658,003</td><td>460,737</td><td>2,436</td><td>252</td></tr>
</table>
</center>
</body>
</html>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -