107 lines
11 KiB
HTML
107 lines
11 KiB
HTML
<!-- Common Lisp HyperSpec (TM), version 7.0 generated by Kent M. Pitman on Mon, 11-Apr-2005 2:31am EDT -->
|
|
<HTML>
|
|
<HEAD>
|
|
<TITLE>CLHS: Function SORT, STABLE-SORT</TITLE>
|
|
<LINK HREF="../Data/clhs.css" REL="stylesheet" TYPE="text/css" />
|
|
<META HTTP-EQUIV="Author" CONTENT="Kent M. Pitman">
|
|
<META HTTP-EQUIV="Organization" CONTENT="LispWorks Ltd.">
|
|
<LINK REL=TOP HREF="../Front/index.htm">
|
|
<LINK REL=COPYRIGHT HREF="../Front/Help.htm#Legal">
|
|
<LINK REL=DISCLAIMER HREF="../Front/Help.htm#Disclaimer">
|
|
<LINK REL=PREV HREF="f_revers.htm">
|
|
<LINK REL=UP HREF="c_sequen.htm">
|
|
<LINK REL=NEXT HREF="f_find_.htm">
|
|
</HEAD>
|
|
<BODY>
|
|
<H1><A REV=MADE HREF="http://www.lispworks.com/"><IMG WIDTH=80 HEIGHT=65 ALT="[LISPWORKS]" SRC="../Graphics/LWSmall.gif" ALIGN=Bottom></A><A REL=TOP HREF="../Front/index.htm"><IMG WIDTH=237 HEIGHT=65 ALT="[Common Lisp HyperSpec (TM)]" SRC="../Graphics/CLHS_Sm.gif" ALIGN=Bottom></A> <A REL=PREV HREF="f_revers.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Previous]" SRC="../Graphics/Prev.gif" ALIGN=Bottom></A><A REL=UP HREF="c_sequen.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Up]" SRC="../Graphics/Up.gif" ALIGN=Bottom></A><A REL=NEXT HREF="f_find_.htm"><IMG WIDTH=40 HEIGHT=40 ALT="[Next]" SRC="../Graphics/Next.gif" ALIGN=Bottom></A></H1>
|
|
|
|
<HR>
|
|
|
|
<A NAME="sort"><A NAME="stable-sort"><I>Function</I> <B>SORT, STABLE-SORT</B></A></A> <P>
|
|
<P><B>Syntax:</B><P>
|
|
<P>
|
|
|
|
<B>sort</B> <I>sequence predicate <TT>&key</TT> key</I> => <I>sorted-sequence</I><P>
|
|
|
|
<B>stable-sort</B> <I>sequence predicate <TT>&key</TT> key</I> => <I>sorted-sequence</I><P>
|
|
<P>
|
|
<P><B>Arguments and Values:</B><P>
|
|
<P>
|
|
<I>sequence</I>---a <A REL=DEFINITION HREF="26_glo_p.htm#proper_sequence"><I>proper sequence</I></A>. <P>
|
|
<I>predicate</I>---a <A REL=DEFINITION HREF="26_glo_d.htm#designator"><I>designator</I></A> for a <A REL=DEFINITION HREF="26_glo_f.htm#function"><I>function</I></A> of two arguments that returns a <A REL=DEFINITION HREF="26_glo_g.htm#generalized_boolean"><I>generalized boolean</I></A>. <P>
|
|
<I>key</I>---a <A REL=DEFINITION HREF="26_glo_d.htm#designator"><I>designator</I></A> for a <A REL=DEFINITION HREF="26_glo_f.htm#function"><I>function</I></A> of one argument, or <A REL=DEFINITION HREF="a_nil.htm#nil"><B>nil</B></A>. <P>
|
|
<I>sorted-sequence</I>---a <A REL=DEFINITION HREF="26_glo_s.htm#sequence"><I>sequence</I></A>. <P>
|
|
<P><B>Description:</B><P>
|
|
<P>
|
|
<A REL=DEFINITION HREF="#sort"><B>sort</B></A> and <A REL=DEFINITION HREF="#stable-sort"><B>stable-sort</B></A> destructively sort <I>sequences</I> according to the order determined by the <I>predicate</I> function. <P>
|
|
If <I>sequence</I> is a <A REL=DEFINITION HREF="26_glo_v.htm#vector"><I>vector</I></A>, the result is a <A REL=DEFINITION HREF="26_glo_v.htm#vector"><I>vector</I></A> that has the same <A REL=DEFINITION HREF="26_glo_a.htm#actual_array_element_type"><I>actual array element type</I></A> as <I>sequence</I>. If <I>sequence</I> is a <A REL=DEFINITION HREF="26_glo_l.htm#list"><I>list</I></A>, the result is a <A REL=DEFINITION HREF="26_glo_l.htm#list"><I>list</I></A>. <P>
|
|
<A REL=DEFINITION HREF="#sort"><B>sort</B></A> determines the relationship between two elements by giving keys extracted from the elements to the <I>predicate</I>. The first argument to the <I>predicate</I> function is the part of one element of <I>sequence</I> extracted by the <I>key</I> function (if supplied); the second argument is the part of another element of <I>sequence</I> extracted by the <I>key</I> function (if supplied). <I>Predicate</I> should return <A REL=DEFINITION HREF="26_glo_t.htm#true"><I>true</I></A> if and only if the first argument is strictly less than the second (in some appropriate sense). If the first argument is greater than or equal to the second (in the appropriate sense), then the <I>predicate</I> should return <A REL=DEFINITION HREF="26_glo_f.htm#false"><I>false</I></A>. <P>
|
|
The argument to the <I>key</I> function is the <I>sequence</I> element. The return value of the <I>key</I> function becomes an argument to <I>predicate</I>. If <I>key</I> is not supplied or <A REL=DEFINITION HREF="a_nil.htm#nil"><B>nil</B></A>, the <I>sequence</I> element itself is used. There is no guarantee on the number of times the <I>key</I> will be called. <P>
|
|
If the <I>key</I> and <I>predicate</I> always return, then the sorting operation will always terminate, producing a <A REL=DEFINITION HREF="26_glo_s.htm#sequence"><I>sequence</I></A> containing the same <A REL=DEFINITION HREF="26_glo_e.htm#element"><I>elements</I></A> as <I>sequence</I> (that is, the result is a permutation of <I>sequence</I>). This is guaranteed even if the <I>predicate</I> does not really consistently represent a total order (in which case the <A REL=DEFINITION HREF="26_glo_e.htm#element"><I>elements</I></A> will be scrambled in some unpredictable way, but no <A REL=DEFINITION HREF="26_glo_e.htm#element"><I>element</I></A> will be lost). If the <I>key</I> consistently returns meaningful keys, and the <I>predicate</I> does reflect some total ordering criterion on those keys, then the <A REL=DEFINITION HREF="26_glo_e.htm#element"><I>elements</I></A> of the <I>sorted-sequence</I> will be properly sorted according to that ordering. <P>
|
|
The sorting operation performed by <A REL=DEFINITION HREF="#sort"><B>sort</B></A> is not guaranteed stable. Elements considered equal by the <I>predicate</I> might or might not stay in their original order. The <I>predicate</I> is assumed to consider two elements <TT>x</TT> and <TT>y</TT> to be equal if <TT>(funcall </TT><I>predicate</I><TT> </TT><I>x</I><TT> </TT><I>y</I><TT>)</TT> and <TT>(funcall </TT><I>predicate</I><TT> </TT><I>y</I><TT> </TT><I>x</I><TT>)</TT> are both <A REL=DEFINITION HREF="26_glo_f.htm#false"><I>false</I></A>. <A REL=DEFINITION HREF="#stable-sort"><B>stable-sort</B></A> guarantees stability. <P>
|
|
The sorting operation can be destructive in all cases. In the case of a <A REL=DEFINITION HREF="26_glo_v.htm#vector"><I>vector</I></A> argument, this is accomplished by permuting the elements in place. In the case of a <A REL=DEFINITION HREF="26_glo_l.htm#list"><I>list</I></A>, the <A REL=DEFINITION HREF="26_glo_l.htm#list"><I>list</I></A> is destructively reordered in the same manner as for <A REL=DEFINITION HREF="f_revers.htm#nreverse"><B>nreverse</B></A>. <P>
|
|
<P><B>Examples:</B><P>
|
|
<P>
|
|
<PRE>
|
|
(setq tester (copy-seq "lkjashd")) => "lkjashd"
|
|
(sort tester #'char-lessp) => "adhjkls"
|
|
(setq tester (list '(1 2 3) '(4 5 6) '(7 8 9))) => ((1 2 3) (4 5 6) (7 8 9))
|
|
(sort tester #'> :key #'car) => ((7 8 9) (4 5 6) (1 2 3))
|
|
(setq tester (list 1 2 3 4 5 6 7 8 9 0)) => (1 2 3 4 5 6 7 8 9 0)
|
|
(stable-sort tester #'(lambda (x y) (and (oddp x) (evenp y))))
|
|
=> (1 3 5 7 9 2 4 6 8 0)
|
|
(sort (setq committee-data
|
|
(vector (list (list "JonL" "White") "Iteration")
|
|
(list (list "Dick" "Waters") "Iteration")
|
|
(list (list "Dick" "Gabriel") "Objects")
|
|
(list (list "Kent" "Pitman") "Conditions")
|
|
(list (list "Gregor" "Kiczales") "Objects")
|
|
(list (list "David" "Moon") "Objects")
|
|
(list (list "Kathy" "Chapman") "Editorial")
|
|
(list (list "Larry" "Masinter") "Cleanup")
|
|
(list (list "Sandra" "Loosemore") "Compiler")))
|
|
#'string-lessp :key #'cadar)
|
|
=> #((("Kathy" "Chapman") "Editorial")
|
|
(("Dick" "Gabriel") "Objects")
|
|
(("Gregor" "Kiczales") "Objects")
|
|
(("Sandra" "Loosemore") "Compiler")
|
|
(("Larry" "Masinter") "Cleanup")
|
|
(("David" "Moon") "Objects")
|
|
(("Kent" "Pitman") "Conditions")
|
|
(("Dick" "Waters") "Iteration")
|
|
(("JonL" "White") "Iteration"))
|
|
;; Note that individual alphabetical order within `committees'
|
|
;; is preserved.
|
|
(setq committee-data
|
|
(stable-sort committee-data #'string-lessp :key #'cadr))
|
|
=> #((("Larry" "Masinter") "Cleanup")
|
|
(("Sandra" "Loosemore") "Compiler")
|
|
(("Kent" "Pitman") "Conditions")
|
|
(("Kathy" "Chapman") "Editorial")
|
|
(("Dick" "Waters") "Iteration")
|
|
(("JonL" "White") "Iteration")
|
|
(("Dick" "Gabriel") "Objects")
|
|
(("Gregor" "Kiczales") "Objects")
|
|
(("David" "Moon") "Objects"))
|
|
</PRE>
|
|
</TT> <P>
|
|
<P><B>Side Effects:</B> None.
|
|
<P>
|
|
<P><B>Affected By:</B> None.
|
|
<P>
|
|
<P><B>Exceptional Situations:</B><P>
|
|
<P>
|
|
Should be prepared to signal an error of <A REL=DEFINITION HREF="26_glo_t.htm#type"><I>type</I></A> <A REL=DEFINITION HREF="e_tp_err.htm#type-error"><B>type-error</B></A> if <I>sequence</I> is not a <A REL=DEFINITION HREF="26_glo_p.htm#proper_sequence"><I>proper sequence</I></A>. <P>
|
|
<P><B>See Also:</B><P>
|
|
<P>
|
|
<A REL=DEFINITION HREF="f_merge.htm#merge"><B>merge</B></A>, <A REL=CHILD HREF="03_ba.htm">Section 3.2.1 (Compiler Terminology)</A>, <A REL=CHILD HREF="03_f.htm">Section 3.6 (Traversal Rules and Side Effects)</A>, <A REL=CHILD HREF="03_g.htm">Section 3.7 (Destructive Operations)</A> <P>
|
|
<P><B>Notes:</B><P>
|
|
<P>
|
|
If <I>sequence</I> is a <A REL=DEFINITION HREF="26_glo_v.htm#vector"><I>vector</I></A>, the result might or might not be simple, and might or might not be <A REL=DEFINITION HREF="26_glo_i.htm#identical"><I>identical</I></A> to <I>sequence</I>. <P>
|
|
<P><HR>The following <A REL=META HREF="../Front/X3J13Iss.htm">X3J13 cleanup issues</A>, <I>not part of the specification</I>, apply to this section:<P><UL><LI> <A REL=CHILD HREF="../Issues/iss240.htm">MAPPING-DESTRUCTIVE-INTERACTION:EXPLICITLY-VAGUE</A><LI> <A REL=CHILD HREF="../Issues/iss083.htm">CONSTANT-MODIFICATION:DISALLOW</A><P></UL><HR>
|
|
|
|
<A REL=NAVIGATOR HREF="../Front/StartPts.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Starting Points]" SRC="../Graphics/StartPts.gif" ALIGN=Bottom></A><A REL=TOC HREF="../Front/Contents.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Contents]" SRC="../Graphics/Contents.gif" ALIGN=Bottom></A><A REL=INDEX HREF="../Front/X_Master.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Index]" SRC="../Graphics/Index.gif" ALIGN=Bottom></A><A REL=INDEX HREF="../Front/X_Symbol.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Symbols]" SRC="../Graphics/Symbols.gif" ALIGN=Bottom></A><A REL=GLOSSARY HREF="../Body/26_a.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Glossary]" SRC="../Graphics/Glossary.gif" ALIGN=Bottom></A><A HREF="../Front/X3J13Iss.htm"><IMG WIDTH=80 HEIGHT=40 ALT="[Issues]" SRC="../Graphics/Issues.gif" ALIGN=Bottom></A><BR>
|
|
|
|
<A REL=COPYRIGHT HREF="../Front/Help.htm#Legal"><I>Copyright 1996-2005, LispWorks Ltd. All rights reserved.</I></A><P>
|
|
</BODY>
|
|
</HTML>
|