📄 page494.html
字号:
<HTML>
<HEAD>
<TITLE>Quicksort</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html8025" HREF="page495.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page495.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html8023" HREF="page492.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page492.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html8017" HREF="page493.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page493.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html8027" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html8028" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H2><A NAME="SECTION0016420000000000000000">Quicksort</A></H2>
<P>
The second exchange sort we consider
is the <em>quicksort</em><A NAME=36580> </A> algorithm.
Quicksort is a <em>divide-and-conquer</em> style algorithm.
A divide-and-conquer algorithm solves a given problem
by splitting it into two or more smaller subproblems,
recursively solving each of the subproblems,
and then combining the solutions to the smaller problems
to obtain a solution to the original one.
<P>
To sort the sequence <IMG WIDTH=157 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline69689" SRC="img2088.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2088.gif" >,
quicksort performs the following steps:
<OL><LI>
Select one of the elements of <I>S</I>.
The selected element, <I>p</I>, is called the <em>pivot</em><A NAME=36584> </A>.<LI>
Remove <I>p</I> from <I>S</I> and then
partition the remaining elements of <I>S</I> into two
distinct sequences, <I>L</I> and <I>G</I>, such that
every element in <I>L</I> is less than or equal to the pivot and
every element in <I>G</I> is greater than or equal to the pivot.
In general, both <I>L</I> and <I>G</I> are <em>unsorted</em>.<LI>
Rearrange the elements of the sequence as follows:
<P> <IMG WIDTH=391 HEIGHT=43 ALIGN=BOTTOM ALT="displaymath70071" SRC="img2141.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2141.gif" ><P>
Notice that the pivot is now in the position
in which it belongs in the sorted sequence,
since all the elements to the left of the pivot are less than
or equal to the pivot
and all the elements to the right are greater than or equal to it.<LI>
Recursively quicksort the unsorted sequences <I>L</I> and <I>G</I>.
</OL>
<P>
The first step of the algorithm is a crucial one.
We have not specified how to select the pivot.
Fortunately, the sorting algorithm works no matter which
element is chosen to be the pivot.
However, the pivot selection affects directly
the running time of the algorithm.
If we choose poorly the running time will be poor.
<P>
Figure <A HREF="page494.html#figsort3" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page494.html#figsort3"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> illustrates the detailed operation of quicksort
as it sorts the sequence <IMG WIDTH=156 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70101" SRC="img2142.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2142.gif" >.
To begin the sort, we select a pivot.
In this example, the value 4 in the last array position is chosen.
Next, the remaining elements are partitioned into two sequences,
one which contains values less than or equal to 4 ( <IMG WIDTH=100 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70107" SRC="img2143.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2143.gif" >)
and one which contains values greater than or equal to 4
( <IMG WIDTH=116 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70111" SRC="img2144.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2144.gif" >).
Notice that the partitioning is accomplished by exchanging elements.
This is why quicksort is considered to be an exchange sort.
<P>
<P><A NAME="37749"> </A><A NAME="figsort3"> </A> <IMG WIDTH=575 HEIGHT=587 ALIGN=BOTTOM ALT="figure36594" SRC="img2145.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2145.gif" ><BR>
<STRONG>Figure:</STRONG> ``Quick'' Sorting<BR>
<P>
<P>
After the partitioning, the pivot is inserted between the two sequences.
This is called <em>restoring</em> the pivot.
To restore the pivot, we simply exchange it with the first element of <I>G</I>.
Notice that the 4 is in its correct position in the sorted sequence
and it is not considered any further.
<P>
Now the quicksort algorithm calls itself recursively,
first to sort the sequence <IMG WIDTH=100 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70107" SRC="img2143.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2143.gif" >;
second to sort the sequence <IMG WIDTH=116 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70131" SRC="img2146.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2146.gif" >.
The quicksort of <I>L</I> selects 1 as the pivot,
and creates the two subsequences <IMG WIDTH=58 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline70137" SRC="img2147.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2147.gif" > and <IMG WIDTH=75 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline70139" SRC="img2148.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2148.gif" >.
Similarly, the quicksort of <I>G</I> uses 5 as the pivot
and creates the two subsequences <IMG WIDTH=77 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline70145" SRC="img2149.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2149.gif" > and <IMG WIDTH=78 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline70147" SRC="img2150.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2150.gif" >.
<P>
At this point in the example the recursion has been stopped.
It turns out that to keep the code simple,
quicksort algorithms usually stop the recursion when the length
of a subsequence falls below a critical value called the <em>cut-off</em>.
In this example, the cut-off is two
(i.e., a subsequence of two or fewer elements is not sorted).
This means that when the algorithm terminates,
the sequence is not yet sorted.
However as Figure <A HREF="page494.html#figsort3" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page494.html#figsort3"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> shows,
the sequence is <em>almost</em> sorted.
In fact, every element is guaranteed to be less than two positions
away from its final resting place.
<P>
We can complete the sorting of the sequence by using a straight insertion sort.
In Section <A HREF="page488.html#secsortinginsertion" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page488.html#secsortinginsertion"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> it is shown that
straight insertion is quite good at sorting sequences that are almost sorted.
In fact, if we know that every element of the sequence is at most <I>d</I>
positions from its final resting place,
the running time of straight insertion is <I>O</I>(<I>dn</I>) and
since <I>d</I>=2 is a constant, the running time is <I>O</I>(<I>n</I>).
<P>
<BR> <HR>
<UL>
<LI> <A NAME="tex2html8029" HREF="page495.html#SECTION0016421000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page495.html#SECTION0016421000000000000000">Implementation</A>
</UL>
<HR><A NAME="tex2html8025" HREF="page495.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page495.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html8023" HREF="page492.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page492.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html8017" HREF="page493.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page493.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html8027" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html8028" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \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://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \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://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -