Mercurial > cgi-bin > hgwebdir.cgi > POP > oldRepo
diff 3__Intelligence_gathering/Bitonic_Sort.mht @ 0:a8cd65eca9a9
Initial add
| author | Me@portablequad |
|---|---|
| date | Sun, 25 Dec 2011 14:39:36 -0800 |
| parents | |
| children |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/3__Intelligence_gathering/Bitonic_Sort.mht Sun Dec 25 14:39:36 2011 -0800 1.3 @@ -0,0 +1,423 @@ 1.4 +From: <Saved by Microsoft Internet Explorer 5> 1.5 +Subject: Bitonic Sort 1.6 +Date: Mon, 4 Jun 2007 10:57:06 -0700 1.7 +MIME-Version: 1.0 1.8 +Content-Type: text/html; 1.9 + charset="Windows-1252" 1.10 +Content-Transfer-Encoding: quoted-printable 1.11 +Content-Location: http://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htm 1.12 +X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2962 1.13 + 1.14 +<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> 1.15 +<HTML><HEAD><TITLE>Bitonic Sort</TITLE> 1.16 +<META http-equiv=3DContent-Type content=3D"text/html; = 1.17 +charset=3Dwindows-1252"> 1.18 +<META content=3D"MSHTML 6.00.2900.2963" name=3DGENERATOR></HEAD> 1.19 +<BODY text=3D#000000 vLink=3D#6699cc aLink=3D#ff3300 link=3D#3333cc = 1.20 +bgColor=3D#ffcc99> 1.21 +<H1 align=3Dcenter>Bitonic Sort</H1> 1.22 +<P align=3Dcenter>Abstract</P> 1.23 +<BLOCKQUOTE> 1.24 + <BLOCKQUOTE> 1.25 + <BLOCKQUOTE> 1.26 + <BLOCKQUOTE> 1.27 + <P align=3Dleft>Continuing a tutorial on sorting algorithms, = 1.28 +this page=20 1.29 + animates bitonic = 1.30 +sort.</P></BLOCKQUOTE></BLOCKQUOTE></BLOCKQUOTE></BLOCKQUOTE> 1.31 +<P align=3Dcenter>Author<BR>Thomas W. Christopher<BR></P> 1.32 +<P>Bitonic sort is a sorting algorithm designed specially for parallel=20 1.33 +machines.</P> 1.34 +<P>A sorted sequence is a monotonically non-decreasing (or = 1.35 +non-increasing)=20 1.36 +sequence. A bitonic sequence is composed of two subsequences, one = 1.37 +monotonically=20 1.38 +non-decreasing and the other monotonically non-increasing. A "V" and an = 1.39 +A-frame=20 1.40 +are examples of bitonic sequences.</P> 1.41 +<P>I get tired of saying "non-decreasing" and "non-increasing." They are = 1.42 +clunky=20 1.43 +and throw an extra negative into sentences. I will use "ascending" to = 1.44 +mean=20 1.45 +"non-decreasing" and "descending" to mean "non-increasing."</P> 1.46 +<P>Moreover, any rotation of a bitonic sequence is a bitonic sequence, = 1.47 +or if you=20 1.48 +prefer, one of the subsequences can wrap around the end of the bitonic=20 1.49 +sequence.</P> 1.50 +<P>Of course, a sorted sequence is itself a bitonic sequence: one of the = 1.51 + 1.52 +subsequences is empty.</P> 1.53 +<P>Now we come to a strange property of bitoinic sequences, the property = 1.54 +that is=20 1.55 +uses in bitonic sort: </P> 1.56 +<BLOCKQUOTE> 1.57 + <P>Suppose you have a bitonic sequence of length 2n, that is, elements = 1.58 +in=20 1.59 + positions [0,2n). You can easily divide it into two halves, [0,n) and = 1.60 +[n,2n),=20 1.61 + such that 1.62 + <UL> 1.63 + <LI>each half is a bitonic sequence, and=20 1.64 + <LI>every element in half [0,n) is less than or equal to each = 1.65 +element in=20 1.66 + [n,2n). (Or greater than or equal to, of course.) = 1.67 +</LI></UL></BLOCKQUOTE> 1.68 +<P>What is this easy method? Simply compare elements in the = 1.69 +corresponding=20 1.70 +positions in the two halves and exchange them if they are out of = 1.71 +order.</P> 1.72 +<BLOCKQUOTE> 1.73 + <P> for (i=3D0;i<n;i++)=20 1.74 + {<BR> if = 1.75 +(get(i)>get(i+n))=20 1.76 + exchange(i,i+n);<BR> }</P></BLOCKQUOTE> 1.77 +<P>This is sometimes called a bitonic merge.</P> 1.78 +<P>Why does it work? I'm not sure I could do a concise and clear enough = 1.79 +proof to=20 1.80 +fit in with these pages. Let's just leave it without a proof, but = 1.81 +true.</P> 1.82 +<P>So here's how we do a bitonic sort:=20 1.83 +<UL> 1.84 + <LI>We sort only sequences a power of two in length, so we can always = 1.85 +divide a=20 1.86 + subsequence of mnore than one element into two halves.=20 1.87 + <LI>We sort the lower half into ascending (=3Dnon-decreasing, = 1.88 +remember) order=20 1.89 + and the upper half into descending order. This gives us a bitonic = 1.90 +sequence.=20 1.91 + <LI>We perform a bitonic merge on the sequence, which gives us a = 1.92 +bitonic=20 1.93 + sequence in each half and all the larger elements in the upper half.=20 1.94 + <LI>We recursively bitonically merge each half until all the elements = 1.95 +are=20 1.96 + sorted. </LI></UL> 1.97 +<P><APPLET height=3D200 archive=3Dsorts3.jar width=3D400 align=3Dleft=20 1.98 +code=3Dcom.toolsofcomputing.SortApplets.BitonicSort.class> 1.99 +Bitonic Sort</APPLET> <B>Bitonic Sort</B> This first version actually = 1.100 +uses=20 1.101 +recursion. It uses methods sortup, sortdown, mergeup, and mergedown, to = 1.102 +sort=20 1.103 +into ascending order or descending order and to recursively merge into = 1.104 +ascending=20 1.105 +or descending order.</P> 1.106 +<P>Method <EM>void sortup(int m, int n)</EM> will sort the n elements in = 1.107 +the=20 1.108 +range [m,m+n) into ascending order. It uses method <EM>void mergeup(int = 1.109 +m, int=20 1.110 +n)</EM> to merge the n elements in the subsequence [m,m+n) into = 1.111 +ascending order.=20 1.112 +Similarly for <EM>void sortdown(int m, int n)</EM> and <EM>void = 1.113 +mergedown(int m,=20 1.114 +int n)</EM>.</P> 1.115 +<P>The overall sort is performed by a call:</P> 1.116 +<BLOCKQUOTE> 1.117 + <P> sortup(0,N);</P></BLOCKQUOTE> 1.118 +<P>Both sortup and sortdown recursively sort each half to produce an = 1.119 +A-frame=20 1.120 +shape and then recursively merge that into an ascending or descending=20 1.121 +sequence.</P> 1.122 +<BLOCKQUOTE> 1.123 + <P>void sortup(int m, int n) {//from m to m+n<BR> if = 1.124 +(n=3D=3D1)=20 1.125 + return;<BR> sortup(m,n/2);<BR> =20 1.126 + sortdown(m+n/2,n/2);<BR> = 1.127 +mergeup(m,n/2);<BR>}<BR>void=20 1.128 + sortdown(int m, int n) {//from m to m+n<BR> if = 1.129 +(n=3D=3D1)=20 1.130 + return;<BR> sortup(m,n/2);<BR> =20 1.131 + sortdown(m+n/2,n/2);<BR> =20 1.132 +mergedown(m,n/2);<BR>}</P></BLOCKQUOTE> 1.133 +<P>Methods mergeup and mergedown are fairly straightfoward. They compare = 1.134 + 1.135 +elements in the two halves, exchange them if they are out of order, and=20 1.136 +recursively merge the two halves. Call mergeup( m, n) sorts into = 1.137 +ascending=20 1.138 +order the 2*n elements in the range [m,2n).</P> 1.139 +<BLOCKQUOTE> 1.140 + <P>void mergeup(int m, int n) {<BR> if (n=3D=3D0)=20 1.141 + return;<BR> int i;<BR> for=20 1.142 + (i=3D0;i<n;i++) {<BR> if=20 1.143 + (get(m+i)>get(m+i+n)) exchange(m+i,m+i+n);<BR> =20 1.144 + }<BR> mergeup(m,n/2);<BR> =20 1.145 + mergeup(m+n,n/2);<BR>}<BR>void mergedown(int m, int n) = 1.146 +{<BR> =20 1.147 + if (n=3D=3D0) return;<BR> int = 1.148 +i;<BR> for=20 1.149 + (i=3D0;i<n;i++) {<BR> if=20 1.150 + (get(m+i)<get(m+i+n)) exchange(m+i,m+i+n);<BR> =20 1.151 + }<BR> mergedown(m,n/2);<BR> =20 1.152 + mergedown(m+n,n/2);<BR>}</P></BLOCKQUOTE> 1.153 +<P> </P> 1.154 +<P><APPLET height=3D200 archive=3Dsorts3.jar width=3D400 align=3Dleft=20 1.155 +code=3Dcom.toolsofcomputing.SortApplets.BitonicSort2.class> 1.156 +Bitonic Sort2</APPLET> <B>Bitonic Sort2</B> Bitonic sort is perfect for=20 1.157 +parallelization. The recursive calls of merge can be done in parallel. = 1.158 +The loops=20 1.159 +in the merges, comparing and conditionally exchanging elements (m+i) and = 1.160 +(m+i+n)=20 1.161 +can also be run in parallel.</P> 1.162 +<P>However, getting it to run efficiently in parallel requires turning = 1.163 +the=20 1.164 +algorithm upside down. The algorithm is expressed in terms of recursive = 1.165 +calls.=20 1.166 +What we need is an algorithm in terms of each individual element.</P> 1.167 +<P>Let's examine what the elements are doing. We will use an = 1.168 +eight-element array=20 1.169 +and identify the elements by their positions in binary.</P> 1.170 +<BLOCKQUOTE> 1.171 + <DIV align=3Dleft> 1.172 + <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 = 1.173 +border=3D1> 1.174 + <TBODY> 1.175 + <TR> 1.176 + <TD>index</TD> 1.177 + <TD align=3Dmiddle>0</TD> 1.178 + <TD align=3Dmiddle>1</TD> 1.179 + <TD align=3Dmiddle>2</TD> 1.180 + <TD align=3Dmiddle>3</TD> 1.181 + <TD align=3Dmiddle>4</TD> 1.182 + <TD align=3Dmiddle>5</TD> 1.183 + <TD align=3Dmiddle>6</TD> 1.184 + <TD align=3Dmiddle>7</TD></TR> 1.185 + <TR> 1.186 + <TD>in binary</TD> 1.187 + <TD align=3Dmiddle>0000</TD> 1.188 + <TD align=3Dmiddle>0001</TD> 1.189 + <TD align=3Dmiddle>0010</TD> 1.190 + <TD align=3Dmiddle>0011</TD> 1.191 + <TD align=3Dmiddle>0100</TD> 1.192 + <TD align=3Dmiddle>0101</TD> 1.193 + <TD align=3Dmiddle>0110</TD> 1.194 + <TD = 1.195 +align=3Dmiddle>0111</TD></TR></TBODY></TABLE></DIV></BLOCKQUOTE> 1.196 +<P>The bits in the addresses are numbered from 0 on the right: the = 1.197 +rightmost bit=20 1.198 +is bit 0, the bit to its left is bit 1, etc. Bit j contributes = 1.199 +2<SUP>j</SUP> to=20 1.200 +the value of the binary number.</P> 1.201 +<P>Here is the sequence of operations that can be performed in parallel: = 1.202 + 1.203 +<OL> 1.204 + <LI>All elements are sorted single element subsequences.=20 1.205 + <LI>Pairs of elements are sorted into ascending or descending = 1.206 +subsequences: 1.207 + <DIV align=3Dleft> 1.208 + <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 = 1.209 +border=3D1> 1.210 + <TBODY> 1.211 + <TR> 1.212 + <TD>[0000,0001]</TD> 1.213 + <TD>ascending</TD></TR> 1.214 + <TR> 1.215 + <TD>[0010,0011]</TD> 1.216 + <TD>descending</TD></TR> 1.217 + <TR> 1.218 + <TD>[0100,0101]</TD> 1.219 + <TD>ascending</TD></TR> 1.220 + <TR> 1.221 + <TD>[0110,0111]</TD> 1.222 + <TD>descending</TD></TR></TBODY></TABLE></DIV></LI></OL> 1.223 +<BLOCKQUOTE> 1.224 + <UL> 1.225 + <LI>Pairs of elements whose numbers differ in bit 0, the lowest bit, = 1.226 +are=20 1.227 + compared and conditionally exchanged.=20 1.228 + <LI>Pairs of numbers whose bit 1 is zero are sorted in ascending = 1.229 +order.=20 1.230 + Those whose bit 1 is one are sorted into descending order.=20 1.231 +</LI></UL></BLOCKQUOTE> 1.232 +<OL start=3D3> 1.233 + <LI>These pairs are compared and conditionally exchanged: </LI></OL> 1.234 +<BLOCKQUOTE> 1.235 + <P>First, corresponding to the top level merge call:</P></BLOCKQUOTE> 1.236 +<BLOCKQUOTE> 1.237 + <DIV align=3Dleft> 1.238 + <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 = 1.239 +border=3D1> 1.240 + <TBODY> 1.241 + <TR> 1.242 + <TD>0000<->0010</TD> 1.243 + <TD>ascending</TD></TR> 1.244 + <TR> 1.245 + <TD>0001<->0011</TD> 1.246 + <TD>ascending</TD></TR> 1.247 + <TR> 1.248 + <TD>0100<->0110</TD> 1.249 + <TD>descending</TD></TR> 1.250 + <TR> 1.251 + <TD>0101<->0111</TD> 1.252 + <TD>descending</TD></TR></TBODY></TABLE></DIV></BLOCKQUOTE> 1.253 +<BLOCKQUOTE> 1.254 + <P>Second, corresponding to the recursive merge = 1.255 +calls:</P></BLOCKQUOTE> 1.256 +<BLOCKQUOTE> 1.257 + <DIV align=3Dleft> 1.258 + <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 = 1.259 +border=3D1> 1.260 + <TBODY> 1.261 + <TR> 1.262 + <TD>0000<->0001</TD> 1.263 + <TD>ascending</TD></TR> 1.264 + <TR> 1.265 + <TD>0010<->0011</TD> 1.266 + <TD>ascending</TD></TR> 1.267 + <TR> 1.268 + <TD>0100<->0101</TD> 1.269 + <TD>descending</TD></TR> 1.270 + <TR> 1.271 + <TD>0110<->0111</TD> 1.272 + <TD>descending</TD></TR></TBODY></TABLE></DIV></BLOCKQUOTE> 1.273 +<BLOCKQUOTE> 1.274 + <P>In both cases, bit 2 determines whether the elements are sorted = 1.275 +ascending=20 1.276 + (bit 2 equals 0) or descending (=3D1).</P> 1.277 + <P>In the first level recursive call of mergeup or mergedown, the = 1.278 +elements=20 1.279 + compared have positions that differ in bit 1. In the second level = 1.280 +calls, the=20 1.281 + elements compared differ in bit 0.</P></BLOCKQUOTE> 1.282 +<OL start=3D4> 1.283 + <LI>The final series of merges that puts the array in order = 1.284 +corresponds to=20 1.285 + three levels of calls to mergeup.=20 1.286 + <P>First level call of mergeup:</P> 1.287 + <DIV align=3Dleft> 1.288 + <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 = 1.289 +border=3D1> 1.290 + <TBODY> 1.291 + <TR> 1.292 + <TD>0000<->0100</TD> 1.293 + <TD>ascending</TD></TR> 1.294 + <TR> 1.295 + <TD>0001<->0101</TD> 1.296 + <TD>ascending</TD></TR> 1.297 + <TR> 1.298 + <TD>0010<->0110</TD> 1.299 + <TD>ascending</TD></TR> 1.300 + <TR> 1.301 + <TD>0011<->0111</TD> 1.302 + <TD>ascending</TD></TR></TBODY></TABLE></DIV></LI></OL> 1.303 +<BLOCKQUOTE> 1.304 + <P>Two second level recursive calls of mergeup:</P></BLOCKQUOTE> 1.305 +<BLOCKQUOTE> 1.306 + <DIV align=3Dleft> 1.307 + <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 = 1.308 +border=3D1> 1.309 + <TBODY> 1.310 + <TR> 1.311 + <TD>0000<->0010</TD> 1.312 + <TD>ascending</TD></TR> 1.313 + <TR> 1.314 + <TD>0001<->0011</TD> 1.315 + <TD>ascending</TD></TR> 1.316 + <TR> 1.317 + <TD>0100<->0110</TD> 1.318 + <TD>ascending</TD></TR> 1.319 + <TR> 1.320 + <TD>0101<->0111</TD> 1.321 + <TD>ascending</TD></TR></TBODY></TABLE></DIV></BLOCKQUOTE> 1.322 +<BLOCKQUOTE> 1.323 + <P>Four third level recursive calls of mergeup:</P></BLOCKQUOTE> 1.324 +<BLOCKQUOTE> 1.325 + <DIV align=3Dleft> 1.326 + <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 = 1.327 +border=3D1> 1.328 + <TBODY> 1.329 + <TR> 1.330 + <TD>0000<->0001</TD> 1.331 + <TD>ascending</TD></TR> 1.332 + <TR> 1.333 + <TD>0010<->0011</TD> 1.334 + <TD>ascending</TD></TR> 1.335 + <TR> 1.336 + <TD>0100<->0101</TD> 1.337 + <TD>ascending</TD></TR> 1.338 + <TR> 1.339 + <TD>0110<->0111</TD> 1.340 + <TD>ascending</TD></TR></TBODY></TABLE></DIV></BLOCKQUOTE> 1.341 +<BLOCKQUOTE> 1.342 + <P>In all cases, bit 3 determines that the elements are sorted = 1.343 +ascending (bit=20 1.344 + 3 equals 0).</P> 1.345 + <P>In the first level recursive call of mergeup or mergedown, the = 1.346 +elements=20 1.347 + compared have positions that differ in bit 2. In the second level = 1.348 +calls, the=20 1.349 + elements compared differ in bit 1. In the third level calls, the = 1.350 +elements=20 1.351 + compared differ in bit 0.</P> 1.352 + <P>So here's the code:</P> 1.353 + <BLOCKQUOTE><PRE> <FONT face=3DCourier> </FONT>int i,j,k; 1.354 + for (k=3D2;k<=3DN;k=3D2*k) { 1.355 + for (j=3Dk>>1;j>0;j=3Dj>>1) { 1.356 + for (i=3D0;i<N;i++) { 1.357 + int ixj=3Di^j; 1.358 + if ((ixj)>i) { 1.359 + if ((i&k)=3D=3D0 && get(i)>get(ixj)) = 1.360 +exchange(i,ixj); 1.361 + if ((i&k)!=3D0 && get(i)<get(ixj)) = 1.362 +exchange(i,ixj); 1.363 + } 1.364 + } 1.365 + } 1.366 + }</PRE></BLOCKQUOTE> 1.367 + <P>In this code, k selects the bit position that determines whether = 1.368 +the pairs=20 1.369 + of elements are to be exchanged into ascending or descending order. = 1.370 +Variable j=20 1.371 + corresponds to the distance apart the elements are that are to be = 1.372 +compared and=20 1.373 + conditionally exchanged. Variable i goes through all the = 1.374 +elements; ixj=20 1.375 + is the element that is the pair of element i (the exclusive-or of i = 1.376 +and j, the=20 1.377 + element whose position differs only in bit position (log<SUB>2</SUB> = 1.378 +j)). We=20 1.379 + only compare elements i and ixj if i<ixj. This avoids comparing = 1.380 +them=20 1.381 + twice.</P></BLOCKQUOTE> 1.382 +<P><APPLET height=3D200 archive=3Dsorts3.jar width=3D400 align=3Dleft=20 1.383 +code=3Dcom.toolsofcomputing.SortApplets.BitonicSort3.class> 1.384 +Bitonic Sort3</APPLET> <B>Bitonic Sort3</B><STRONG>.</STRONG> The third = 1.385 +version=20 1.386 +of bitonic sort is the same as the second except that the array is shown = 1.387 +after=20 1.388 +each iteration of the <EM>for i</EM> loop. This gives the appearance of = 1.389 +a=20 1.390 +parallel algorithm.</P> 1.391 +<P>In this version, the delay between each showing of the array is set = 1.392 +to five=20 1.393 +times the delay following exchanges of single elements in the other = 1.394 +versions.=20 1.395 +There are two reasons: first, it simulates the longer time required to = 1.396 +exchange=20 1.397 +elements between nodes of a distributed memory parallel computer, and = 1.398 +second, it=20 1.399 +slows down the simulation enough that you will be able to make sense of = 1.400 +it. </P> 1.401 +<P> </P> 1.402 +<P> </P> 1.403 +<P><STRONG>Parallel bitonic sort. </STRONG>Here is a version of = 1.404 +bitonic=20 1.405 +sort that uses the Tools of Computing thread package. A version of the = 1.406 +first=20 1.407 +bitonic sort algorithm builds a task graph to do the sorting. The tasks = 1.408 +are=20 1.409 +placed in a RunQueue when they become runnable. Tasks become runnable = 1.410 +when all=20 1.411 +tasks in a predecessor set have terminated. There are a limited number = 1.412 +of=20 1.413 +Threads (4) running tasks from the queue. When tasks complete, they = 1.414 +signal a=20 1.415 +TerminationGroup. When all tasks in a TerminationGroup have signaled = 1.416 +their=20 1.417 +completion, the tasks waiting for the termination of that group are made = 1.418 + 1.419 +runnable.</P> 1.420 +<P><APPLET height=3D200 archive=3Dsorts3.jar width=3D768=20 1.421 +code=3Dcom.toolsofcomputing.SortApplets.ParBitonicSort.class> 1.422 + ParBitonicSort </APPLET> </P> 1.423 +<P><A=20 1.424 +href=3D"http://www.tools-of-computing.com/tc/CS/Sorts/SortAlgorithms.htm"= 1.425 +>Back to=20 1.426 +beginning of the tutorial</A></P></BODY></HTML>