source: proiecte/HadoopJUnit/hadoop-0.20.1/docs/api/org/apache/hadoop/util/QuickSort.html @ 120

Last change on this file since 120 was 120, checked in by (none), 14 years ago

Added the mail files for the Hadoop JUNit Project
  • Property svn:executable set to *
File size: 16.4 KB
Line 
1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
2<!--NewPage-->
3<HTML>
4<HEAD>
5<!-- Generated by javadoc (build 1.6.0_07) on Tue Sep 01 20:56:55 UTC 2009 -->
6<TITLE>
7QuickSort (Hadoop 0.20.1 API)
8</TITLE>
9
10<META NAME="date" CONTENT="2009-09-01">
11
12<LINK REL ="stylesheet" TYPE="text/css" HREF="../../../../stylesheet.css" TITLE="Style">
13
14<SCRIPT type="text/javascript">
15function windowTitle()
16{
17    if (location.href.indexOf('is-external=true') == -1) {
18        parent.document.title="QuickSort (Hadoop 0.20.1 API)";
19    }
20}
21</SCRIPT>
22<NOSCRIPT>
23</NOSCRIPT>
24
25</HEAD>
26
27<BODY BGCOLOR="white" onload="windowTitle();">
28<HR>
29
30
31<!-- ========= START OF TOP NAVBAR ======= -->
32<A NAME="navbar_top"><!-- --></A>
33<A HREF="#skip-navbar_top" title="Skip navigation links"></A>
34<TABLE BORDER="0" WIDTH="100%" CELLPADDING="1" CELLSPACING="0" SUMMARY="">
35<TR>
36<TD COLSPAN=2 BGCOLOR="#EEEEFF" CLASS="NavBarCell1">
37<A NAME="navbar_top_firstrow"><!-- --></A>
38<TABLE BORDER="0" CELLPADDING="0" CELLSPACING="3" SUMMARY="">
39  <TR ALIGN="center" VALIGN="top">
40  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../../../../overview-summary.html"><FONT CLASS="NavBarFont1"><B>Overview</B></FONT></A>&nbsp;</TD>
41  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="package-summary.html"><FONT CLASS="NavBarFont1"><B>Package</B></FONT></A>&nbsp;</TD>
42  <TD BGCOLOR="#FFFFFF" CLASS="NavBarCell1Rev"> &nbsp;<FONT CLASS="NavBarFont1Rev"><B>Class</B></FONT>&nbsp;</TD>
43  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="class-use/QuickSort.html"><FONT CLASS="NavBarFont1"><B>Use</B></FONT></A>&nbsp;</TD>
44  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="package-tree.html"><FONT CLASS="NavBarFont1"><B>Tree</B></FONT></A>&nbsp;</TD>
45  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../../../../deprecated-list.html"><FONT CLASS="NavBarFont1"><B>Deprecated</B></FONT></A>&nbsp;</TD>
46  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../../../../index-all.html"><FONT CLASS="NavBarFont1"><B>Index</B></FONT></A>&nbsp;</TD>
47  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../../../../help-doc.html"><FONT CLASS="NavBarFont1"><B>Help</B></FONT></A>&nbsp;</TD>
48  </TR>
49</TABLE>
50</TD>
51<TD ALIGN="right" VALIGN="top" ROWSPAN=3><EM>
52</EM>
53</TD>
54</TR>
55
56<TR>
57<TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2">
58&nbsp;<A HREF="../../../../org/apache/hadoop/util/Progressable.html" title="interface in org.apache.hadoop.util"><B>PREV CLASS</B></A>&nbsp;
59&nbsp;<A HREF="../../../../org/apache/hadoop/util/ReflectionUtils.html" title="class in org.apache.hadoop.util"><B>NEXT CLASS</B></A></FONT></TD>
60<TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2">
61  <A HREF="../../../../index.html?org/apache/hadoop/util/QuickSort.html" target="_top"><B>FRAMES</B></A>  &nbsp;
62&nbsp;<A HREF="QuickSort.html" target="_top"><B>NO FRAMES</B></A>  &nbsp;
63&nbsp;<SCRIPT type="text/javascript">
64  <!--
65  if(window==top) {
66    document.writeln('<A HREF="../../../../allclasses-noframe.html"><B>All Classes</B></A>');
67  }
68  //-->
69</SCRIPT>
70<NOSCRIPT>
71  <A HREF="../../../../allclasses-noframe.html"><B>All Classes</B></A>
72</NOSCRIPT>
73
74
75</FONT></TD>
76</TR>
77<TR>
78<TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2">
79  SUMMARY:&nbsp;NESTED&nbsp;|&nbsp;FIELD&nbsp;|&nbsp;<A HREF="#constructor_summary">CONSTR</A>&nbsp;|&nbsp;<A HREF="#method_summary">METHOD</A></FONT></TD>
80<TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2">
81DETAIL:&nbsp;FIELD&nbsp;|&nbsp;<A HREF="#constructor_detail">CONSTR</A>&nbsp;|&nbsp;<A HREF="#method_detail">METHOD</A></FONT></TD>
82</TR>
83</TABLE>
84<A NAME="skip-navbar_top"></A>
85<!-- ========= END OF TOP NAVBAR ========= -->
86
87<HR>
88<!-- ======== START OF CLASS DATA ======== -->
89<H2>
90<FONT SIZE="-1">
91org.apache.hadoop.util</FONT>
92<BR>
93Class QuickSort</H2>
94<PRE>
95<A HREF="http://java.sun.com/javase/6/docs/api/java/lang/Object.html?is-external=true" title="class or interface in java.lang">java.lang.Object</A>
96  <IMG SRC="../../../../resources/inherit.gif" ALT="extended by "><B>org.apache.hadoop.util.QuickSort</B>
97</PRE>
98<DL>
99<DT><B>All Implemented Interfaces:</B> <DD><A HREF="../../../../org/apache/hadoop/util/IndexedSorter.html" title="interface in org.apache.hadoop.util">IndexedSorter</A></DD>
100</DL>
101<HR>
102<DL>
103<DT><PRE>public final class <B>QuickSort</B><DT>extends <A HREF="http://java.sun.com/javase/6/docs/api/java/lang/Object.html?is-external=true" title="class or interface in java.lang">Object</A><DT>implements <A HREF="../../../../org/apache/hadoop/util/IndexedSorter.html" title="interface in org.apache.hadoop.util">IndexedSorter</A></DL>
104</PRE>
105
106<P>
107An implementation of the core algorithm of QuickSort.
108<P>
109
110<P>
111<HR>
112
113<P>
114
115<!-- ======== CONSTRUCTOR SUMMARY ======== -->
116
117<A NAME="constructor_summary"><!-- --></A>
118<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
119<TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor">
120<TH ALIGN="left" COLSPAN="2"><FONT SIZE="+2">
121<B>Constructor Summary</B></FONT></TH>
122</TR>
123<TR BGCOLOR="white" CLASS="TableRowColor">
124<TD><CODE><B><A HREF="../../../../org/apache/hadoop/util/QuickSort.html#QuickSort()">QuickSort</A></B>()</CODE>
125
126<BR>
127&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</TD>
128</TR>
129</TABLE>
130&nbsp;
131<!-- ========== METHOD SUMMARY =========== -->
132
133<A NAME="method_summary"><!-- --></A>
134<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
135<TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor">
136<TH ALIGN="left" COLSPAN="2"><FONT SIZE="+2">
137<B>Method Summary</B></FONT></TH>
138</TR>
139<TR BGCOLOR="white" CLASS="TableRowColor">
140<TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1">
141<CODE>protected static&nbsp;int</CODE></FONT></TD>
142<TD><CODE><B><A HREF="../../../../org/apache/hadoop/util/QuickSort.html#getMaxDepth(int)">getMaxDepth</A></B>(int&nbsp;x)</CODE>
143
144<BR>
145&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Deepest recursion before giving up and doing a heapsort.</TD>
146</TR>
147<TR BGCOLOR="white" CLASS="TableRowColor">
148<TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1">
149<CODE>&nbsp;void</CODE></FONT></TD>
150<TD><CODE><B><A HREF="../../../../org/apache/hadoop/util/QuickSort.html#sort(org.apache.hadoop.util.IndexedSortable, int, int)">sort</A></B>(<A HREF="../../../../org/apache/hadoop/util/IndexedSortable.html" title="interface in org.apache.hadoop.util">IndexedSortable</A>&nbsp;s,
151     int&nbsp;p,
152     int&nbsp;r)</CODE>
153
154<BR>
155&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Sort the given range of items using quick sort.</TD>
156</TR>
157<TR BGCOLOR="white" CLASS="TableRowColor">
158<TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1">
159<CODE>&nbsp;void</CODE></FONT></TD>
160<TD><CODE><B><A HREF="../../../../org/apache/hadoop/util/QuickSort.html#sort(org.apache.hadoop.util.IndexedSortable, int, int, org.apache.hadoop.util.Progressable)">sort</A></B>(<A HREF="../../../../org/apache/hadoop/util/IndexedSortable.html" title="interface in org.apache.hadoop.util">IndexedSortable</A>&nbsp;s,
161     int&nbsp;p,
162     int&nbsp;r,
163     <A HREF="../../../../org/apache/hadoop/util/Progressable.html" title="interface in org.apache.hadoop.util">Progressable</A>&nbsp;rep)</CODE>
164
165<BR>
166&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Same as <A HREF="../../../../org/apache/hadoop/util/IndexedSorter.html#sort(org.apache.hadoop.util.IndexedSortable, int, int)"><CODE>IndexedSorter.sort(IndexedSortable,int,int)</CODE></A>, but indicate progress
167 periodically.</TD>
168</TR>
169</TABLE>
170&nbsp;<A NAME="methods_inherited_from_class_java.lang.Object"><!-- --></A>
171<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
172<TR BGCOLOR="#EEEEFF" CLASS="TableSubHeadingColor">
173<TH ALIGN="left"><B>Methods inherited from class java.lang.<A HREF="http://java.sun.com/javase/6/docs/api/java/lang/Object.html?is-external=true" title="class or interface in java.lang">Object</A></B></TH>
174</TR>
175<TR BGCOLOR="white" CLASS="TableRowColor">
176<TD><CODE><A HREF="http://java.sun.com/javase/6/docs/api/java/lang/Object.html?is-external=true#clone()" title="class or interface in java.lang">clone</A>, <A HREF="http://java.sun.com/javase/6/docs/api/java/lang/Object.html?is-external=true#equals(java.lang.Object)" title="class or interface in java.lang">equals</A>, <A HREF="http://java.sun.com/javase/6/docs/api/java/lang/Object.html?is-external=true#finalize()" title="class or interface in java.lang">finalize</A>, <A HREF="http://java.sun.com/javase/6/docs/api/java/lang/Object.html?is-external=true#getClass()" title="class or interface in java.lang">getClass</A>, <A HREF="http://java.sun.com/javase/6/docs/api/java/lang/Object.html?is-external=true#hashCode()" title="class or interface in java.lang">hashCode</A>, <A HREF="http://java.sun.com/javase/6/docs/api/java/lang/Object.html?is-external=true#notify()" title="class or interface in java.lang">notify</A>, <A HREF="http://java.sun.com/javase/6/docs/api/java/lang/Object.html?is-external=true#notifyAll()" title="class or interface in java.lang">notifyAll</A>, <A HREF="http://java.sun.com/javase/6/docs/api/java/lang/Object.html?is-external=true#toString()" title="class or interface in java.lang">toString</A>, <A HREF="http://java.sun.com/javase/6/docs/api/java/lang/Object.html?is-external=true#wait()" title="class or interface in java.lang">wait</A>, <A HREF="http://java.sun.com/javase/6/docs/api/java/lang/Object.html?is-external=true#wait(long)" title="class or interface in java.lang">wait</A>, <A HREF="http://java.sun.com/javase/6/docs/api/java/lang/Object.html?is-external=true#wait(long, int)" title="class or interface in java.lang">wait</A></CODE></TD>
177</TR>
178</TABLE>
179&nbsp;
180<P>
181
182<!-- ========= CONSTRUCTOR DETAIL ======== -->
183
184<A NAME="constructor_detail"><!-- --></A>
185<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
186<TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor">
187<TH ALIGN="left" COLSPAN="1"><FONT SIZE="+2">
188<B>Constructor Detail</B></FONT></TH>
189</TR>
190</TABLE>
191
192<A NAME="QuickSort()"><!-- --></A><H3>
193QuickSort</H3>
194<PRE>
195public <B>QuickSort</B>()</PRE>
196<DL>
197</DL>
198
199<!-- ============ METHOD DETAIL ========== -->
200
201<A NAME="method_detail"><!-- --></A>
202<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
203<TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor">
204<TH ALIGN="left" COLSPAN="1"><FONT SIZE="+2">
205<B>Method Detail</B></FONT></TH>
206</TR>
207</TABLE>
208
209<A NAME="getMaxDepth(int)"><!-- --></A><H3>
210getMaxDepth</H3>
211<PRE>
212protected static int <B>getMaxDepth</B>(int&nbsp;x)</PRE>
213<DL>
214<DD>Deepest recursion before giving up and doing a heapsort.
215 Returns 2 * ceil(log(n)).
216<P>
217<DD><DL>
218</DL>
219</DD>
220<DD><DL>
221</DL>
222</DD>
223</DL>
224<HR>
225
226<A NAME="sort(org.apache.hadoop.util.IndexedSortable, int, int)"><!-- --></A><H3>
227sort</H3>
228<PRE>
229public void <B>sort</B>(<A HREF="../../../../org/apache/hadoop/util/IndexedSortable.html" title="interface in org.apache.hadoop.util">IndexedSortable</A>&nbsp;s,
230                 int&nbsp;p,
231                 int&nbsp;r)</PRE>
232<DL>
233<DD>Sort the given range of items using quick sort.
234 Sort the items accessed through the given IndexedSortable over the given
235 range of logical indices. From the perspective of the sort algorithm,
236 each index between l (inclusive) and r (exclusive) is an addressable
237 entry. If the recursion depth falls below <A HREF="../../../../org/apache/hadoop/util/QuickSort.html#getMaxDepth(int)"><CODE>getMaxDepth(int)</CODE></A>,
238 then switch to <A HREF="../../../../org/apache/hadoop/util/HeapSort.html" title="class in org.apache.hadoop.util"><CODE>HeapSort</CODE></A>.
239<P>
240<DD><DL>
241<DT><B>Specified by:</B><DD><CODE><A HREF="../../../../org/apache/hadoop/util/IndexedSorter.html#sort(org.apache.hadoop.util.IndexedSortable, int, int)">sort</A></CODE> in interface <CODE><A HREF="../../../../org/apache/hadoop/util/IndexedSorter.html" title="interface in org.apache.hadoop.util">IndexedSorter</A></CODE></DL>
242</DD>
243<DD><DL>
244<DT><B>See Also:</B><DD><A HREF="../../../../org/apache/hadoop/util/IndexedSortable.html#compare(int, int)"><CODE>IndexedSortable.compare(int, int)</CODE></A>,
245<A HREF="../../../../org/apache/hadoop/util/IndexedSortable.html#swap(int, int)"><CODE>IndexedSortable.swap(int, int)</CODE></A></DL>
246</DD>
247</DL>
248<HR>
249
250<A NAME="sort(org.apache.hadoop.util.IndexedSortable, int, int, org.apache.hadoop.util.Progressable)"><!-- --></A><H3>
251sort</H3>
252<PRE>
253public void <B>sort</B>(<A HREF="../../../../org/apache/hadoop/util/IndexedSortable.html" title="interface in org.apache.hadoop.util">IndexedSortable</A>&nbsp;s,
254                 int&nbsp;p,
255                 int&nbsp;r,
256                 <A HREF="../../../../org/apache/hadoop/util/Progressable.html" title="interface in org.apache.hadoop.util">Progressable</A>&nbsp;rep)</PRE>
257<DL>
258<DD>Same as <A HREF="../../../../org/apache/hadoop/util/IndexedSorter.html#sort(org.apache.hadoop.util.IndexedSortable, int, int)"><CODE>IndexedSorter.sort(IndexedSortable,int,int)</CODE></A>, but indicate progress
259 periodically.
260<P>
261<DD><DL>
262<DT><B>Specified by:</B><DD><CODE><A HREF="../../../../org/apache/hadoop/util/IndexedSorter.html#sort(org.apache.hadoop.util.IndexedSortable, int, int, org.apache.hadoop.util.Progressable)">sort</A></CODE> in interface <CODE><A HREF="../../../../org/apache/hadoop/util/IndexedSorter.html" title="interface in org.apache.hadoop.util">IndexedSorter</A></CODE></DL>
263</DD>
264<DD><DL>
265<DT><B>See Also:</B><DD><A HREF="../../../../org/apache/hadoop/util/IndexedSorter.html#sort(org.apache.hadoop.util.IndexedSortable, int, int)"><CODE>IndexedSorter.sort(IndexedSortable,int,int)</CODE></A></DL>
266</DD>
267</DL>
268<!-- ========= END OF CLASS DATA ========= -->
269<HR>
270
271
272<!-- ======= START OF BOTTOM NAVBAR ====== -->
273<A NAME="navbar_bottom"><!-- --></A>
274<A HREF="#skip-navbar_bottom" title="Skip navigation links"></A>
275<TABLE BORDER="0" WIDTH="100%" CELLPADDING="1" CELLSPACING="0" SUMMARY="">
276<TR>
277<TD COLSPAN=2 BGCOLOR="#EEEEFF" CLASS="NavBarCell1">
278<A NAME="navbar_bottom_firstrow"><!-- --></A>
279<TABLE BORDER="0" CELLPADDING="0" CELLSPACING="3" SUMMARY="">
280  <TR ALIGN="center" VALIGN="top">
281  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../../../../overview-summary.html"><FONT CLASS="NavBarFont1"><B>Overview</B></FONT></A>&nbsp;</TD>
282  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="package-summary.html"><FONT CLASS="NavBarFont1"><B>Package</B></FONT></A>&nbsp;</TD>
283  <TD BGCOLOR="#FFFFFF" CLASS="NavBarCell1Rev"> &nbsp;<FONT CLASS="NavBarFont1Rev"><B>Class</B></FONT>&nbsp;</TD>
284  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="class-use/QuickSort.html"><FONT CLASS="NavBarFont1"><B>Use</B></FONT></A>&nbsp;</TD>
285  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="package-tree.html"><FONT CLASS="NavBarFont1"><B>Tree</B></FONT></A>&nbsp;</TD>
286  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../../../../deprecated-list.html"><FONT CLASS="NavBarFont1"><B>Deprecated</B></FONT></A>&nbsp;</TD>
287  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../../../../index-all.html"><FONT CLASS="NavBarFont1"><B>Index</B></FONT></A>&nbsp;</TD>
288  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../../../../help-doc.html"><FONT CLASS="NavBarFont1"><B>Help</B></FONT></A>&nbsp;</TD>
289  </TR>
290</TABLE>
291</TD>
292<TD ALIGN="right" VALIGN="top" ROWSPAN=3><EM>
293</EM>
294</TD>
295</TR>
296
297<TR>
298<TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2">
299&nbsp;<A HREF="../../../../org/apache/hadoop/util/Progressable.html" title="interface in org.apache.hadoop.util"><B>PREV CLASS</B></A>&nbsp;
300&nbsp;<A HREF="../../../../org/apache/hadoop/util/ReflectionUtils.html" title="class in org.apache.hadoop.util"><B>NEXT CLASS</B></A></FONT></TD>
301<TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2">
302  <A HREF="../../../../index.html?org/apache/hadoop/util/QuickSort.html" target="_top"><B>FRAMES</B></A>  &nbsp;
303&nbsp;<A HREF="QuickSort.html" target="_top"><B>NO FRAMES</B></A>  &nbsp;
304&nbsp;<SCRIPT type="text/javascript">
305  <!--
306  if(window==top) {
307    document.writeln('<A HREF="../../../../allclasses-noframe.html"><B>All Classes</B></A>');
308  }
309  //-->
310</SCRIPT>
311<NOSCRIPT>
312  <A HREF="../../../../allclasses-noframe.html"><B>All Classes</B></A>
313</NOSCRIPT>
314
315
316</FONT></TD>
317</TR>
318<TR>
319<TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2">
320  SUMMARY:&nbsp;NESTED&nbsp;|&nbsp;FIELD&nbsp;|&nbsp;<A HREF="#constructor_summary">CONSTR</A>&nbsp;|&nbsp;<A HREF="#method_summary">METHOD</A></FONT></TD>
321<TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2">
322DETAIL:&nbsp;FIELD&nbsp;|&nbsp;<A HREF="#constructor_detail">CONSTR</A>&nbsp;|&nbsp;<A HREF="#method_detail">METHOD</A></FONT></TD>
323</TR>
324</TABLE>
325<A NAME="skip-navbar_bottom"></A>
326<!-- ======== END OF BOTTOM NAVBAR ======= -->
327
328<HR>
329Copyright &copy; 2009 The Apache Software Foundation
330</BODY>
331</HTML>
Note: See TracBrowser for help on using the repository browser.