📄 node99.html
字号:
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 3.2 Final//FR"><!-- Converted with LaTeX2HTML 95.1 (Fri Jan 20 1995) --><!-- by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds --><!-- Modified Simulog 03/97 --><HTML><HEAD><TITLE>7.7 Sorting and dichotomy</TITLE><LINK REL=STYLESHEET TYPE="text/css" HREF="./Modulef.css" TITLE="Modulef CSS"><meta name="description" value="7.7 Sorting and dichotomy"><meta name="keywords" value="Guide6"><meta name="resource-type" value="document"><meta name="distribution" value="global"></HEAD><BODY BGCOLOR="#FFFFFF"><P> <IMG SRC="../icons/smallmod.gif" WIDTH=211 HEIGHT=50 ALIGN=BOTTOM ALT="Modulef"><A NAME=tex2html1632 HREF="node98.html"><IMG BORDER=0 ALIGN=BOTTOM SRC="../icons/previous_motif.gif" ALT="previous"></A><A NAME=tex2html1638 HREF="node92.html"><IMG BORDER=0 ALIGN=BOTTOM SRC="../icons/up_motif.gif" ALT="up"></A><A NAME=tex2html1640 HREF="node100.html"><IMG BORDER=0 ALIGN=BOTTOM SRC="../icons/next_motif.gif" ALT="next"></A><A NAME=tex2html1642 HREF="node2.html"><IMG BORDER=0 ALIGN=BOTTOM SRC="../icons/contents_motif.gif" ALT="contents"></A><A HREF="../Guide6-18/node99.html"><IMG BORDER=0 SRC="../icons/zoom18.gif" ALIGN=BOTTOM ALT="[BIG]"></A><A HREF="../Guide6-14/node99.html"><IMG BORDER=0 SRC="../icons/zoom14.gif" ALIGN=BOTTOM ALT="[Normal]"></A><A HREF="../Guide6-10/node99.html"><IMG BORDER=0 SRC="../icons/zoom10.gif" ALIGN=BOTTOM ALT="[small]"></A><BR><B> Next: </B> <A NAME=tex2html1641 HREF="node100.html">7.8 Implementation aids</A><B>Up: </B> <A NAME=tex2html1639 HREF="node92.html">7 Internal programs</A><B> Prev: </B> <A NAME=tex2html1633 HREF="node98.html">7.6 Matrix and vector manipulations</A><B><A HREF="node2.html" >Contents</A></B><HR SIZE=3 WIDTH="75%"><H1><A NAME=SECTION05770000000000000000>7.7 Sorting and dichotomy</A></H1><P><P><P>Numerous sorting subroutines<A NAME=3436> </A> are proposed here. They differ in the type and number of input parameters.They all have "HEAP" in their namesexcept BUBBLE. The *HEAP* subroutines correspond to sorts of O(log n), whereas BUBBLE is of O(n**2).<P><UL><LI><P><PRE> SUBROUTINE BUBBLE(TAB,N) INTEGER N,TAB(N)</PRE><P>sorts TAB in<A NAME=3438> </A> order of increasing values (BUBBLE-SORT).<P><LI><P><PRE> SUBROUTINE HEAP(CRITER, RECORD, N) INTEGER N, RECORD(N) REAL CRITER(N)</PRE><P>sorts <A NAME=3439> </A> the values of CRITER in increasing order. RECORD follows the reordering.<P><LI><P><PRE> SUBROUTINE HEAP2I(CRITER, N) INTEGER N INTEGER CRITER(2, N)</PRE><P>Sorts <A NAME=3440> </A> the values of CRITER(1, *) in increasing order. CRITER(2, *) follows the reordering.<P><LI><P><PRE> SUBROUTINE HEAP3I(CRITER, N) INTEGER N INTEGER CRITER(3, N)</PRE><P>sorts the values<A NAME=3441> </A> of CRITER(1, *) in increasing order. CRITER(2, *) and CRITER(3, *) follows the reordering.<P><LI><P><PRE> SUBROUTINE HPD2I(CRITER, RECORD, N) INTEGER N, RECORD(2, N) DOUBLE PRECISION CRITER(N)</PRE><P>sorts the values <A NAME=3442> </A> of CRITER in increasing order. RECORD follows the reordering.<P><LI><P><PRE> SUBROUTINE HEAPDI(CRITER, RECORD, N) INTEGER N, RECORD(N) DOUBLE PRECISION CRITER(N)</PRE><P> sorts the values <A NAME=3443> </A> of CRITER in increasing order. RECORD follows the reordering.<P><LI><P><PRE> SUBROUTINE HEAPI(CRITER, N) INTEGER N INTEGER CRITER(N)</PRE><P>sorts the values of<A NAME=3444> </A> CRITER in increasing order.<P><LI><P><PRE> SUBROUTINE HEAPI2(CRITER, RECORD, N) INTEGER N, RECORD(N) INTEGER CRITER(N)</PRE><P>sorts the values of <A NAME=3445> </A> CRITER in increasing order.RECORD follows the reordering.<P><LI><P><PRE> SUBROUTINE HEPI2I(CRITER, RECORD, N) INTEGER N, RECORD(2, N) INTEGER CRITER(N)</PRE><P>sorts the<A NAME=3446> </A> values of CRITER in increasing order.RECORD follows the reordering.<P><LI><P><PRE> SUBROUTINE HEAPI3(CRITER, RECRD1, RECRD2, RECRD3, N) INTEGER N INTEGER RECRD1(N), RECRD2(N), RECRD3(N) INTEGER CRITER(N)</PRE><P> sorts the<A NAME=3447> </A> values of CRITER in increasing order.RECRD* follows the reordering.<P><LI><P><PRE> SUBROUTINE DHEAP(CRITER,RECORD,N) INTEGER N,RECORD(N) DOUBLE PRECISION CRITER(N)</PRE><P> sorts the<A NAME=3448> </A> values of CRITER in increasing order.RECORD follows the reordering.<P><LI><P><PRE> SUBROUTINE HPLX2I(CRITER, N) INTEGER N INTEGER CRITER(2, N)</PRE><P>lexicographically sorts the values<A NAME=3449> </A> of CRITER(1, *) and CRITER(2, *) in increasing order.<P><LI><P><PRE> SUBROUTINE HPLX2R(CRITER, RECORD, N) INTEGER N REAL CRITER(2, N) INTEGER RECORD(N)</PRE><P>lexicographically sorts the values<A NAME=3450> </A> of CRITER(1, *) and CRITER(2, *) in increasing order.<P><LI><P><PRE> SUBROUTINE HPLXNI(CRITER, MM, N) INTEGER N, MM INTEGER CRITER(MM, N)</PRE><P>lexicographically sorts the values<A NAME=3451> </A> of CRITER(1, *), CRITER(2, *) ... CRITER(MM, *) in increasing order.<P><LI><P><PRE> SUBROUTINE HPLXNR(CRITER, MM, N) INTEGER N, MM REAL CRITER(MM, N)</PRE><P>lexicographically sorts the values<A NAME=3452> </A> of CRITER(1, *), CRITER(2, *) ... CRITER(MM, *) in increasing order.<P><LI><P><PRE> INTEGER FUNCTION IDICHO(CRIT, N, VAL) INTEGER N INTEGER CRIT(N), VAL</PRE><P> searches for value<A NAME=3453> </A> VAL in CRIT by dichotomy<A NAME=3454> </A>. CRIT is assumed to be sorted in increasing order. <BR><P>Input: CRIT, N, VAL <BR><P>Output: IDICHO = Index in CRIT if VAL is found;<P>if VAL <b><</b> CRIT(1);<P>N if VAL <b>></b> CRIT(N). <BR><P>The following relation holds: <DIV ALIGN=center>CRIT(IDICHO(CRIT, N, VAL)) <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img11.gif"> VAL <b><</b> CRIT(IDICHO(CRIT, N, VAL)+1) </DIV><P><LI><P><PRE> INTEGER FUNCTION DICHO(CRIT, N, VAL) INTEGER N REAL CRIT(N), VAL</PRE><P>searches for value VAL<A NAME=3459> </A> in CRIT by dichotomy.<P> CRIT is assumed to be sorted in increasing order. <BR><P>Input: CRIT, N, VAL <BR><P>Output: DICHO = index in CRIT if VAL is found;<P>if VAL <b><</b> CRIT(1);<P>N if VAL <b>></b> CRIT(N). <BR><P>The following relation holds: <DIV ALIGN=center>CRIT(DICHO(CRIT, N, VAL)) <IMG BORDER=0 ALIGN=MIDDLE ALT="" SRC="img11.gif"> VAL <b><</b> CRIT(DICHO(CRIT, N, VAL)+1) <P></DIV></UL><P><P><P><HR SIZE=3 WIDTH="75%"><IMG SRC="../icons/smallmod.gif" WIDTH=211 HEIGHT=50 ALIGN=BOTTOM ALT="Modulef"><A NAME=tex2html1632 HREF="node98.html"><IMG BORDER=0 ALIGN=BOTTOM SRC="../icons/previous_motif.gif" ALT="previous"></A><A NAME=tex2html1638 HREF="node92.html"><IMG BORDER=0 ALIGN=BOTTOM SRC="../icons/up_motif.gif" ALT="up"></A><A NAME=tex2html1640 HREF="node100.html"><IMG BORDER=0 ALIGN=BOTTOM SRC="../icons/next_motif.gif" ALT="next"></A><A NAME=tex2html1642 HREF="node2.html"><IMG BORDER=0 ALIGN=BOTTOM SRC="../icons/contents_motif.gif" ALT="contents"></A><A HREF="../Guide6-18/node99.html"><IMG BORDER=0 SRC="../icons/zoom18.gif" ALIGN=BOTTOM ALT="[BIG]"></A><A HREF="../Guide6-14/node99.html"><IMG BORDER=0 SRC="../icons/zoom14.gif" ALIGN=BOTTOM ALT="[Normal]"></A><A HREF="../Guide6-10/node99.html"><IMG BORDER=0 SRC="../icons/zoom10.gif" ALIGN=BOTTOM ALT="[small]"></A><BR><B> Next: </B> <A NAME=tex2html1641 HREF="node100.html">7.8 Implementation aids</A><B>Up: </B> <A NAME=tex2html1639 HREF="node92.html">7 Internal programs</A><B> Prev: </B> <A NAME=tex2html1633 HREF="node98.html">7.6 Matrix and vector manipulations</A><B><A HREF="node2.html" >Contents</A></B><BR> <HR><P><ADDRESS></ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -