ࡱ> `!P &y2=~J^ Y xڽklg7J[zNO{NK-)(ph酶 ?ahuiMm8KtNcd/1:5KtF1$ƙ@Q9{))Ls?{<^$K"rU_2'8d$Zg<-<ޝIbHX?⥌N˴rx IbGج6? k}> ־uLJp[7pxjo˝#iH̕&!;얿JܒN-=ʀܕ!8!N/ncUO=lCQ!>;^%>47%w2f4E;'E=]Xߌ~U1r''']-^G A KI^ooI|iI|~ E)7@~o[Q~M[J%(`_$KՒ۔wÜ۬[aD?lZ~%5sx3i_[߆5P 7(5#=oe;dn衯9rh7)ߠ#F߷$U /Kꯕ9y4QY\\^&I(|ϞOȧi <:Naa ϽGF"K"KD KrYrdH-s9/%S=ͪ͘Yk7e eyI.+Cn@Te | i/,]L1նjӵsq1)8)8ߚg"()g|{DoˆAfE}Do/k#j-Ф,~<]C^"zx$z"5DĆ8J8}㌟K^dv#E))͞.ybY=[cG9lEmDߦh,c(}:vy` ۥi3J/gaa2dNI=OQ~uڈQi4Qb'j)5 EEQl ;s0լ3kgwR9S۰ 9ՠصPN3ۙl?5鯯'C&DiCP)]Ot$:u:խ.U5?GWrty_A:W֋.Zmϰ-@f|'ꤵszy8G"i}Ʀ#i4%ӱҌ "6G6 9,(om.*.lL2ڄ>e 4j2*}Yx{/p2{{a^AmGt{0QXk8=wO(c}7ظy{$qO 91#qF2 3ʐM"bqQty?'iŃdYkC`Hԣ̝AKYC9`rDn r c|5c5S^`9=B֔䜤atu9,XDY3~1_Zs07ѣxs]xq7I?-Hh4W1^ `%& tV3+=|h efʳZ(j&khW3!?B,A:h^!ʨ`Y⾑xBbmaU& s;Is븯HDtN]JzʭPE_x8G!SD*cVg! ^d$Nt "7<$mĮ|^ء]dɡxLkdfYXXWa!UV {#J9b鐛z#VO/ya~_uOtQ};fL9KDY!e 2Xl>npY'-VS lc 4˖ ɒ2 )% +#$]%zbG(BAPB$}9zy"dhtIɴ}2 9/f3$U^D\V̗a] V"ZVW :BBl)Be#搙=3١N4tϾ&6g 'pEjm-h+l8d!Xܮ%ЗsߊhWWÿsJX_7K%wnUIRG7h(n=(KUa9z.̉q`;G䃹9 IYhq2"G@ g. zpF({Wg`+[A DA7|Tk=zu\BeyN F @ $ a[gk| -ZnF?hIɌ+Ch @_o]UXө1@9AnS+{VBvPɥU9![\aǂ,zM^EaY ;-;FTP^F\9H'=t}fMrAalbs:q0l&Wl+aEJJ=BՆ-}09:t{jE62m"6ܪp;J{轂ȵowWɿ7h#c5.aX7pe.@>l꠷/Zx|@i Gd# R} >L~ތ?#yy%4,&-L6;8$8A? c@Gx;UƝ{ \_WEƿs,Xkt:ID}ID}AD}!hz?jUo|됪 fAh}:v?D @ʍdF,@Vj ntqxCfX+' 5Xb|Mؤ-v3}O hsX,@O9=s}݉<-i;;|*zb}fGW% 'Sx5ԝ*L-|>v%",Ge(,%+.A%BZ'4 wPǺz2>pPY9J]Ov%!ٴ>rbZww3}5dVkñ|`mح/'s?ف45=~5*|se:i{!d SIвGkcv,2۱J5֭UVMg'_]m Mnho67mn2^V}Eǟ(%7:2pp b^dRqD˓JS0w4Uhjowu'`!Nr ]hpf*i:% ?4x}y眻<1llc7Y d,.)WYؒ%'RYʖ$B[J IϷ^ys=s>~F 'S#&k)2r)#%ʨH+"}z$A;DK! Yl KH8e !hMtQ*\v$djJ*wxQ5ZX9I[:V3'@v= '6]EʫEH"FuW{0CXT/l5I6-Yd1}l0SjR,9K'ʮzh=c?1ޕ^H'-ʩ6m+HwEe/7R.[~wpҽ #\Z ^hzIM>ꔊ DX$sQ]UzZMHtŻf,i9iL꾑\]-W\"O %INbn[~t@6CU%W,q4QdGS~}xhv‘r.rR CZpE &AKU38%c52=rP^S(?JܳfnxM+"9ߕQ].voc4kvk_z(z"&x^ ÃbJ%_5f?xt-h]wUĺQ;T|bgv?)ʘD!17ffF H׻ğ(dY:}S<Й9cflTrUiWgw3PDωF%I^)t11`|'9tNmbLg/vvMƖD/:em>jMP֝^ u2jUuWUþ#CzO#.W`rϿŜ+ZѧpuuW=a_v"c5(`r`)M27Q<(dE8'Lqe[=DM0ݦ#V{[/x."-VT5IY\ W31X B\Q%cn p4BƒG&uq2SmI= F4sx䳨.B"}R{.S3MyߑqEGdЉQTZ]:U+褚E!MaOG ?NXc/$~^nUũڇE.Jޏ' =*xEH7]ӟ,ónO8ʉng܋7&̭Va%BUkpډs \.y|s˰,‚0 0 !a"y\~zó*/QtV=IJ{TwڤSS:^QAy7H"T$\b%YjFUW*ɿs^OݠL~3Ed{@˲3hlF'9bQRE VGikiXFIRny(C%}un"?l [0$)?.u=Le.(3۴dz4ꀟqqK)<_&<-%Ny n$HDц.ߊ.(}R:8/9&v.6jjdL5c~ Ye6C!38nCU%,(gr $ح;2 9{sB+haF j lETG3l j^ח9}KfԿ=az*iUf*`֩ѵ3f.Kk_k߆x${<":%6->7LBGC˾'O72 :?ѱqDc.VgD>_|-k^[CgPz%:DfM>OMf%yTs 2f t6 d|'+z{ڍo}Vf0ȤA/JDƈxS'85UMyib%_K!ߥ"X%L>l*c2 56u96E^Zon5ʔŭl佸՜] t:J:h2O3oRF046Oho.I6J&/;Itwz~nL^ ϋ[:e'(05 ͣ랰=bPiF _25b0K{[4g&Mgi H#6JqRX~W5"!$hUo=ya7Bᬪf0AۊXX!U?C2tU͆`%vبj`}<)Ee:*/]v{cJ?OȆ'pVV 8)MT2}#fmy¹G *WyI_2I2FחUtpVE@$꼧 庙ܢ; \cyByW1]g=K,u}b>.֙>%2_}qN?yc]f;6O6D)&+1S *S'Zq9jJTIj u [F(C?<qް9?x ֫DzMuj*R邼B;e>D>I{Ѕ૜i$ ?Fӷ0F2O3 uUpdzu@ {)VC* ~w=uJ@> 9K&|KovNYwY%~eze:zAUtNhje%/0T՗U֭2zg3.uRއ'6`i=5+[̆&m2ƙk>w̻ o@33)2`T+8K0UIS5MJ6yUYeN2u@nK5WU/S :sd?J5TGSV=řj33_Tަ'\/pn+8i.8{X=6OZGmO<ẽzlA&Zxt[[ &(f؞sX6ƪܷ-mU%zvβs;w4oFnκG{(ٟeA{S&ڃ=޲k+=֩Yvk?_mr%6ROڶ+lI.Cv:zmݵ[Pʹ)jlaOse>H s;(c a:'y/uܣEA}ӪYr9!ӶLOB Z٧}{s-Uiˡ|;TE#HVY2OxqUT@u Q^ [vfh,ƺ``mtE~U.ء[T{~\TO٠^PbZk{]sjAH~~UU/c,UY/)}7 LjuO8'݂j 3,RX2Oxg{=xMM >W9Wߠ}n  ^\&h8dU?^p2.a"i.9[Ht]k:DQ;_T"mݶilo[c:;u>Q2,3­KNqeAv AWE~J > ^lsI;V<E Wx_ n&n8䆊ծ;)Kly$feb=",-,i]m\5+'pxg\F;7Bt3v1q3y}nkO`A'q1x\^M83o'Zs ߹h!ߩVSJ؟ok.2fJ3͵Cm5δIf_qNc jmB<89_G5c]{ҷb3 >֧)1-]~un<1LtaOq[j(;V/IsbY| tak}TM/cLgQ!_X}I*RU ڬ|`!fI T6fxn8{x>tm`_6WY-c#n[*K_d=>LXbKE-t6bZIiՠVT(x'ul'\ץlb%fސM:Q^ܸL3ckpfAװ*ʍkЁ4kk нT;!9.(M@X`!hecsq`12+ +81xڝWGgfww %f$@ [\$8łCyUݯn*@g[3Sc%NVhEacGK85/JS;^h݇[oXQرSAeFLkH_2䞙'WhdzEX~7ɬĖ 01eI+LYh0=fKGUBu 2ey,SYaP;r]=7DlԺQ({9f0o4yÇW|tk?0i6foks<[v\oD)=@*dQyFle2MALIevUcHETʢI¬[f;59E[UZi*cyIM^jbSzȴ%K(]nvnIÞoy'6RBVfr{vąR¤̗𓬆r ᏒJ>+TR_J |nuaXۍ֮7rmqa"sEˋ7\|$yC} g447~[CkBZ~.v/4(-|~$?UVS'p|wOtnZ~G/:[Ġ[tۂ3#&2+H)݃[? \(8ł\*8C\5ϟ{a+7 vq``lCww_C蘐T$P@. ${f.9Fk(A|oz]׃Nδu MvikGnpͧaFV^?$|F7s_z/ }K7|U}g,tUmX+/0(3̧|8s9Y0CrЗ[wМxNPWYyUWyM*_SDV7hipivp&;_ZJ0#)UГb-譯D}NO~xHpWG}k39O~IWGnV&S3H]lԬlX!ή8v$HVGr}|6RUc(O$}] \y5)ܗ6٪vWikVpU#i%\8@b{ r9@5s0ń.pI`K \d~pE`+\X*Wvfut77 08n>v .޻~ ? HC*%@N;P? /}rbukX~ci DFGu*_WfR4 -n;sϺ|ԍ-n/pFRʵqA!-e<2kJǑcS;J3TJLY([y!tAEk0¼ N*an*%(?Vl9Δ Q|bWA 0*DSIgw\WY_q|=<\3q0#[nC@!8Z9SL-DnvӸ ή(p3aRwמst);8Qb](=!DuyqHFx~ tgBBjH MSeC3y)];Js%wn*ŤLvW3c0.$ fwQ=Re T 3cYFͿ^gy4!? ]*v|fH1;W)ZS}#.6=NpnjVE9I`Ui4PQ|J#*Ϩb p` ؜i~3hnq*%)! '_DžpL9\ q,0J )ܣ[QsA9|J!k%&ʿ(>nw(GڒJ>k+i.Oڪ|3aj V؆mymcff۔7fVe,RB[~5UVU*b-6y+Yٵ?:wfgz!|SzVԿ(>nwkx8QrZūGJej+@ \#Tvyδǫ^1$.(9'[q2)ⳜOs&>!Jm3#uǕh>Bz-H,硘T6Y Oe$՜F,R7 z!Jomwtt m\+9Za @-*i.VF)~V*5?cWH,TMRJm$ aJ##LQCNcB9^"߄T=-UJO2@,[xlᲉGF+Z(H\ ta*$10/},7br*Uw%Murj.@WҼuH7_Cпl>T6|C\;%L>oUlĝSu]HUH`4 J ֱ!ߗ'|G>;E߆|7Gs~[_S%XkM:oUA=jAJ$ [ p.pOo>٣صO5.bΛ.0\\ݒ L;j KKS Ҵ&%/4NϤ i K,k0L,3@SLUf0܇pj&-y0v@h iņ7&aaqa-޶psKhʅmF(eg*nv/'B=jh_R[{X<4 >LVӴv+]b J)?0AOS5AU)>Ѽ=)%L % '8p'8 d8ƶp4 ~VZlkw+*t$tEqf51V#q}uʎ(t"hlNGD4W\n}+{[UcU^+HSx˺c|iſ8@rp$g@l wmX\oa9M`{ H?ݎ5lOf &bnfbF dҺNƘ2Ҭ0GSEԖl1Mdi.{M 9`:A]a_}fga@Np`VFJeR.v4YA?jRZ؞Hu TkJ]/naOt{CymvllMnMVnڬ91۝\غm^f]*hE+_R+]ej؅2r=`ʭt}aP͍n4r!R n5\q'{]B MWxMn9nt{0n?TjViZqG֩!.q (ͤnupikt0W&Hkɫ\2IF~EJ8k8b.Z;pwx܅p7ƽXc~<(>puf Ĵ2OP@e )k|e:W3a:_|&[1p'.q0/g4DŽ'$HȻx! j(1Vm~ܲK+x ҄j@,;N \JQR{8]zci!qn=%c('N(L8*]>֢b2#5wv Pj1"uЇvirEO͆8p `?ycm o'X[A0eK/";L>yt'.nrӑ<|Ǽv3K۝t,)9E??IgX:e' ;jw؆;څ]rڪ&A5JWؕLYjWhj@k7UfO"z<܎|j:;DL ezrDu'i/]w{\inQ7{^P{:?4GjnQ浏}Ju3e_P5s+++*}N%ծ+io+TwIK$US}VI{;t]ݭ>So'Uw:kr8?W\s%.şr9.JRTۅ8ZdW.Y*Et悜)JY.jjq|. tBR/]-Ymegu8mșlS`[r:ۖSvĶ 'P)Wvf_ޙ4P]mVVRr˖⸶UP,ɔJ*9-[R}*tLW 2T@ar3Yu3#pkg[u=c q=o(QF9:ua3TQu3 h+Av"[>57`?^`zI%{JF?ǝ^1'im4>B04OG_i 拉y+-Mze#T|^Lsx_D=w׼Rc1=tl7L]g̻=O]\R~*NzZ@Jie*0FCRhuF.;p!K\m{m=}+991Pr^6R9N9d7+&LNi踶r~&7lIc#L^ZDž{.sN8ʰ2ns 4q]ˁXJ\m'TJN!9|gzHe&9RZ)Q .[LMDžpJT&T.dgl%yFgqhyF^s-~uctFO(   3 -M 2Microsoft ClipArt Gallery $MS_ClipArt_Gallery02Microsoft ClipArt Gallery00M 2Microsoft ClipArt Gallery $MS_ClipArt_Gallery02Microsoft ClipArt Gallery01M 2Microsoft ClipArt Gallery $MS_ClipArt_Gallery02Microsoft ClipArt GalleryL/ 0|DTimes New Roman#M |dv 0|( 0DComic Sans MSn#M |dv 0|( 0B DTahomaans MSn#M |dv 0|( 0"0DWingdings MSn#M |dv 0|( 0@DSymbolgs MSn#M |dv 0|( 0c.  @n?" dd@  @@`` xpqIP   1a)/57  "#%&'()*+,-.189 +%2#a? CE :  O2$&y2=~X 2$ ;]Iפ5Ì71X 2$r ]hpf*i:V2$hecsq`1, 0e0e A@A5%8c8c     ?1d0u0@Ty2 NP'p<'p@A)BCD|E?@8+gʚ;S4ʚ; g4<d<dv 0pppp@ <4!d!d` 0,$M <4dddd` 0,$M <4BdBd` 0,$M $g4EdEdv 0p"p@ pp? %O == Remember Sorting_Machine? 4Sorting_Machine Continued&  4Sorting_Machine Continued& VType ( inserting: boolean contents: multiset of Item ) Initial value (true, {}) d8 8 $,  %o4A Math Type: Multiset Multisets are just like sets except that duplicates are allowed In set theory: {2, 18, 2, 36} = {2, 18, 36} and |{2, 18, 2, 36}| = 3 In multiset theory: {2, 18, 2, 36} /= {2, 18, 36} and |{2, 18, 2, 36}| = 4 BZ :BA$ ~ @ 4Sorting_Machine Continued& Operations m.Insert (x) m.Change_To_Extraction_Phase ( ) m.Remove_First (x) m.Remove_Any (x) m.Is_In_Extraction_Phase ( ) m.Size ( )2 z y   Sorting AlgorithmsSelection Sort Insertion Sort Mergesort Quicksort Heapsort Tree Sort &  :A Sort Procedureprocedure Sort ( alters Queue_Of_Item& q ); /*! ensures q is permutation of #q and IS_ORDERED (q) !*/z )#CMath Definitionmath operation IS_ORDERED ( s: string of Item ): boolean explicit definition for all u, v: Item where ( * is substring of s) (ARE_IN_ORDER (u, v))!  $ .,Lb 1p5An Old Math Definitionmath operation ARE_IN_ORDER ( x: Item, y: Item ): boolean restriction for all x, y, z: Item (ARE_IN_ORDER (x, x) and (ARE_IN_ORDER (x, y) or ARE_IN_ORDER (y, x)) and (if (ARE_IN_ORDER (x, y) and ARE_IN_ORDER (y, z)) then ARE_IN_ORDER (x, z)))P  9+-]#<Selection SortIprocedure Remove_Min ( alters Queue_Of_Item& q, produces Item& x ); /*! requires q /= empty_string ensures (q * ) is permutation of #q and for all y: Item where (y is in elements (q)) (ARE_IN_ORDER (x, y)) !*/JZ     4 T=6Selection Sort: You Give It A TryAprocedure Sort ( alters Queue_Of_Item& q ) { }:BZ #*>Insertion Sortprocedure Insert_In_Order ( alters Queue_Of_Item& q, consumes Item& x ); /*! requires IS_ORDERED (q) ensures q is permutation of (#q * <#x>) and IS_ORDERED (q) !*/   #?6Insertion Sort: You Give It A Try@procedure Sort ( alters Queue_Of_Item& q ) { }8A ">!@ Quicksort procedure Partition ( consumes Queue_Of_Item& q, preserves Item& p, produces Queue_Of_Item& q1, produces Queue_Of_Item& q2 ); /*! ensures q1 * q2 is permutation of #q and for all x: Item where (x is in elements (q1)) (ARE_IN_ORDER (x, p)) and for all x: Item where (x is in elements (q2)) (not ARE_IN_ORDER (x, p)) !*/xZ  *  .  B(Quicksort Continued&   procedure Combine ( produces Queue_Of_Item& q, consumes Item& p, consumes Queue_Of_Item& q1, consumes Queue_Of_Item& q2 ); /*! ensures q = #q1 * <#p> * #q2 !*/ *)DQuicksort: You Give It A Try Cprocedure Sort ( alters Queue_Of_Item& q ) { }8D %>!E(Quicksort Continued&   procedure Partition ( consumes Queue_Of_Item& q, preserves Item& p, produces Queue_Of_Item& q1, produces Queue_Of_Item& q2 ) { }|Z  'F(Quicksort Continued&   procedure Combine ( produces Queue_Of_Item& q, consumes Item& p, consumes Queue_Of_Item& q1, consumes Queue_Of_Item& q2 ) { }z %G Mergesort procedure Split ( consumes Queue_Of_Item& q, produces Queue_Of_Item& q1, produces Queue_Of_Item& q2 ); /*! ensures q1 * q2 is permutation of #q and |q2| <= |q1| <= |q2| + 1 !*/ Z *- H(Mergesort Continued&   /procedure Merge ( consumes Queue_Of_Item& q1, consumes Queue_Of_Item& q2, produces Queue_Of_Item& q ); /*! requires IS_ORDERED (q1) and IS_ORDERED (q2) ensures q is permutation of #q1 * #q2 and IS_ORDERED (q) !*/ 0Z )  #IMergesort: You Give It A Try @procedure Sort ( alters Queue_Of_Item& q ) { }8A ")! Sorting_Machine: Inside StoryJ .Inside Story Continued& As an example, assume the representation for Sorting_Machine has two fields: contents_rep of type Queue_Of_Item inserting_rep of type Boolean What are some possible implementations?RMA(M  (" ^Let s Procrastinate  the Students Choice_operation m.Insert (x) m.Change_To_ Extraction_Phase () m.Remove_First (x) m.Remove_Any (x)\ Z  F$ V  what happens? #How About Eager Beavers_operation m.Insert (x) m.Change_To_ Extraction_Phase () m.Remove_First (x) m.Remove_Any (x)\ Z  F$ V  what happens? $Are There Other Possibilities?_operation m.Insert (x) m.Change_To_ Extraction_Phase () m.Remove_First (x) m.Remove_Any (x)\ Z  F$ V  what happens? K!A Heapsort Implementation An ARE_IN_ORDER Heap is a special kind of binary tree: shape property: the tree is complete ordering property: for each item x in the tree, ARE_IN_ORDER (x, child) holds for each child of xD77QL"Complete Binary Trees^All levels of the tree are completely filled up except possibly the bottom level. Any  holes in the bottom level must appear to the right of all existing items at that level.M#Heap Ordering PropertyFor each item x in the tree: N$ExamplesO%HeapsortBuild an ARE_IN_ORDER heap with the items to be sorted using the specified ARE_IN_ORDER Implement Remove_First so that, after removing the first item in the ordering from the heap, it restores the heap properties P&How Will Remove_First Work?g-Sift _Root _Downh.>Turning a Complete Tree Into a HeapS)tTurning a Complete Tree Into a Heap Continued& T*;Mapping Complete Binary Tree Positions Into Array LocationsU+Remember Array Operations?Za.Set_Bounds (lower, upper) a[i] --accessor operation a.Lower_Bound () a.Upper_Bound ()V,Insertion-Phase Container?{What is the effect of a.Set_Bounds (lower, upper)? At what point will the Sorting_Machine be ready to set the array bounds?j/5Swapping/Comparing Two Elements in an Array FGiven: object Array_Of_Item a; object Integer i, j; What s wrong with: a[i] &= a[j] and Item_Are_In_Order::Are_In_Order (a[i], a[j])? They violate the repeated argument rule a[i] and a[j] are references to parts of a s representation: the parts could be the same (see Partial_Map_Kernel_3)IZ?ZZ ,:  %Hl1Swapping Two Array ElementsvUse a.Exchange_At (i, j) instead of a[i] &= a[j] Exchange_At is an Array extension It requires that a.lb i, j a.ub See AT/Array/Exchange_At.h in the RESOLVE_Catalog for complete specs  3EtFm2Comparing Two Array ElementsUse a.Are_In_Order_At (i, j) instead of Item_Are_In_Order::Are_In_Order (a[i], a[j]) Are_In_Order_At is an Array extension It requires that a.lb i, j a.ub See AT/Array/Are_In_Order_At.h in the RESOLVE_Catalog for complete specs  -7KKn39Sorting_Machine_Kernel_2: Component Coupling Diagram/% & ' ();WXYZ[]^_`abcdei!q"r# ` 33PP` 3333` ___MMM` 13` 333fpKNāvI` j@v۩ῑ΂H` Q_{>?" dd@(?n<d@ `7 `2@`7``2 n?" ddH@ f @`PR    @ ` ` p>>     (     <l^M " @   TH"M d" @   <M "U_ @   TTfM d">& @   NiM "P @   <mM "{ @   C x ?d?"mU @   6  "` M  T Click to edit Master title style! !$  0  " "   RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  6$  "@   B*  6p  "@`    D*  6,  "`   D*B  s *޽h ? 13 321B%     k (  T +  "+bb P@ # "Dwoh  s *"PP  Bd" P@bb P 0  # "Nyh  s *"P    Bd"P 0 z   <" a*h   s *"    f?d?"+)   <d  ?"pP  T Click to edit Master title style! !   0Y  " `     W#Click to edit Master subtitle style$ $  6  "`p    F*  6{ "`p  /  H*  6{ "` /  H*B  s *޽h ? 13,0 `|(    05  P   5  \*   0 5     5  ^* d  c $ ?  5   0$ 5   @ 5  RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S  6<5  `P  5  \*   6`/  `  5  *02-SortingMachine - * ,H  0޽h ? ̙33   0V(  ~  s *M  `  M  j  BGjJ?l&   `y5 xaxa1?5n bIsn t it a beauty! Go ahead . . . kick the tires!2 2  HA ?1?@P8,X $0!0 F    7/r  BGjJ? l  <jJ? Ll   <jJ?d N t    t     `d5 xaxajJ?  QChange_To_ Extraction_Phase l2   <jJ?t     `5 xaxajJ?g   6In    `5 xaxajJ? w  7Out H  0޽h ? 13l?  ??pOO>(  x  c $u/  `  /  j  BG1?  d  <1?X  d  <1?X L   Zw/ xaxa1?Y  QChange_To_ Extraction_Phase d2  <1? `    `h|/ xaxa1?; F  6In     `H/ xaxa1?; 7 F  7Out z  P    P,$D0   HA ?1? t PX $0!0    `$/ xaxa1?  S3: Sorted items come out here  r   BG1?@ z X`   X` ,$D0  HA ?1?P ` X $0!0r B BG1?X0   `X/ xaxa1?r H2: Push the button 4z `  `,$D0   ``/ xaxa1?zm  G1: Items go in here x  HG1?` *2N   C  N O$   O$ VN O$   O$ VN OQ$   OQ$    BC"DE8FBࠀ1NN1 rO2 k;  #-;OcurMv%vmhc_cGc'hrG-5-U}} }uu'M'%#;b "%"Mm  #;KvcbsO1@`OQ$ N |`   |`   B/CDE F(1lY@'/@`   B8CDEF108( @| N       BC"DE@FJ@1PP,"(HXo &6N]"u1@Tq}}eVF>>6 " o_Pgwwogg{oqwlgb]TJJEE@@@EoEX@P@@;86(11,@` N        BCDE,F6`@ 1  @`9 ! BCDEF`@ 1 @` " B8CDE4F>`@ 1 ( 8 (    @`z # B0CDE4F>`@ 1 ((( ( 0 (   @`  $ B0CDE8FB`@ 1    (0 ( (   @` ; % B(C DEF&`@ 1 (@`+S N B;} & B;} ' B0CDEF@p 00 @ B;[ ( B0C'DE4F> 0( ''"(00 0 @`V} N    )    N f   * f  N fK   + fK  " , BC'DEDFN0001`H0'h' $(@`f U  - BClDE@FJ0001P'8"(;XbglX@"'P'"$@`lK  N ~   . ~   / bBCDEF1?? w#26&@6T>cFqF>>FN]u,@mTNgvlT@'m @b_@88v8T@1@@ 80 {m^J6 @`~  N  (  0  ( j 1 :B.CEDEhFr``1.@&E@;66661,'#o_H8(68@` Z  2 BC DEF"``1   @`   N    3    4 BCDEF"``1@`   5 BCDE F*``1 @`   6 BC DE F*``1 @` ( N  Z  7  Z N  V3  8  V3  9 BCDEFࠀ1))8Oo,,,1;DIXg{oO8( vq l(g(b(]0X8X8S?IGIWDG@86(, TX@` V3 >N  7  :  7  ; |BCDEF1 @   < BC DEF1 @  = |BC DEF1 @  > B8CDEF 1 (8 @ 7 $N  Z  ?  Z tN  U  @  U N - U  A - U  B BCIDE F*1I?D_;I@`E U  C B/C#DEF"1 (/ #@`-$ \G  D BC DEF1  @`U= dG BN  L  E  L  F BCcDE@FJ1O@(,8GW o_1O;OJ?Y8c(^TO"$@` L  G BC DEF1  @`f v JN ? Z  H ? Z B I BC]DEF155'XO@,G_w"16E%OMJm@@EOXbl{'};}]eS=I%I?1''g"O?  7Ogww_{?l'Xlp@`? Z N G   J G   K B7C6DE,F61  '/#767#/ @`   L B'C"DE4F>1  " '  @`UB |d  M RBOC(DEtF~1O G @8 ( (8@@8(  08@GGG#8(G#OOO <@@`   N B C DEF"1   @`) 3  O BWCEDE,F41 E;6,''/7?G WO@G B H  0޽h ? 3333  $<(  $~ $ s *4/  `  /  ~ $ s */   " /  H $ 0޽h ? 3333 " 0(  x  c $  `   x  c $(   "   H  0޽h ? 3333  (<(  (~ ( s *2  `   ~ ( s *\/   "   H ( 0޽h ? 3333  @ L(    s *x5  S`  5  0Sorting With Sorting_Machine   `@5  ??pD ,$D0 ,// input a bunch of integers placing them in sorting machine m while (not ins.At_EOS ()) { object Integer i; ins >> i; m.Insert (i); }~0n<P?-`   `T5  ??0 p ,$D0 P// now output the same integers in sorted order m.Change_To_Extraction_Phase ();0Q0n<PP    `65  ?? pV D,$D0 Fwhile (m.Size () > 0) { object Integer i; m.Remove_First (i); outs << i <<  \n ; }n_0n<P:H  0޽h ? 3333  ,0(  ,x , c $t/  `  /  x , c $/   " /  H , 0޽h ? 3333  0(  x  c $=  `   x  c $4   "   H  0޽h ? 3333  0 0(   x   c $  `   x   c $(   "   H   0޽h ? 3333 # P0(  x  c $  `   x  c $      H  0޽h ? 3333  p0(  x  c $K  `   x  c $@k   "   H  0޽h ? 3333  *(  x  c $o  `   x  c $@z          `   ?? ,$D0 . object Queue_Of_Item tmp; while (q.Length () > 0) { object Item x; Remove_Min (q, x); tmp.Enqueue (x); } q &= tmp;t0n<Z!QH  0޽h ? 3333  0(  x  c ${ `  { x  c ${  " { H  0޽h ? 3333  /(  x  c $  `   x  c $          `u{ ?? ,$D0 3 object Queue_Of_Item tmp; while (q.Length () > 0) { object Item x; q.Dequeue (x); Insert_In_Order (tmp, x); } q &= tmp;t0n<Z!VH  0޽h ? 3333  0(  x  c $<  `   x  c $B   "   H  0޽h ? 3333  0(  x  c $2  `   x  c $   "   H  0޽h ? 3333W  0((  (x ( c $y `  y x ( c $y   y _ (  `y ??} ,$D0  if (q.Length () > 1) { object Item x; object Queue_Of_Item q1, q2; q.Dequeue (x); Partition (q, x, q1, q2); Sort (q1); Sort (q2); Combine (q, x, q1, q2); }~0n<Z!2H ( 0޽h ? 3333^  P0(  0x 0 c $\c  `   x 0 c $   P   f 0  `4y ?? g,$D0  q1.Clear (); q2.Clear (); while (q.Length () > 0) { object Item x; q.Dequeue (x); if (Item_Are_In_Order::Are_In_Order (x, p)) { q1.Enqueue (x); } else { q2.Enqueue (x); } }0n<Z"!(N!H 0 0޽h ? 3333  p8(  8x 8 c $y `  y x 8 c $xy   y  8  `y ??0 ,$D0  q.Clear (); q &= q1; q.Enqueue (p); while (q2.Length () > 0) { object Item x; q2.Dequeue (x); q.Enqueue (x); }f0n<Z4"=H 8 0޽h ? 3333  @0(  @x @ c $hy `  y x @ c $y  " y H @ 0޽h ? 3333  H0(  Hx H c $x `  x x H c $x  " x H H 0޽h ? 3333  P#(  Px P c $w  `   x P c $        P  `.x ??T ,$D0 ' if (q.Length () > 1) { object Queue_Of_Item q1, q2; Split (q, q1, q2); Sort (q1); Sort (q2); Merge (q1, q2, q); }f0n<Z!xH P 0޽h ? 3333nO   OO``tN(  t~ t s *tx `  x j t BGjJ?0l t  `xxaxa1?5n f2Are you ready to look under the hood of this baby?3 300F X 0& t  X0&N X & t X &R t "B=ChDE\Ff@@@1 Og "(4EK%K5Q=W-] hhW_K?K?QE. 04@` &R t "B5ChDE\Ff@@@1 #w(_4GF/KKQW]'hghWKKQ5F5.-04@`X    t BCDE4F>1MM.Ew]otg_XPH@@8"@3@K8\0n 8H_Q. .E\-M]|y\(tQ4mM  @`  )N  0P   t  0P N  0P   t  0P   t B=CWDEF1##WwnL4# %==QWQQ4wg_OG7(HL@` P *  t B/C4DEHFR1' '##(#(444.(#'// &(@`. ]  t BCDE4F>1      @` = z t JBCDEpFz1        :<@`\ =y  t BDCWDEF1##<nL4#~fW ?Q?WnQQ4$<D<HL@` 0P * t B0C4DEHFR1 # #0( #(444.(# &(@`j   t B'CDE4F>1  '     @`  z t JB'CDEpFz1'       ' :<@`\ y  t BOCDEF1'#/O @}   t BHCDEF1(H(0.@@ @ K  t BCDE@FJ1 4 W08H_gw]w4wW@"$@` + N    t     t B7CDE8FB1.Qt 77t/Q'./' @`   t BCDEF1 @` '  t BCDEF1 @` '  t BCDEF&``1@`' ( FN  8  t  8 H2 t C 1  H2 t C 13 8 H2 t C 1  H  t C 1a  H !t C 1 n  N s .  "t s .  #t BC#DE$F.ࠀ1  #@`   N s .  $t s . R %t "B7C)DE\Ff17))))))###''// / //77704@`  N s   &t s   't B_CKDEFࠀ1&&?W___W#OGO#O)G.?474747:7@/@(F(@(F KKKFFF@:4)#  /?NP@`s   (t BC DEF1  @   )t BC DEF 1   @   *t BCDEF 1   @   +t BCDE<FF@1   $@`  " ,t B8CDEDFN1 ((0080(( $(@` . " -t B CDEDFN1 $(@`   N s (  .t s (  /t BC#DE$F.ࠀ1  #@` (  N s (  0t s ( R 1t "B8C)DE\Ff18)0)0)0)()() # ##  04@`  N s   2t s   3t BgCKDEFࠀ1&&(# #) .(404040:0@8@8F@@@F@KHKPKWF_F_Fg@g:g4g)g#g_W P@8(NP@`s   4t BC DEF1 @   5t BC DEF 1 @   6t BCDEF 1   @   7t BCDE<FF@1   $@`  " 8t B/CDEDFN1'/'$(@`  " 9t BCDEDFN1$(@` ( F F   :t F   N F   ;t F  Z t B*CDEF@1oo   "**n h]]WK@:.|(l#U(MMM =-  wg WG(84 @KWht (8@GOgwgoowztnnnnnhhntzzz-t=nMhUc\WdQtQ|QQ]cntz@`F W N =  ?t = : @t BGC(DEPFZ`@ 1G(/#'' 7/' ''###((/(G(*,@` At B'CDE(F2`@ 1  ' @`Cj Bt B CDE$F.`@ 1  @`=] Ct BCDE$F.`@ 1   @`E] Dt B/CDE@FJ`@ 1'/'' /   "$@`  N iM  Et iM L Ft B CnDE`Fh1  .:FW]cnnfnGicWL@4#/' 14@Q   N i M  Gt i M N  jG  Ht  jG LN  fG  It  fG H2 Jt C 1 fG N2 Kt S 1, NA H Lt C 1& N0  Mt BCDE$F.1 'W@` j" N i M  Nt i M 2 Ot CɛENGH06=JQQ1 w`T7(ɛw`T7(ɛQ(ɛQi H 2 Pt C.ENG*hHx I`TJ_TQ1 ?.S?.S`T_T?.S`T_Tf M N E  Qt E N  Rt  St B_CDEF@p_?( @# Tt B^CDEF@p'G^ @N ZE  Ut ZE B2 Vt 3 E B2 Wt 3 +ZE  F   Xt 7/r Yt BGjJ? l Zt <jJ? Ll [t <jJ?d N t  \t t  ]t  `4xxaxajJ?  QChange_To_ Extraction_Phase l2 ^t <jJ?t  _t  `xxaxajJ?g   6In  `t  `PxxaxajJ? w  7Out H t 0޽h ?/ OtPt 13  X0(  Xx X c $p-  `   x X c $8   "   H X 0޽h ? 3333   ]U |(  |x | c $x `  x x | c $x p " x x | c $Xux  " x  | c AC:\Program Files\Common Files\Microsoft Shared\Clipart\CagCat50\pe01931_.wmf`p,$D 0 |  ` ?? ,$D0 ? q.Enqueue (x) | T ?" k" ,$D0 Iset phase to extraction  | Tp* ?"z  ,$D0 CRemove_Min (q, x)  | T ?"  ,$D0 ? q.Dequeue (x)  | T  ?",$D0 @c1"   | T ?"" ,$D0 @c2"   | Tc ?"z z ,$D 0 Kc3n,   | T$! ?"  ,$D 0 @c4" J | T8 ?"]c,$D 0 RHow long will it take to perform each operation as a function of n = |m.contents|?SSz @ | @,$D 0 | TH ?"u Acn2" 2 | T jJ?"@ | T  ?"`f,$D 0 Kc1n,  | TӚ ?"@ ` ,$D 0 Xc3n28  H | 0޽h ? 13j   @(  x  c $P"8  `   x  c $*8  p " 8  x  c $x  " 8      `| ?? o,$D0 HInsert_In_Order (q, x)  Td ?" k" ,$D0 Iset phase to extraction  T ?"z  ,$D0 ? q.Dequeue (x)  To ?"  ,$D0 ? q.Dequeue (x)  T ?"f,$D0 Kc1n,   T ?"" ,$D0 @c2"   T  ?"z  ,$D 0 Jc3,   T(^ ?"  ,$D 0 @c3" J  Tta ?"]c,$D 0 RHow long will it take to perform each operation as a function of n = |m.contents|?SSz @  @,$D 0  Tך ?"u Acn2" 2  T jJ?"@  c lAHD:\IMAGES\ANIMALS\WILD\Adx00009.wmf`Y,$D 0  Tۚ ?"`,$D 0 Xc1n28    T ?"@ z` ,$D 0 Kc3n, H  0޽h ? 13  YQ`(  x  c $܏x `  x x  c $x p " x x  c $tx  " x    `W ?? ,$D0 ? q.Enqueue (x)  T ?" k ,$D0 S!q.Sort () set phase to extraction""  T ?"z  ,$D0 ? q.Dequeue (x)  Tp$ ?"  ,$D0 ? q.Dequeue (x)  T' ?",$D0 @c1"   T+ ?"0" ,$D0 Oc2nlogn,   T0 ?"z  ,$D0 Jc3,   T4 ?"  ,$D 0 @c3" J  T8 ?"]c,$D 0 RHow long will it take to perform each operation as a function of n = |m.contents|?SSz @  @00,$D 0  T> ?" ^cnlogn" 2  N jJ?"@  TlB ?"`f,$D 0 Kc1n,   TG ?"@ z` ,$D 0 Kc3n, H  0޽h ? 3333  \0(  \x \ c $;t  `  t  x \ c $(<8   " t  H \ 0޽h ? 3333  bZ `(  `x ` c $Ht  `  t  x ` c $@St   " t  z 0 ` 0 ` @`,$D0B `B  `D8c?"0 ` B `  `D8c?"0  B ` ZD8c?" ` 0 B `B  `D8c?"` 0 B  `  `D8c?"` H ` 0޽h ? 13   S K d{ (  dx d c $ `   x d c $d  "  _F  P  d ppp2 d  `H jJ?" @,$D 0 5x2 d  `؊ jJ?"0 P  5y d TjJ?" * 2 d  `^ jJ?"p0 P  5z  d TjJ?"v*   d  fDR jJ?"   ]+ARE_IN_ORDER (x, y) and ARE_IN_ORDER (x, z),,F  >   d 8 h 2  d  `l48  jJ?" . ,$D 0 5x2  d  ` jJ?" >  5y d TjJ?"P   d  fn jJ?"@ 9`  EARE_IN_ORDER (x, y)H d 0޽h ??`ddddd d d dd 13)  ^)V)11hf&(  hx h c $( `   2 h  ` jJ?",$D 0 6182 h  `p2/  jJ?" 0 ,$D 0 6362 h  `| jJ?"  ,$D 0 6242 h  ` M  jJ?"  6582 h  `HrM  jJ?" @  653 h@ TjJ?"|   h TjJ?"|0   h TjJ?" :   h@ TjJ?" @   h ZjJ?" 2  h  ``vM  jJ?"   6612 h  `yM  jJ?"P p,$D 0 6182 h  `(}M  jJ?"@ ` ,$D 0 6362 h  `@M  jJ?",$D 0 6242 h  `M  jJ?"P p  653 h@ TjJ?"L   h TjJ?"L ` h TjJ?" j 2 h  `M  jJ?"0 P  612 h TjJ?"6 2 h  `|M  jJ?" @ ,$D 0 6182 h  `M  jJ?"@ p` ,$D 0 6362 h  ` M  jJ?"@  ` ,$D 0 6242 h  `lM  jJ?"P p 653 h@ TjJ?" J:  h TjJ?" :  h TjJ?"< J 2 h  `M  jJ?"P `p 661 h TjJ?"< fJ 2  h  `M  jJ?"P 0p 658 !h TjJ?"< *J 2 "h  `tM  jJ?"`,$D 0 6142 #h  `xM  jJ?"p 621 $h TjJ?"2 %h  ` 2 (p Z88 jJ?" 612 z @`  )p  1 ,$D0 2 *p Z5 jJ?"`,$D0 663 2 +p Z5 jJ?" @,$D 0 646 2 ,p Z05 jJ?",$D 0 6182 -p Z5 jJ?"0P 654 .pB TjJ?"\ /p TjJ?"\@ 0p TjJ?"J2 1p Zġ jJ?"0 673 2p TjJ?"2 3p Z jJ?" 637 4p TjJ?"P2 5p Z0  jJ?"@ `  682 6p TjJ?"Z 2 7p Zܴ jJ?" 699 8p TjJ?"02 9p Z̸ 8c?"  @  >  :p T8c?"&  z P ;p  1 ,$D0 2 p Z jJ?"  0 ,$D 0 6632 ?p Z jJ?" @ 654 @pB TjJ?"  Ap TjJ?"   Bp TjJ?"   2 Cp Z\ jJ?" @ 673 Dp TjJ?" p  2 Ep Z jJ?" @ 637 Fp TjJ?"  2 Gp Z jJ?"00 P 682 Hp TjJ?"* *2 Ip Z jJ?"p @ 699 Jp TjJ?"v  2 Kp Z 8c?" 0 P >  Lp T8c?"  ( z   Mp  1 ,$D0 2 Np Z` jJ?"  @ ,$D0 618 2 Op Z jJ?"p@ ` ,$D 0 646 2 Pp Z jJ?"@ ` ,$D 0 6372 Qp Z jJ?"P p 654 RpB TjJ?" J:  Sp TjJ?" :  Tp TjJ?"< J 2 Up Z jJ?"`P p 673 Vp TjJ?"f< J 2 Wp Z8 jJ?"P 0p 663 Xp TjJ?"< *J 2 Yp ZL jJ?"` 682 Zp TjJ?" LZ2 [p Z jJ?"P p 699 \p TjJ?"< J 2 ]p Z 8c?"p` >  ^p T8c?"vLXR _p  ` 8c?"@,$D0R `p  ` 8c?"" r ,$D0H p 0޽h ?ppppp ppp pp p p pppppppppppp 'ppp 'ppp ppp ppp pp p!pp"pp#p$pp%p&p*p+p.p*p,p/p-p+p0p+p1p2p3p,p4p5p-p6p,p7p8ppAp?p=pBp=pCpDpEp>pFpGp?pHp>pIpJpNpOpRp NpPpSp!QpOpTp"OpUpVp#WpPpXp$YpQpZp%Pp[p\p&-p9p:p'Qp]p^p(?pKpLp 13  6(  x  c $! `   ~   f$ jJ?"PR Zprocedure Sift_Root_Down ( alters  binary tree t ); /*! requires [t is a complete tree and both left and right subtrees of t are heaps] ensures [t is a heap and t contains exactly the items in #t] !*/d. ( vVH  0޽h ? 13  !     (  x  c $k `      f  jJ?"P  6procedure Heapify ( alters  binary tree t ); /*! requires [t is a complete tree] ensures [t is a heap and t contains exactly the items in #t] !*/d ( +V7z     ,$D0T p #   ZjJ?"^ G    ZjJ?"  R   f 8c?"pR    f 8c?"` AR    f 8c?" ~A2    ` jJ?"h  ,$D 0 >     f@ jJ?"$ 9Hint:H  0޽h ?/@     13  [S0(  x  c $ `      fC jJ?"1  procedure_body Heapify ( alters  binary tree t ) { }@H!   `8J ??\,$D0  if (|t| > 1) { Heapify (left subtree of t) Heapify (right subtree of t) Sift _Root_Down (t) }<{H  0޽h ? 13T>  >=@DDL<(  x  c $kt  `  t  2  Z$jJ?" 0,$D0 6122  ZֆjJ?"P`p,$D 0 6462  Z_jJ?"Pp p,$D 0 6182  ZPcjJ?"` 0  654 @ TjJ?" J  TjJ?"  J   TjJ?"LZ 2   ZfjJ?"`   673   TjJ?"LV@Z 2   ZjjJ?"` @  637   TjJ?"L Z 2  ZnjJ?"p   682  TjJ?"\ P:j 2  Z8pjJ?"p `  663  TjJ?"\ j 2  Z0tjJ?"`  699  TjJ?"Lf P Z H   fx jJ?"} pLet s number the tree positions (top-bottom, left-right)99   f{ jJ?" ,$D0 =(1)   fp jJ?"P^J,$D0 =(2)   f jJ?"P6 J,$D0 =(3)   f jJ?"` )Z ,$D0 =(4)   f jJ?"` Z ,$D0 =(5)   f jJ?"` ? Z ,$D0 =(6)   f jJ?"` Z ,$D 0 =(7)   f jJ?"p 3j ,$D 0 =(9)   f jJ?"p j ,$D 0 =(8)z } `   }`,$D  08   fx jJ?"} P ,$D  0 X$Which array corresponds to the tree?%%&N @     ` ! Z jJ?"@ B "  `DjJ?"@@ B #  `DjJ?" B $  `DjJ?"@@ B %  `DjJ?"  B &  `DjJ?"@ @ B '  `DjJ?"  B (  `DjJ?"@@ B )  `DjJ?"  *  fĠ jJ?"ke,$D0 ;1 +  fT jJ?"`S)Z,$D0 ;2 ,  fħ jJ?"`Z,$D0 ;3 -  fT jJ?"`S ) Z,$D0 ;4 .  f" jJ?"` Z,$D0 ;5 /  f豎 jJ?"`S ) Z,$D0 ;6 0  fP jJ?"` Z,$D0 ;7 1  fd jJ?"`S)Z,$D0 ;8 2  f jJ?"`Z,$D0 ;9 3  fd jJ?"0,$D0 612 4  fŽ jJ?"p0,$D0 646 5  fdƎ jJ?"0,$D0 618 6  fɎ jJ?"" 0,$D0 654 7  fd͎ jJ?" 0,$D0 673 8  fЎ jJ?" p 0,$D0 637 9  fdԎ jJ?" 0,$D0 699 :  f׎ jJ?"p0,$D0 682 ;  fdێ jJ?"0,$D0 663z  P  < P  ,$D 0 2 = ZߎjJ?"[P{p,$D 0 5x2 > ZjJ?" ` +  5y ? TjJ?"LZ 2 @ Z$jJ?"`   5z A TjJ?"QL;Z  B  f jJ?"P<SJ,$D!0 =(i) C  f| jJ?"` Z ,$D"0 >(2i) D  f  jJ?"` Z ,$D#0 @(2i+1)H  0޽h ?@      >=? =@A 13  P0(  x  c $| `   x  c $8  "  H  0޽h ? 13  `0(  x  c $ `  t  x  c $Ñ  "  H  0޽h ? 13  pP(  r  S pt  `  t    S t  "<$0 t  H  0޽h ? 13  \(  x  c $x^ P`     c $藃  "<$0  H  0޽h ? 13  \(  x  c $8 P`     c $  "<$0  H  0޽h ? 13%  >%6% 99$(  ~  s *5  `  5  F 1   V)"   f p??I    fT5  8c??1  KSorting_Machine_ Type   `T"5  ?? E  7extB  # lDjJ??@ @ B  # lDjJ??@ @     `X&5  ?? !  5iF 1    V)"    f p??2     fP*5  p??1 u MSorting_Machine_ KernelF 1      V)    ` p??2     f@/5  p??1   OSorting_Machine_ Kernel_2F PB  p"   f p??P@   f|35  p??PB DRepresentationF P@  p "   f p??P@   f75  p??m# B Array_Kernel    NjJ?"    NjJ?"    NjJ?"  B @ # lDjJ??P @pB @ # lDjJ??P 0 0 pB  # lDjJ??P pppB @ # lDjJ?? p B @ # lDjJ?? 0 B  # lDjJ??    `p>5  ??   5u    `B5  ??  5u !  `LE5  ??p j  7enc "  `H5  ??  5i #  `(L5  ??v 0 p 5i $  `O5  ??l pf 5iF P@ % p " &  f p??P@ '  f8S5  p??[8 B Queue_Kernel  F    (  0" )  f p??   *  fW5  p??*   HArray_ Exchange_AtF   +   " ,  f p??  -  f[5  p??  LArray_ Are_In_Order_AtF  p  .  p " /  `p?? _  0  f_5  p?? pu  KGeneral_ Are_In_Order 1 NjJ?"P `P B 2 3 rZDjJ?? p` B 3 3 rZDjJ?? P@  4  `d5  ?? A  5i 5  `h5  ?? G  5uB 6 # lDjJ??  B 7 # lDjJ??p p  8  `|l5  ??p (j  5i 9  ` p5  ?? D  5iH  0޽h ? 13J0   (   d  c $   M   3 r / ^_^_ @  M  <(Quick overview of Sorting Machine operation Point out that it is a  2-phased machine so that you start in insertion phase, put in all the items, then change to extraction phase, and finally get the items out in order Also, SM is a template and can sort any items in any orderH  0޽h ? ̙330 PHf(  HX H C    5  H S /  @  5  hTWe assume students have already seen the client view of SM in 222, but a quick review won t hurt (plus unless they have taken 222 last fall, they would have not seen yet)H H 0޽h ? ̙33x0 80L(  LX L C    0 L S 5  @   What s a multiset? I got rid of the slide, but we should still go over it. :H L 0޽h ? ̙33L0  P(  PX P C     P S x#  @   These are the algorithms we want to mention They should have already seen some form of selection sort in 222 Insertion sort can probably be a homework Mergesort Quicksort they ll do in closed lab 1 Heapsort they ll do in lab 1 We talk about tree sort after binary search trees I d demo the first four algorithms using the stacking cups and trying to lead students to each algorithm by suggesting first step The point here is for students to see that we can sort in very different ways, not to completely grasp the algorithms6,,, >H P 0޽h ? ̙33 0 xB(  xd xc $    x3 rux^_^_ @   Let s pick a representation. We need to represent the phase and the contents. A Boolean for the phase seems ok. We can pick pretty much any container for the contents, say a Queue of Item. Why not Set? Let s look at various options& H x 0޽h ? ̙332 0 0(  d c $    3 rx^_^_ @   $Here the idea is put off as much as possible doing the actual work At each step you want to do as little as possible Which sorting algorithm does this remind you of? (selection sort) How long is it going to take for each operation as a function of n (the size of the SM)? H  0޽h ? ̙330 PA(  d c $   8  3 rx^_^_ @  8  Here the idea is to do the work as soon as possible Which sorting algorithm does this remind you of? (insertion sort) How long is it going to take for each operation as a function of n (the size of the SM)? H  0޽h ? ̙330 pP(  d c $    3 r()8 ^_^_ @   Procrastination did work in Remove_First, eager beaver did work in Insert. Where else could we sort? (in Change_To_Extraction_Phase) How long is it going to take for each operation as a function of n (the size of the SM)? H  0޽h ? ̙3340 (  d c $   5  3 r/ ^_^_ @  5  &Activity (3-5 min)H  0޽h ? ̙3320  (  ^ S    5  c $&/  @  5  xBActivity: students implement Quicksort using Partition and Combine H  0޽h ? ̙33n0 .&(  ^ S      c $z  @   We can ask students to implement Remove_Min and then explain in English how they would use that to sort a queue (or maybe we can skip the implementation of Remove_Min they might have done that already in 222)H  0޽h ? ̙3320 (  ^ S      c $h$  @    xBActivity: students implement Quicksort using Partition and Combine H  0޽h ? ̙330 A(  ^ S     c $l  @   7#HW#2: implementing Insert_In_Order.H  0޽h ? ̙3320 (  ^ S     c $  @   xBActivity: students implement Quicksort using Partition and Combine H  0޽h ? ̙330  (   ^  S    z  c $  @   Go over Quicksort algorithm again and motivate Partition and Combine Get students to explain the specs for Partition Note difference from HW#1: Queue_Of_Item instead of Queue_Of_Integer and ARE_IN_ORDER instead of <= H   0޽h ? ̙330  K(  ^ S     c $  @   A-Get students to explain the specs for CombineH  0޽h ? ̙33>0 @$(  $^ $S      $c $\\  @    pGo over definition only if students think it s necessaryH $ 0޽h ? ̙3320 @,(  ,^ ,S     ,c $Xe{ @   xBActivity: students implement Quicksort using Partition and Combine H , 0޽h ? ̙330 zr`4 (  4^ 4S    l 4c $$y @   Discuss code for Partition: Note that HW1 used queues of Integer and <=, but for closed lab and lab they ll have to use utility class Item_Are_In_Order and the operation Are_In_Order q1 and q2 must be cleared to be produced&H 4 0޽h ? ̙330 <6(  <^ <S     <c $  @   ,Discuss code for CombineH < 0޽h ? ̙33/0 D(  D^ DS     Dc $X  @   uaGo over Merge sort again and motivate Split and Merge Get students to explain the specs for SplitH D 0޽h ? ̙330 L(  L^ LS     Lc $0 8  @   Get students to explain the specs for Merge Ask students to write the Sort procedure that implements mergesort for a queue using Split and Merge (we should then add one slide with the specs for Sort and space for the body).e qH L 0޽h ? ̙3320 T(  T^ TS    8  Tc $P 8  @  8  xBActivity: students implement Quicksort using Partition and Combine H T 0޽h ? ̙33&0 tT(  t^ tS     tc $! @   J6First, which item will have to be removed? (root) Is this always the case? Why? Now let s first fix the shape property. How can we do that by just moving one item? (63 rightmost leaf on bottom level to root) Will this always work? Why? What do we know about the two subtrees of the new root? (they are heaps!) Will this always be the case? Why? So we know that the only item that breaks the ordering property is the root. How can we move it to its proper place while at the same time not breaking the ordering property in other places? (sift down) Look at the root and its two children. Which of the three should be at the root? (18--the smallest of the three) Why don t we just swap the root and the smaller of the children (only if the smaller of the children is smaller than the root itself).H t 0޽h ? ̙33.0  .(  ^ S     c $ @   $Activity (5 min)H  0޽h ? ̙3340 (  d c $   5 y 3 r/ N_N_ @  5  After talking about multisets, go back to previous slide and discuss alternative models, e.g., why not use set or string for the contents mH  0޽h ? ̙3350 ld`(  d c $   X 3 r̒ !e!e @   Go over definition (this is not a function definition it s a restriction on a function: it tells what properties our actual AIO function must satisfy to be legal) Go back to previous slide and ask where items = to the partitioning element should go; point out that they go in q1 because of first property (reflexivity) of AIOH  0޽h ? ̙33  xp^RЀ3ÿ lHbP  LPÄ!1 4axĐ% y@( XyTxeH!]/ܮκa) 9 $ى C>@2ݑĐEB@Ae OR gCo`ǐL2C of1<0s"yR$,/$|3Js2 JsrR*)_*8*&ٯ32:'3d敤%(xX!/O- JZ8+e[%C$3;g30(RPo|qR#x8:9^hpP. 7?@5rm@6 ׺3D  @P@1._6! 9eZ`ϐB~`ANO; ~jl?%  xp^RЀ3ÿ lHbP  LPÄ!1 4axĐ% y@( XyTxeH!]/ܮκa) 9 $ى C>@2ݑĐEB@Ae OR gCo`ǐL2C of1<0s"yR$,/$|3Js2 JsrR*)_*8*&ٯ32:'3d敤%(xX!/O- JZ8+e[%C$3;g30(RP uCsG' 7c9c|HZM@(Z{t>PV9(#]*(f`k&7g?eZ`ϐB~`ANO 8N$H`(B  xp^RЀ3ÿ lHbP  LPÄ!1 4axĐ% y@( XyTxeH!]/ܮκa) 9 $ى C>@2ݑĐEB@Ae OR gCo`ǐL2C of1<0s"yR$,/$|3Js2 JsrR*)_*8*&ٯ32:'3d敤%(xX!/O- JZ8+e[%C$3;g30(RP uCsG' 7c9c|HZM@(Z{t>PV9(#]*(f`k&7g?eZ`ϐB~`ANO 8N$H`(Br\0O^h*<n x}y@ӊq },BSSeŖ:p6qi[SJBB:4@vw}a%S?VXp S]#&lhVdg@Zlp\^`ye3 NrN( Oh+'0U hp   , 8 DPXRemember Sorting_Machine?i Paolo Bucci9C:\WINDOWS\Application Data\Microsoft\Templates\321B.pots Paolo Bucci37lMicrosoft PowerPointn D@DiJ@QlW@gGSg  )'    """)))UUUMMMBBB999|PP3f333f3333f3ffffff3f̙3ff333f333333333f33333333f33f3ff3f3f3f3333f33̙33333f333333f3333f3ffffff3f33ff3f3f3f3fff3ffffffffff3ffff̙fff3fffff3fff333f3f3ff3ff33f̙̙3̙ff̙̙̙3f̙3f333f3333f3ffffff3f̙3f3f3f333f3333f3ffffff3f̙3f3ffffffffff!___www4'A x(xKʦ """)))UUUMMMBBB999|PP3f3333f333ff3fffff3f3f̙f3333f3333333333f3333333f3f33ff3f3f3f3333f3333333f3̙33333f333ff3ffffff3f33f3ff3f3f3ffff3fffffffff3fffffff3f̙ffff3ff333f3ff33fff33f3ff̙3f3f3333f333ff3fffff̙̙3̙f̙̙̙3f̙3f3f3333f333ff3fffff3f3f̙3ffffffffff!___wwwCtttttttttttttttttttttttttttttttttttttttt+$ttt$$ttt$+t$$$$*$$$$*$*$$Root EntrydO)gTPicturesICurrent UserASummaryInformation(8U  !#_!4 *Paolo BucciPaolo Buccig Servicese՜.+,0    $ On-screen ShowThe Ohio State UniversityeE4+{ 2Times New RomanComic Sans MRoot EntrydO)2mOPicturesICurrent User/SummaryInformation(8U  !_!4"buccibucciolo Buccig Servicese՜.+,0    $ On-screen ShowThe Ohio State UniversityeE4+{ 2Times New RomanComic Sans M  62Microsoft ClipArt Gallery $MS_ClipArt_Gallery02Microsoft ClipArt Gallery2Microsoft ClipArt Gallery $MS_ClipArt_Gallery02Microsoft ClipArt Gallery2Microsoft ClipArt Gallery $MS_ClipArt_Gallery02Microsoft ClipArt GalleryJ/ 0|DTimes New Roman0:A 0DComic Sans MSn0:A 0?B DTahomaans MSn0:A 00DWingdings MSn0:A 0@DSymbolgs MSn0:A 0 C.  @n?" dd@  @@`` xpqIP   1a)/57  "#%&'()*+,-.189 +%2#Root EntrydO) gPicturesICurrent UserASummaryInformation(8U  !#_!4 Paolo BucciPaolo Buccig Servicese՜.+,0    $ On-screen ShowThe Ohio State UniversityeE4+{ 2Times New RomanComic Sans M  !"#$&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~a? CDEF HI:  O2$&y2=~X 2$ ;]Iפ5Ì71X 2$r ]hpf*i:V2$hecsq`1, 0e0e A@A5%8c8c     ?1d0u0@Ty2 NP'p<PowerPoint Document(%E4DocumentSummaryInformation8'p@A)BCD|E?@8*FlO ʚ;Sk8ʚ; g4hdhd :A 0ppp@ <4!d!dL$ 0d<4ddddL$ 0d<4BdBdL$ 0d$g4EdEd :A 0"p@ pp80___PPT10 ? %O =; Remember Sorting_Machine? 4Sorting_Machine Continued&  4Sorting_Machine Continued& VType ( inserting: boolean contents: multiset of Item ) Initial value (true, {}) d8 8 $,%o4A Math Type: Multiset Multisets are just like sets except that duplicates are allowed In set theory: {2, 18, 2, 36} = {2, 18, 36} and |{2, 18, 2, 36}| = 3 In multiset theory: {2, 18, 2, 36} /= {2, 18, 36} and |{2, 18, 2, 36}| = 4 BZ :BA$ A 4Sorting_Machine Continued& Operations m.Insert (x) m.Change_To_Extraction_Phase ( ) m.Remove_First (x) m.Remove_Any (x) m.Is_In_Extraction_Phase ( ) m.Size ( )2 z y   Sorting AlgorithmsSelection Sort Insertion Sort Mergesort Quicksort Heapsort Tree Sort & >   :A Sort Procedureprocedure Sort ( alters Queue_Of_Item& q ); /*! ensures q is permutation of #q and IS_ORDERED (q) !*/z )#CMath Definitionmath definition IS_ORDERED ( s: string of Item ): boolean is for all u, v: Item where ( * is substring of s) (ARE_IN_ORDER (u, v))    ">ip5An Old Math DefinitionWmath definition ARE_IN_ORDER ( x: Item, y: Item ): boolean satisfies restriction for all x, y, z: Item (ARE_IN_ORDER (x, x) and (ARE_IN_ORDER (x, y) or ARE_IN_ORDER (y, x)) and (if (ARE_IN_ORDER (x, y) and ARE_IN_ORDER (y, z)) then ARE_IN_ORDER (x, z)))X8  1#%G <Selection SortIprocedure Remove_Min ( alters Queue_Of_Item& q, produces Item& x ); /*! requires q /= empty_string ensures (q * ) is permutation of #q and for all y: Item where (y is in elements (q)) (ARE_IN_ORDER (x, y)) !*/JZ     4=6Selection Sort: You Give It A TryAprocedure Sort ( alters Queue_Of_Item& q ) { }:BZ #>Insertion Sortprocedure Insert_In_Order ( alters Queue_Of_Item& q, consumes Item& x ); /*! requires IS_ORDERED (q) ensures q is permutation of (#q * <#x>) and IS_ORDERED (q) !*/   #?6Insertion Sort: You Give It A Try@procedure Sort ( alters Queue_Of_Item& q ) { }8A "@ Quicksort procedure Partition ( consumes Queue_Of_Item& q, preserves Item& p, produces Queue_Of_Item& q1, produces Queue_Of_Item& q2 ); /*! ensures q1 * q2 is permutation of #q and for all x: Item where (x is in elements (q1)) (ARE_IN_ORDER (x, p)) and for all x: Item where (x is in elements (q2)) (not ARE_IN_ORDER (x, p)) !*/xZ  *  .  B(Quicksort Continued&   procedure Combine ( produces Queue_Of_Item& q, consumes Item& p, consumes Queue_Of_Item& q1, consumes Queue_Of_Item& q2 ); /*! ensures q = #q1 * <#p> * #q2 !*/ *)DQuicksort: You Give It A Try Cprocedure Sort ( alters Queue_Of_Item& q ) { }8D %E(Quicksort Continued&   procedure Partition ( consumes Queue_Of_Item& q, preserves Item& p, produces Queue_Of_Item& q1, produces Queue_Of_Item& q2 ) { }|Z  'F(Quicksort Continued&   procedure Combine ( produces Queue_Of_Item& q, consumes Item& p, consumes Queue_Of_Item& q1, consumes Queue_Of_Item& q2 ) { }z %G Mergesort procedure Split ( consumes Queue_Of_Item& q, produces Queue_Of_Item& q1, produces Queue_Of_Item& q2 ); /*! ensures q1 * q2 is permutation of #q and |q2| <= |q1| <= |q2| + 1 !*/ Z *-H(Mergesort Continued&   /procedure Merge ( consumes Queue_Of_Item& q1, consumes Queue_Of_Item& q2, produces Queue_Of_Item& q ); /*! requires IS_ORDERED (q1) and IS_ORDERED (q2) ensures q is permutation of #q1 * #q2 and IS_ORDERED (q) !*/ 0Z )  #IMergesort: You Give It A Try @procedure Sort ( alters Queue_Of_Item& q ) { }8A "! Sorting_Machine: Inside StoryJ .Inside Story Continued& As an example, assume the representation for Sorting_Machine has two fields: contents_rep of type Queue_Of_Item inserting_rep of type Boolean What are some possible implementations?RMA(M  (" ^Let s Procrastinate  the Students Choice_operation m.Insert (x) m.Change_To_ Extraction_Phase () m.Remove_First (x) m.Remove_Any (x)Z Z  F$ V  what happens? #How About Eager Beavers_operation m.Insert (x) m.Change_To_ Extraction_Phase () m.Remove_First (x) m.Remove_Any (x)Z Z  F$ V  what happens? $Are There Other Possibilities?_operation m.Insert (x) m.Change_To_ Extraction_Phase () m.Remove_First (x) m.Remove_Any (x)Z Z  F$ V  what happens? K!A Heapsort ImplementationAn ARE_IN_ORDER Heap is a special kind of binary tree: shape property: the tree is complete ordering property: for each item x in the tree, ARE_IN_ORDER (x, child) holds for each child of xD77QL"Complete Binary Trees^All levels of the tree are completely filled up except possibly the bottom level. Any  holes in the bottom level must appear to the right of all existing items at that level.M#Heap Ordering PropertyFor each item x in the tree: N$ExamplesO%HeapsortBuild an ARE_IN_ORDER heap with the items to be sorted using the specified ARE_IN_ORDER Implement Remove_First so that, after removing the first item in the ordering from the heap, it restores the heap properties P&How Will Remove_First Work?g-Sift _Root _Downh.>Turning a Complete Tree Into a HeapS)tTurning a Complete Tree Into a Heap Continued& T*;Mapping Complete Binary Tree Positions Into Array LocationsU+Remember Array Operations?Za.Set_Bounds (lower, upper) a[i] --accessor operation a.Lower_Bound () a.Upper_Bound ()V,Insertion-Phase Container?{What is the effect of a.Set_Bounds (lower, upper)? At what point will the Sorting_Machine be ready to set the array bounds?j/5Swapping/Comparing Two Elements in an ArrayFGiven: object Array_Of_Item a; object Integer i, j; What s wrong with: a[i] &= a[j] and Item_Are_In_Order::Are_In_Order (a[i], a[j])? They violate the repeated argument rule a[i] and a[j] are references to parts of a s representation: the parts could be the same (see Partial_Map_Kernel_3)IZ?ZZ ,:  %Hl1Swapping Two Array ElementsvUse a.Exchange_At (i, j) instead of a[i] &= a[j] Exchange_At is an Array extension It requires that a.lb i, j a.ub See AT/Array/Exchange_At.h in the RESOLVE_Catalog for complete specs  3ErFm2Comparing Two Array ElementsUse a.Are_In_Order_At (i, j) instead of Item_Are_In_Order::Are_In_Order (a[i], a[j]) Are_In_Order_At is an Array extension It requires that a.lb i, j a.ub See AT/Array/Are_In_Order_At.h in the RESOLVE_Catalog for complete specs  -7KKn39Sorting_Machine_Kernel_2: Component Coupling Diagram/% & ' ();WXYZ[]^_`abcdei!q"r#  0 H(   x   c $! `      <U   P p  H   0޽h ? 3333 # P0(  x  c $L1 `   x  c $ 2 P  H  0޽h ? 3333rC/p 25m4r888888YYu888888Yzyģ888XY__888YutϨ888Yyuá888YYáá888Yytááááááááááááááááááááááááááááááááƅƣġááááááááááááááááááááááááááááááááááááá_ţġáááááááááááááááááááááááááááááááááááƅƤġáááááááááááááááááááááááááááááááááááááƅƤţġáááááááááááááááááááááááááƅġáááááááááƅƣġááááááááááƅġƅƣġSTahoma WingdingsSymbol321BMicrosoft ClipArt GalleryRemember Sorting_Machine?Sorting_Machine ContinuedSorting_Machine ContinuedA Math Type: MultisetSorting_Machine ContinuedSorting With Sorting_MachineSorting AlgorithmsA Sort ProcedureMath DefinitionAn Old Math DefinitionSelection Sort7Selection Sort: You Give It A TryInsertion Sort7Insertion Sort: You Give It A Try QuicksortQuicksort ContinuedQuicksort: You Give It A TryQuicksort ContinuedQuicksort Continued MergesortMergesort ContinuedMergesort: You Give It A TrySorting_Machine: Inside StoryInside Story Continued0Lets Procrastinate the Students ChoiceHow About Eager BeaversAre There Other Possibilities?A Heapsort ImplementationComplete Binary TreesHeap Ordering Property Examples HeapsortHow Will Remove_First Work?Sift _Root _Down?Turning a Complete Tree Into a Heap;Turning a Complete Tree Into a Heap Continued<Mapping Complete Binary Tree Positions Into Array LocationsRemember Array Operations?Insertion-Phase Container?6Swapping/Comparing Two Elements in an ArraySwapping Two Array ElementsComparing Two Array Elements:Sorting_Machine_Kernel_2: Component Coupling Diagram  Fonts UsedDesign TemplateEmbedded OLE Servers Slide Titles+