Mercurial > cgi-bin > hgwebdir.cgi > POP > oldRepo
view 3__Intelligence_gathering/Bitonic_Sort.mht @ 4:ef3143bbd516
Display works, modifying syntax graph generator -- adding view hierarchy to it
| author | Sean Halle <seanhalle@yahoo.com> |
|---|---|
| date | Wed, 23 Jul 2014 18:51:15 -0700 |
| parents | |
| children |
line source
1 From: <Saved by Microsoft Internet Explorer 5>
2 Subject: Bitonic Sort
3 Date: Mon, 4 Jun 2007 10:57:06 -0700
4 MIME-Version: 1.0
5 Content-Type: text/html;
6 charset="Windows-1252"
7 Content-Transfer-Encoding: quoted-printable
8 Content-Location: http://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htm
9 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2962
11 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
12 <HTML><HEAD><TITLE>Bitonic Sort</TITLE>
13 <META http-equiv=3DContent-Type content=3D"text/html; =
14 charset=3Dwindows-1252">
15 <META content=3D"MSHTML 6.00.2900.2963" name=3DGENERATOR></HEAD>
16 <BODY text=3D#000000 vLink=3D#6699cc aLink=3D#ff3300 link=3D#3333cc =
17 bgColor=3D#ffcc99>
18 <H1 align=3Dcenter>Bitonic Sort</H1>
19 <P align=3Dcenter>Abstract</P>
20 <BLOCKQUOTE>
21 <BLOCKQUOTE>
22 <BLOCKQUOTE>
23 <BLOCKQUOTE>
24 <P align=3Dleft>Continuing a tutorial on sorting algorithms, =
25 this page=20
26 animates bitonic =
27 sort.</P></BLOCKQUOTE></BLOCKQUOTE></BLOCKQUOTE></BLOCKQUOTE>
28 <P align=3Dcenter>Author<BR>Thomas W. Christopher<BR></P>
29 <P>Bitonic sort is a sorting algorithm designed specially for parallel=20
30 machines.</P>
31 <P>A sorted sequence is a monotonically non-decreasing (or =
32 non-increasing)=20
33 sequence. A bitonic sequence is composed of two subsequences, one =
34 monotonically=20
35 non-decreasing and the other monotonically non-increasing. A "V" and an =
36 A-frame=20
37 are examples of bitonic sequences.</P>
38 <P>I get tired of saying "non-decreasing" and "non-increasing." They are =
39 clunky=20
40 and throw an extra negative into sentences. I will use "ascending" to =
41 mean=20
42 "non-decreasing" and "descending" to mean "non-increasing."</P>
43 <P>Moreover, any rotation of a bitonic sequence is a bitonic sequence, =
44 or if you=20
45 prefer, one of the subsequences can wrap around the end of the bitonic=20
46 sequence.</P>
47 <P>Of course, a sorted sequence is itself a bitonic sequence: one of the =
49 subsequences is empty.</P>
50 <P>Now we come to a strange property of bitoinic sequences, the property =
51 that is=20
52 uses in bitonic sort: </P>
53 <BLOCKQUOTE>
54 <P>Suppose you have a bitonic sequence of length 2n, that is, elements =
55 in=20
56 positions [0,2n). You can easily divide it into two halves, [0,n) and =
57 [n,2n),=20
58 such that
59 <UL>
60 <LI>each half is a bitonic sequence, and=20
61 <LI>every element in half [0,n) is less than or equal to each =
62 element in=20
63 [n,2n). (Or greater than or equal to, of course.) =
64 </LI></UL></BLOCKQUOTE>
65 <P>What is this easy method? Simply compare elements in the =
66 corresponding=20
67 positions in the two halves and exchange them if they are out of =
68 order.</P>
69 <BLOCKQUOTE>
70 <P> for (i=3D0;i<n;i++)=20
71 {<BR> if =
72 (get(i)>get(i+n))=20
73 exchange(i,i+n);<BR> }</P></BLOCKQUOTE>
74 <P>This is sometimes called a bitonic merge.</P>
75 <P>Why does it work? I'm not sure I could do a concise and clear enough =
76 proof to=20
77 fit in with these pages. Let's just leave it without a proof, but =
78 true.</P>
79 <P>So here's how we do a bitonic sort:=20
80 <UL>
81 <LI>We sort only sequences a power of two in length, so we can always =
82 divide a=20
83 subsequence of mnore than one element into two halves.=20
84 <LI>We sort the lower half into ascending (=3Dnon-decreasing, =
85 remember) order=20
86 and the upper half into descending order. This gives us a bitonic =
87 sequence.=20
88 <LI>We perform a bitonic merge on the sequence, which gives us a =
89 bitonic=20
90 sequence in each half and all the larger elements in the upper half.=20
91 <LI>We recursively bitonically merge each half until all the elements =
92 are=20
93 sorted. </LI></UL>
94 <P><APPLET height=3D200 archive=3Dsorts3.jar width=3D400 align=3Dleft=20
95 code=3Dcom.toolsofcomputing.SortApplets.BitonicSort.class>
96 Bitonic Sort</APPLET> <B>Bitonic Sort</B> This first version actually =
97 uses=20
98 recursion. It uses methods sortup, sortdown, mergeup, and mergedown, to =
99 sort=20
100 into ascending order or descending order and to recursively merge into =
101 ascending=20
102 or descending order.</P>
103 <P>Method <EM>void sortup(int m, int n)</EM> will sort the n elements in =
104 the=20
105 range [m,m+n) into ascending order. It uses method <EM>void mergeup(int =
106 m, int=20
107 n)</EM> to merge the n elements in the subsequence [m,m+n) into =
108 ascending order.=20
109 Similarly for <EM>void sortdown(int m, int n)</EM> and <EM>void =
110 mergedown(int m,=20
111 int n)</EM>.</P>
112 <P>The overall sort is performed by a call:</P>
113 <BLOCKQUOTE>
114 <P> sortup(0,N);</P></BLOCKQUOTE>
115 <P>Both sortup and sortdown recursively sort each half to produce an =
116 A-frame=20
117 shape and then recursively merge that into an ascending or descending=20
118 sequence.</P>
119 <BLOCKQUOTE>
120 <P>void sortup(int m, int n) {//from m to m+n<BR> if =
121 (n=3D=3D1)=20
122 return;<BR> sortup(m,n/2);<BR> =20
123 sortdown(m+n/2,n/2);<BR> =
124 mergeup(m,n/2);<BR>}<BR>void=20
125 sortdown(int m, int n) {//from m to m+n<BR> if =
126 (n=3D=3D1)=20
127 return;<BR> sortup(m,n/2);<BR> =20
128 sortdown(m+n/2,n/2);<BR> =20
129 mergedown(m,n/2);<BR>}</P></BLOCKQUOTE>
130 <P>Methods mergeup and mergedown are fairly straightfoward. They compare =
132 elements in the two halves, exchange them if they are out of order, and=20
133 recursively merge the two halves. Call mergeup( m, n) sorts into =
134 ascending=20
135 order the 2*n elements in the range [m,2n).</P>
136 <BLOCKQUOTE>
137 <P>void mergeup(int m, int n) {<BR> if (n=3D=3D0)=20
138 return;<BR> int i;<BR> for=20
139 (i=3D0;i<n;i++) {<BR> if=20
140 (get(m+i)>get(m+i+n)) exchange(m+i,m+i+n);<BR> =20
141 }<BR> mergeup(m,n/2);<BR> =20
142 mergeup(m+n,n/2);<BR>}<BR>void mergedown(int m, int n) =
143 {<BR> =20
144 if (n=3D=3D0) return;<BR> int =
145 i;<BR> for=20
146 (i=3D0;i<n;i++) {<BR> if=20
147 (get(m+i)<get(m+i+n)) exchange(m+i,m+i+n);<BR> =20
148 }<BR> mergedown(m,n/2);<BR> =20
149 mergedown(m+n,n/2);<BR>}</P></BLOCKQUOTE>
150 <P> </P>
151 <P><APPLET height=3D200 archive=3Dsorts3.jar width=3D400 align=3Dleft=20
152 code=3Dcom.toolsofcomputing.SortApplets.BitonicSort2.class>
153 Bitonic Sort2</APPLET> <B>Bitonic Sort2</B> Bitonic sort is perfect for=20
154 parallelization. The recursive calls of merge can be done in parallel. =
155 The loops=20
156 in the merges, comparing and conditionally exchanging elements (m+i) and =
157 (m+i+n)=20
158 can also be run in parallel.</P>
159 <P>However, getting it to run efficiently in parallel requires turning =
160 the=20
161 algorithm upside down. The algorithm is expressed in terms of recursive =
162 calls.=20
163 What we need is an algorithm in terms of each individual element.</P>
164 <P>Let's examine what the elements are doing. We will use an =
165 eight-element array=20
166 and identify the elements by their positions in binary.</P>
167 <BLOCKQUOTE>
168 <DIV align=3Dleft>
169 <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 =
170 border=3D1>
171 <TBODY>
172 <TR>
173 <TD>index</TD>
174 <TD align=3Dmiddle>0</TD>
175 <TD align=3Dmiddle>1</TD>
176 <TD align=3Dmiddle>2</TD>
177 <TD align=3Dmiddle>3</TD>
178 <TD align=3Dmiddle>4</TD>
179 <TD align=3Dmiddle>5</TD>
180 <TD align=3Dmiddle>6</TD>
181 <TD align=3Dmiddle>7</TD></TR>
182 <TR>
183 <TD>in binary</TD>
184 <TD align=3Dmiddle>0000</TD>
185 <TD align=3Dmiddle>0001</TD>
186 <TD align=3Dmiddle>0010</TD>
187 <TD align=3Dmiddle>0011</TD>
188 <TD align=3Dmiddle>0100</TD>
189 <TD align=3Dmiddle>0101</TD>
190 <TD align=3Dmiddle>0110</TD>
191 <TD =
192 align=3Dmiddle>0111</TD></TR></TBODY></TABLE></DIV></BLOCKQUOTE>
193 <P>The bits in the addresses are numbered from 0 on the right: the =
194 rightmost bit=20
195 is bit 0, the bit to its left is bit 1, etc. Bit j contributes =
196 2<SUP>j</SUP> to=20
197 the value of the binary number.</P>
198 <P>Here is the sequence of operations that can be performed in parallel: =
200 <OL>
201 <LI>All elements are sorted single element subsequences.=20
202 <LI>Pairs of elements are sorted into ascending or descending =
203 subsequences:
204 <DIV align=3Dleft>
205 <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 =
206 border=3D1>
207 <TBODY>
208 <TR>
209 <TD>[0000,0001]</TD>
210 <TD>ascending</TD></TR>
211 <TR>
212 <TD>[0010,0011]</TD>
213 <TD>descending</TD></TR>
214 <TR>
215 <TD>[0100,0101]</TD>
216 <TD>ascending</TD></TR>
217 <TR>
218 <TD>[0110,0111]</TD>
219 <TD>descending</TD></TR></TBODY></TABLE></DIV></LI></OL>
220 <BLOCKQUOTE>
221 <UL>
222 <LI>Pairs of elements whose numbers differ in bit 0, the lowest bit, =
223 are=20
224 compared and conditionally exchanged.=20
225 <LI>Pairs of numbers whose bit 1 is zero are sorted in ascending =
226 order.=20
227 Those whose bit 1 is one are sorted into descending order.=20
228 </LI></UL></BLOCKQUOTE>
229 <OL start=3D3>
230 <LI>These pairs are compared and conditionally exchanged: </LI></OL>
231 <BLOCKQUOTE>
232 <P>First, corresponding to the top level merge call:</P></BLOCKQUOTE>
233 <BLOCKQUOTE>
234 <DIV align=3Dleft>
235 <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 =
236 border=3D1>
237 <TBODY>
238 <TR>
239 <TD>0000<->0010</TD>
240 <TD>ascending</TD></TR>
241 <TR>
242 <TD>0001<->0011</TD>
243 <TD>ascending</TD></TR>
244 <TR>
245 <TD>0100<->0110</TD>
246 <TD>descending</TD></TR>
247 <TR>
248 <TD>0101<->0111</TD>
249 <TD>descending</TD></TR></TBODY></TABLE></DIV></BLOCKQUOTE>
250 <BLOCKQUOTE>
251 <P>Second, corresponding to the recursive merge =
252 calls:</P></BLOCKQUOTE>
253 <BLOCKQUOTE>
254 <DIV align=3Dleft>
255 <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 =
256 border=3D1>
257 <TBODY>
258 <TR>
259 <TD>0000<->0001</TD>
260 <TD>ascending</TD></TR>
261 <TR>
262 <TD>0010<->0011</TD>
263 <TD>ascending</TD></TR>
264 <TR>
265 <TD>0100<->0101</TD>
266 <TD>descending</TD></TR>
267 <TR>
268 <TD>0110<->0111</TD>
269 <TD>descending</TD></TR></TBODY></TABLE></DIV></BLOCKQUOTE>
270 <BLOCKQUOTE>
271 <P>In both cases, bit 2 determines whether the elements are sorted =
272 ascending=20
273 (bit 2 equals 0) or descending (=3D1).</P>
274 <P>In the first level recursive call of mergeup or mergedown, the =
275 elements=20
276 compared have positions that differ in bit 1. In the second level =
277 calls, the=20
278 elements compared differ in bit 0.</P></BLOCKQUOTE>
279 <OL start=3D4>
280 <LI>The final series of merges that puts the array in order =
281 corresponds to=20
282 three levels of calls to mergeup.=20
283 <P>First level call of mergeup:</P>
284 <DIV align=3Dleft>
285 <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 =
286 border=3D1>
287 <TBODY>
288 <TR>
289 <TD>0000<->0100</TD>
290 <TD>ascending</TD></TR>
291 <TR>
292 <TD>0001<->0101</TD>
293 <TD>ascending</TD></TR>
294 <TR>
295 <TD>0010<->0110</TD>
296 <TD>ascending</TD></TR>
297 <TR>
298 <TD>0011<->0111</TD>
299 <TD>ascending</TD></TR></TBODY></TABLE></DIV></LI></OL>
300 <BLOCKQUOTE>
301 <P>Two second level recursive calls of mergeup:</P></BLOCKQUOTE>
302 <BLOCKQUOTE>
303 <DIV align=3Dleft>
304 <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 =
305 border=3D1>
306 <TBODY>
307 <TR>
308 <TD>0000<->0010</TD>
309 <TD>ascending</TD></TR>
310 <TR>
311 <TD>0001<->0011</TD>
312 <TD>ascending</TD></TR>
313 <TR>
314 <TD>0100<->0110</TD>
315 <TD>ascending</TD></TR>
316 <TR>
317 <TD>0101<->0111</TD>
318 <TD>ascending</TD></TR></TBODY></TABLE></DIV></BLOCKQUOTE>
319 <BLOCKQUOTE>
320 <P>Four third level recursive calls of mergeup:</P></BLOCKQUOTE>
321 <BLOCKQUOTE>
322 <DIV align=3Dleft>
323 <TABLE borderColorDark=3D#000000 borderColorLight=3D#ff9933 =
324 border=3D1>
325 <TBODY>
326 <TR>
327 <TD>0000<->0001</TD>
328 <TD>ascending</TD></TR>
329 <TR>
330 <TD>0010<->0011</TD>
331 <TD>ascending</TD></TR>
332 <TR>
333 <TD>0100<->0101</TD>
334 <TD>ascending</TD></TR>
335 <TR>
336 <TD>0110<->0111</TD>
337 <TD>ascending</TD></TR></TBODY></TABLE></DIV></BLOCKQUOTE>
338 <BLOCKQUOTE>
339 <P>In all cases, bit 3 determines that the elements are sorted =
340 ascending (bit=20
341 3 equals 0).</P>
342 <P>In the first level recursive call of mergeup or mergedown, the =
343 elements=20
344 compared have positions that differ in bit 2. In the second level =
345 calls, the=20
346 elements compared differ in bit 1. In the third level calls, the =
347 elements=20
348 compared differ in bit 0.</P>
349 <P>So here's the code:</P>
350 <BLOCKQUOTE><PRE> <FONT face=3DCourier> </FONT>int i,j,k;
351 for (k=3D2;k<=3DN;k=3D2*k) {
352 for (j=3Dk>>1;j>0;j=3Dj>>1) {
353 for (i=3D0;i<N;i++) {
354 int ixj=3Di^j;
355 if ((ixj)>i) {
356 if ((i&k)=3D=3D0 && get(i)>get(ixj)) =
357 exchange(i,ixj);
358 if ((i&k)!=3D0 && get(i)<get(ixj)) =
359 exchange(i,ixj);
360 }
361 }
362 }
363 }</PRE></BLOCKQUOTE>
364 <P>In this code, k selects the bit position that determines whether =
365 the pairs=20
366 of elements are to be exchanged into ascending or descending order. =
367 Variable j=20
368 corresponds to the distance apart the elements are that are to be =
369 compared and=20
370 conditionally exchanged. Variable i goes through all the =
371 elements; ixj=20
372 is the element that is the pair of element i (the exclusive-or of i =
373 and j, the=20
374 element whose position differs only in bit position (log<SUB>2</SUB> =
375 j)). We=20
376 only compare elements i and ixj if i<ixj. This avoids comparing =
377 them=20
378 twice.</P></BLOCKQUOTE>
379 <P><APPLET height=3D200 archive=3Dsorts3.jar width=3D400 align=3Dleft=20
380 code=3Dcom.toolsofcomputing.SortApplets.BitonicSort3.class>
381 Bitonic Sort3</APPLET> <B>Bitonic Sort3</B><STRONG>.</STRONG> The third =
382 version=20
383 of bitonic sort is the same as the second except that the array is shown =
384 after=20
385 each iteration of the <EM>for i</EM> loop. This gives the appearance of =
386 a=20
387 parallel algorithm.</P>
388 <P>In this version, the delay between each showing of the array is set =
389 to five=20
390 times the delay following exchanges of single elements in the other =
391 versions.=20
392 There are two reasons: first, it simulates the longer time required to =
393 exchange=20
394 elements between nodes of a distributed memory parallel computer, and =
395 second, it=20
396 slows down the simulation enough that you will be able to make sense of =
397 it. </P>
398 <P> </P>
399 <P> </P>
400 <P><STRONG>Parallel bitonic sort. </STRONG>Here is a version of =
401 bitonic=20
402 sort that uses the Tools of Computing thread package. A version of the =
403 first=20
404 bitonic sort algorithm builds a task graph to do the sorting. The tasks =
405 are=20
406 placed in a RunQueue when they become runnable. Tasks become runnable =
407 when all=20
408 tasks in a predecessor set have terminated. There are a limited number =
409 of=20
410 Threads (4) running tasks from the queue. When tasks complete, they =
411 signal a=20
412 TerminationGroup. When all tasks in a TerminationGroup have signaled =
413 their=20
414 completion, the tasks waiting for the termination of that group are made =
416 runnable.</P>
417 <P><APPLET height=3D200 archive=3Dsorts3.jar width=3D768=20
418 code=3Dcom.toolsofcomputing.SortApplets.ParBitonicSort.class>
419 ParBitonicSort </APPLET> </P>
420 <P><A=20
421 href=3D"http://www.tools-of-computing.com/tc/CS/Sorts/SortAlgorithms.htm"=
422 >Back to=20
423 beginning of the tutorial</A></P></BODY></HTML>