#N canvas 643 389 587 357 10;
#X obj 53 51 inlet;
#X obj 53 249 outlet;
#X obj 449 100 loadbang;
#X obj 387 52 inlet;
#X obj 387 161 list append \$1;
#X obj 387 131 t b a;
#X obj 387 189 s \$0-direction;
#X obj 225 167 sel 0 1;
#X obj 53 73 list-filter;
#N canvas 189 406 677 293 \$0-checknum 0;
#X obj 131 95 route float;
#X msg 131 116 1;
#X obj 205 149 print;
#X msg 205 119 list-sort: Warning: dropped a non-number from list;
#X obj 131 70 inlet;
#X obj 131 149 outlet;
#X connect 0 0 1 0;
#X connect 0 1 3 0;
#X connect 1 0 5 0;
#X connect 3 0 2 0;
#X connect 4 0 0 0;
#X restore 142 73 pd \$0-checknum;
#X obj 287 153 s \$0-length;
#X obj 225 136 t f f;
#X obj 53 225 list-tabdump;
#X obj 53 179 list prepend \$0-table;
#X obj 53 153 f;
#X obj 68 131 r \$0-length;
#X obj 53 203 list append 0;
#X text 55 294 2008 Matt Barber;
#N canvas 363 457 852 403 \$0-table 0;
#X obj 80 75 list-len;
#X msg 261 337 resize \$1;
#X obj 60 354 s \$0-table;
#X obj 41 24 inlet;
#X obj 31 378 outlet;
#X obj 60 118 list prepend 0;
#X obj 148 92 t f f;
#X obj 41 46 t b a a;
#X obj 31 109 f;
#X obj 139 24 table \$0-table 100;
#X obj 175 112 moses 100;
#X obj 175 149 * 0.01;
#X obj 175 171 + 1;
#X obj 175 194 int;
#X obj 175 218 * 100;
#X obj 261 235 t f f f;
#X obj 280 259 * 2;
#X msg 280 281 resize \$1;
#X obj 280 303 s \$0-queue-table;
#X text 398 314 <== resize list table so that it can hold the lists.
Size of queue table needs to be about 2 times this in the worst case
(2 values for each partition \, with a worst case of n-1 partitions
for a list of size n).;
#X connect 0 0 6 0;
#X connect 1 0 2 0;
#X connect 3 0 7 0;
#X connect 5 0 2 0;
#X connect 6 0 8 1;
#X connect 6 1 10 0;
#X connect 7 0 8 0;
#X connect 7 1 5 0;
#X connect 7 2 0 0;
#X connect 8 0 4 0;
#X connect 10 1 11 0;
#X connect 11 0 12 0;
#X connect 12 0 13 0;
#X connect 13 0 14 0;
#X connect 14 0 15 0;
#X connect 15 0 1 0;
#X connect 15 1 16 0;
#X connect 15 2 10 1;
#X connect 16 0 17 0;
#X connect 17 0 18 0;
#X restore 225 113 pd \$0-table;
#X obj 53 96 t b a;
#X text 364 248 <== engine;
#X obj 264 219 - 1;
#N canvas 176 230 1064 568 \$0-main-loop 0;
#X obj 70 14 inlet;
#X obj 70 231 v \$0-left;
#X obj 136 231 v \$0-right;
#N canvas 677 165 450 300 \$0-tabswap 0;
#X obj 164 23 inlet;
#X obj 236 47 inlet;
#X obj 250 120 f;
#X obj 265 97 tabread \$0-table;
#X obj 69 120 tabread \$0-table;
#X obj 93 204 tabwrite \$0-table;
#X obj 164 46 t b f f;
#X connect 0 0 6 0;
#X connect 1 0 3 0;
#X connect 1 0 5 1;
#X connect 2 0 5 0;
#X connect 3 0 2 1;
#X connect 4 0 5 0;
#X connect 6 0 2 0;
#X connect 6 1 5 1;
#X connect 6 2 4 0;
#X restore 401 461 pd \$0-tabswap;
#N canvas 406 412 735 438 \$0-find-pivot 0;
#X obj 38 125 inlet;
#N canvas 95 526 394 222 \$0-median-of-three 0;
#X obj 47 13 inlet;
#X obj 146 50 v \$0-right;
#X obj 47 58 v \$0-left;
#X obj 96 96 +;
#X obj 96 116 * 0.5;
#X obj 47 79 t f f;
#N canvas 291 521 635 449 \$0-find-median 0;
#X obj 163 76 inlet;
#X obj 331 86 inlet;
#X obj 386 82 inlet;
#X obj 206 311 outlet;
#X obj 206 261 f;
#X obj 175 261 f;
#N canvas 60 186 904 625 \$0-logic 0;
#X obj 68 27 inlet;
#X obj 239 108 inlet;
#X obj 383 108 inlet;
#X obj 72 493 outlet;
#X obj 152 493 outlet;
#X obj 239 180 max;
#X obj 148 169 min;
#X obj 48 197 min;
#X obj 133 214 max;
#X obj 368 257 ==;
#X obj 152 293 ==;
#X obj 72 301 ==;
#X obj 133 240 t f f f;
#X obj 72 325 sel 1;
#X obj 152 317 sel 1;
#X obj 368 290 sel 1;
#X obj 152 461 spigot;
#X obj 72 460 spigot;
#X obj 68 60 t f f b;
#X obj 107 108 s \$0-logic-spigots;
#X msg 107 86 1;
#X obj 152 342 t b b;
#X obj 246 398 r \$0-logic-spigots;
#X msg 185 398 0;
#X msg 105 398 0;
#X text 376 396 <== if median is doubled \, only bang out one of them.
;
#X obj 368 314 t b b;
#X obj 368 493 outlet;
#X text 396 177 <== First "sort" right and center \, then "sort" left
and right \, then "sort" left and center. Median will be sent to the
trigger. Another option might be to actually sort them in the table
\, but this probably takes more steps in Pd since reading a table requires
an object.;
#X connect 0 0 18 0;
#X connect 1 0 5 0;
#X connect 1 0 6 0;
#X connect 1 0 10 1;
#X connect 2 0 6 1;
#X connect 2 0 5 1;
#X connect 2 0 9 1;
#X connect 5 0 7 1;
#X connect 6 0 8 1;
#X connect 7 0 8 0;
#X connect 8 0 12 0;
#X connect 9 0 15 0;
#X connect 10 0 14 0;
#X connect 11 0 13 0;
#X connect 12 0 11 0;
#X connect 12 1 10 0;
#X connect 12 2 9 0;
#X connect 13 0 17 0;
#X connect 14 0 21 0;
#X connect 15 0 26 0;
#X connect 16 0 4 0;
#X connect 17 0 3 0;
#X connect 18 0 7 0;
#X connect 18 1 11 1;
#X connect 18 2 20 0;
#X connect 20 0 19 0;
#X connect 21 0 16 0;
#X connect 21 1 24 0;
#X connect 22 0 16 1;
#X connect 22 0 17 1;
#X connect 23 0 16 1;
#X connect 23 0 17 1;
#X connect 24 0 17 1;
#X connect 26 0 27 0;
#X connect 26 1 23 0;
#X connect 26 1 24 0;
#X restore 45 189 pd \$0-logic;
#X obj 386 103 tabread \$0-table;
#X obj 213 103 tabread \$0-table;
#X obj 45 120 tabread \$0-table;
#X obj 163 103 t f f;
#X obj 237 261 f;
#X text 276 262 <== output index of median;
#X connect 0 0 10 0;
#X connect 1 0 4 1;
#X connect 1 0 8 0;
#X connect 2 0 7 0;
#X connect 2 0 11 1;
#X connect 4 0 3 0;
#X connect 5 0 3 0;
#X connect 6 0 5 0;
#X connect 6 1 4 0;
#X connect 6 2 11 0;
#X connect 7 0 6 2;
#X connect 8 0 6 1;
#X connect 9 0 6 0;
#X connect 10 0 9 0;
#X connect 10 1 5 1;
#X connect 11 0 3 0;
#X restore 47 160 pd \$0-find-median;
#X obj 47 182 outlet;
#X obj 96 137 int;
#X obj 47 33 t b b;
#X connect 0 0 9 0;
#X connect 1 0 6 2;
#X connect 1 0 3 1;
#X connect 2 0 5 0;
#X connect 3 0 4 0;
#X connect 4 0 8 0;
#X connect 5 0 6 0;
#X connect 5 1 3 0;
#X connect 6 0 7 0;
#X connect 8 0 6 1;
#X connect 9 0 2 0;
#X connect 9 1 1 0;
#X restore 38 204 pd \$0-median-of-three;
#X obj 182 163 v \$0-right;
#X obj 38 146 t b b;
#X obj 38 258 ==;
#X obj 38 228 t f f;
#X obj 88 313 f;
#X obj 137 330 pack 0 0;
#X obj 38 280 sel 0;
#X obj 137 351 s \$0-swap;
#X text 215 279 <== If the median is the right element \, do nothing
\, otherwise swap the median element with the right element.;
#X text 36 15 Quicksort algorithm runs quicker on average (with evenly
distributed lists) if pivot is chosen as the median of three elements
of a partition to be sorted. The upshot is that the same method can
be used to manually sort partitions of 3 elements or less. This step
isn't needed for partitions of size four \, since the next round will
be manually sorted no matter what. This step can be sabotaged with
specialized "median-of-three killer" lists \, which don't arise in
everyday circumstances.;
#X text 235 202 <== Find the median of the left \, middle \, and right
elements and pass the index. Any three indices will do \, but using
these three might lead to fewer total swaps.;
#X connect 0 0 3 0;
#X connect 1 0 5 0;
#X connect 2 0 4 1;
#X connect 2 0 7 1;
#X connect 3 0 1 0;
#X connect 3 1 2 0;
#X connect 4 0 8 0;
#X connect 5 0 4 0;
#X connect 5 1 6 1;
#X connect 6 0 7 0;
#X connect 7 0 9 0;
#X connect 8 0 6 0;
#X restore 175 403 pd \$0-find-pivot;
#N canvas 292 184 823 728 \$0-partition-loop 0;
#X obj 327 288 v \$0-right;
#X obj 149 260 v \$0-left;
#X obj 64 136 inlet;
#N canvas 741 346 630 559 \$0-right-loop 0;
#X obj 165 53 inlet;
#X obj 245 266 inlet;
#X obj 112 133 until;
#X obj 165 74 - 1;
#X obj 169 168 f;
#X obj 225 168 - 1;
#X obj 193 467 f;
#X obj 38 337 sel 1;
#X obj 38 359 t b b;
#X obj 65 382 s \$0-stop-right-loop;
#X obj 38 260 tabread \$0-table;
#X obj 304 208 v $-left;
#X obj 289 286 sel 1;
#X obj 316 329 s \$0-stop-right-loop;
#X obj 139 32 r \$0-stop-right-loop;
#X obj 165 96 t b f b;
#X text 338 266 <== insulate against a runaway "pointer";
#X obj 193 488 outlet;
#X obj 289 306 t b b;
#X obj 169 196 t f f f;
#X obj 289 263 <;
#X obj 304 235 + 1;
#X text 275 45 This decrements a pointer from the right side until
it finds a value less than the pivot.;
#X obj 38 305 <;
#N canvas 547 408 584 529 >or<? 0;
#X obj 40 52 inlet;
#X obj 153 52 inlet;
#X obj 40 272 spigot 1;
#X obj 256 272 spigot;
#X obj 361 224 unpack 0 0;
#X msg 361 178 1 0;
#X msg 412 196 0 1;
#X obj 463 93 select 0;
#X obj 361 71 select asc desc;
#X obj 40 437 outlet;
#X obj 153 437 outlet;
#X obj 153 271 spigot 1;
#X obj 317 273 spigot;
#X obj 361 45 r \$0-direction;
#X obj 256 437 outlet;
#X obj 317 437 outlet;
#X connect 0 0 2 0;
#X connect 0 0 3 0;
#X connect 1 0 11 0;
#X connect 1 0 12 0;
#X connect 2 0 9 0;
#X connect 3 0 14 0;
#X connect 4 0 2 1;
#X connect 4 0 11 1;
#X connect 4 1 3 1;
#X connect 4 1 12 1;
#X connect 5 0 4 0;
#X connect 6 0 4 0;
#X connect 7 0 5 0;
#X connect 7 1 6 0;
#X connect 8 0 5 0;
#X connect 8 1 6 0;
#X connect 8 2 7 0;
#X connect 11 0 10 0;
#X connect 12 0 15 0;
#X connect 13 0 8 0;
#X restore 38 283 pd >or<?;
#X obj 68 305 >;
#X connect 0 0 3 0;
#X connect 1 0 24 1;
#X connect 2 0 4 0;
#X connect 3 0 15 0;
#X connect 4 0 19 0;
#X connect 5 0 4 1;
#X connect 6 0 17 0;
#X connect 7 0 8 0;
#X connect 8 0 6 0;
#X connect 8 1 9 0;
#X connect 10 0 24 0;
#X connect 11 0 21 0;
#X connect 12 0 18 0;
#X connect 14 0 2 1;
#X connect 15 0 2 0;
#X connect 15 1 4 1;
#X connect 15 2 11 0;
#X connect 18 0 6 0;
#X connect 18 1 13 0;
#X connect 19 0 10 0;
#X connect 19 1 20 0;
#X connect 19 2 5 0;
#X connect 19 2 6 1;
#X connect 20 0 12 0;
#X connect 21 0 20 1;
#X connect 23 0 7 0;
#X connect 24 0 23 0;
#X connect 24 1 23 1;
#X connect 24 2 25 0;
#X connect 24 3 25 1;
#X connect 25 0 7 0;
#X restore 312 461 pd \$0-right-loop;
#X obj 405 348 tabread \$0-table;
#X obj 312 431 f;
#X obj 64 424 f;
#N canvas 159 384 697 546 \$0-left-loop 0;
#X obj 165 52 inlet;
#X obj 245 275 inlet;
#X obj 112 133 until;
#X obj 169 168 f;
#X obj 193 477 f;
#X obj 38 357 sel 1;
#X obj 38 379 t b b;
#X obj 38 270 tabread \$0-table;
#X obj 289 276 sel 1;
#X obj 165 96 t b f b;
#X obj 193 498 outlet;
#X obj 139 18 r \$0-stop-left-loop;
#X obj 316 329 s \$0-stop-left-loop;
#X obj 65 402 s \$0-stop-left-loop;
#X obj 226 168 + 1;
#X obj 289 303 t b b;
#X obj 169 196 t f f f;
#X obj 304 188 v \$0-right;
#X obj 304 212 - 1;
#X obj 289 253 >=;
#X text 338 256 <== insulate against a runaway "pointer.";
#X text 289 22 This increments a "pointer" from the left side until
it finds a value that is greater than the pivot.;
#X obj 38 315 >;
#N canvas 547 408 584 529 >or<? 0;
#X obj 40 52 inlet;
#X obj 153 52 inlet;
#X obj 40 272 spigot 1;
#X obj 256 272 spigot;
#X obj 361 224 unpack 0 0;
#X msg 361 178 1 0;
#X msg 412 196 0 1;
#X obj 463 93 select 0;
#X obj 361 71 select asc desc;
#X obj 40 437 outlet;
#X obj 153 437 outlet;
#X obj 153 271 spigot 1;
#X obj 317 273 spigot;
#X obj 361 45 r \$0-direction;
#X obj 256 437 outlet;
#X obj 317 437 outlet;
#X connect 0 0 2 0;
#X connect 0 0 3 0;
#X connect 1 0 11 0;
#X connect 1 0 12 0;
#X connect 2 0 9 0;
#X connect 3 0 14 0;
#X connect 4 0 2 1;
#X connect 4 0 11 1;
#X connect 4 1 3 1;
#X connect 4 1 12 1;
#X connect 5 0 4 0;
#X connect 6 0 4 0;
#X connect 7 0 5 0;
#X connect 7 1 6 0;
#X connect 8 0 5 0;
#X connect 8 1 6 0;
#X connect 8 2 7 0;
#X connect 11 0 10 0;
#X connect 12 0 15 0;
#X connect 13 0 8 0;
#X restore 38 292 pd >or<?;
#X obj 68 315 <;
#X connect 0 0 9 0;
#X connect 1 0 23 1;
#X connect 2 0 3 0;
#X connect 3 0 16 0;
#X connect 4 0 10 0;
#X connect 5 0 6 0;
#X connect 6 0 4 0;
#X connect 6 1 13 0;
#X connect 7 0 23 0;
#X connect 8 0 15 0;
#X connect 9 0 2 0;
#X connect 9 1 3 1;
#X connect 9 2 17 0;
#X connect 11 0 2 1;
#X connect 14 0 3 1;
#X connect 15 0 4 0;
#X connect 15 1 12 0;
#X connect 16 0 7 0;
#X connect 16 1 19 0;
#X connect 16 2 14 0;
#X connect 16 2 4 1;
#X connect 17 0 18 0;
#X connect 18 0 19 1;
#X connect 19 0 8 0;
#X connect 22 0 5 0;
#X connect 23 0 22 0;
#X connect 23 1 22 1;
#X connect 23 2 24 0;
#X connect 23 3 24 1;
#X connect 24 0 5 0;
#X restore 64 461 pd \$0-left-loop;
#X obj 64 569 >=;
#X obj 64 483 t f f;
#X obj 327 331 t f f;
#X obj 64 591 sel 0;
#X obj 114 407 + 1;
#X obj 64 158 t b b;
#X obj 64 236 until;
#X obj 64 260 t b b;
#X obj 91 206 r \$0-stop-partition-loop;
#X obj 109 175 s \$0-partition-loop-init;
#X obj 327 243 r \$0-partition-loop-init;
#X obj 405 372 s \$0-pivot-value;
#X obj 405 435 r \$0-pivot-value;
#X obj 151 435 r \$0-pivot-value;
#X obj 312 484 s \$0-right-pointer;
#X obj 79 548 r \$0-right-pointer;
#X obj 91 508 s \$0-left-pointer;
#X obj 114 382 r \$0-left-pointer;
#X text 123 33 This partitions a portion of the table (from the "left"
to the "right" indices given) based on the pivot \, which will be the
right index value. If we're sorting in ascending order \, all values
less than the pivot will be moved to the left and the values greater
than the pivot will be moved to the right. The two loops find indices
to swap values that are on the wrong side. At the end of the loop \,
the right value will be swapped to the middle \; it is now in its proper
location in the table. New partition boundaries based on this location
are sent to the schedule queue.;
#X text 371 551 <== if the pointers have not met \, then we've found
values to swap. If they have met or passed each other \, then all values
are in place \, and we should break the loop.;
#X text 430 461 <== Run the two loops to find values to swap.;
#X obj 354 394 s \$0-right-index;
#N canvas 86 406 953 398 \$0-tail 0;
#X obj 63 69 inlet;
#X obj 398 80 inlet;
#X obj 437 137 s \$0-stop-partition-loop;
#X obj 63 277 pack 0 0;
#X obj 63 254 f;
#X obj 235 290 pack 0 0;
#X obj 328 138 f;
#X obj 63 307 s \$0-swap;
#N canvas 308 492 677 393 \$0-schedule-next 0;
#X obj 85 93 inlet;
#X obj 91 216 - 1;
#X obj 46 233 moses;
#X obj 46 178 v \$0-left;
#X obj 155 240 moses;
#X obj 129 188 v \$0-right;
#X obj 203 223 + 2;
#X obj 182 296 pack 0 0;
#X obj 182 271 swap;
#X obj 203 93 inlet;
#X obj 46 313 list append;
#X obj 46 259 pack 0 0;
#X obj 203 246 - 1;
#X obj 73 286 t b;
#X obj 46 336 s \$0-schedule;
#X obj 85 115 t b b b;
#X text 28 24 This schedules the next partitions to be sorted. After
the pivot is replaced to its proper location \, the new partitions
should be [left \, pivotindex-1] and [pivotindex+1 \, right].;
#X text 277 230 <== If the values within a pair are the same \, they
point to one element of the table which is in its proper location.
So we don't schedule it. Note the spooky arithmetic \, necessary because
[moses] is >= at the right outlet.;
#X connect 0 0 15 0;
#X connect 1 0 2 1;
#X connect 1 0 11 1;
#X connect 2 0 11 0;
#X connect 2 1 13 0;
#X connect 3 0 2 0;
#X connect 4 1 8 0;
#X connect 5 0 4 0;
#X connect 6 0 4 1;
#X connect 6 0 12 0;
#X connect 7 0 10 1;
#X connect 8 0 7 0;
#X connect 8 1 7 1;
#X connect 9 0 6 0;
#X connect 9 0 1 0;
#X connect 10 0 14 0;
#X connect 11 0 10 0;
#X connect 12 0 8 1;
#X connect 13 0 10 0;
#X connect 15 0 3 0;
#X connect 15 1 5 0;
#X connect 15 2 10 1;
#X restore 398 350 pd \$0-schedule-next;
#X obj 398 106 t b b b;
#X obj 78 227 r \$0-left-pointer;
#X obj 343 53 r \$0-left-pointer;
#X obj 108 250 r \$0-right-pointer;
#X obj 437 158 r \$0-right-index;
#X obj 328 182 t f f f;
#N canvas 0 0 363 368 \$0-adjacent? 0;
#X obj 63 73 inlet;
#X obj 123 134 inlet;
#X obj 115 220 f;
#X obj 63 151 ==;
#X obj 63 180 sel 1;
#X obj 63 95 + 1;
#X obj 63 122 t f f;
#X obj 115 243 outlet;
#X connect 0 0 5 0;
#X connect 1 0 3 1;
#X connect 2 0 7 0;
#X connect 3 0 4 0;
#X connect 4 0 2 0;
#X connect 5 0 6 0;
#X connect 6 0 3 0;
#X connect 6 1 2 1;
#X restore 427 311 pd \$0-adjacent?;
#N canvas 2 76 450 338 \$0-pivot-order? 0;
#X obj 86 44 inlet;
#X obj 96 272 outlet;
#X obj 105 192 sel 0;
#X obj 112 104 r \$0-pivot-value;
#X obj 105 79 tabread \$0-table;
#N canvas 547 408 584 529 >or<? 0;
#X obj 40 52 inlet;
#X obj 153 52 inlet;
#X obj 40 272 spigot 1;
#X obj 256 272 spigot;
#X obj 361 224 unpack 0 0;
#X msg 361 178 1 0;
#X msg 412 196 0 1;
#X obj 463 93 select 0;
#X obj 361 71 select asc desc;
#X obj 40 437 outlet;
#X obj 153 437 outlet;
#X obj 153 271 spigot 1;
#X obj 317 273 spigot;
#X obj 361 45 r \$0-direction;
#X obj 256 437 outlet;
#X obj 317 437 outlet;
#X connect 0 0 2 0;
#X connect 0 0 3 0;
#X connect 1 0 11 0;
#X connect 1 0 12 0;
#X connect 2 0 9 0;
#X connect 3 0 14 0;
#X connect 4 0 2 1;
#X connect 4 0 11 1;
#X connect 4 1 3 1;
#X connect 4 1 12 1;
#X connect 5 0 4 0;
#X connect 6 0 4 0;
#X connect 7 0 5 0;
#X connect 7 1 6 0;
#X connect 8 0 5 0;
#X connect 8 1 6 0;
#X connect 8 2 7 0;
#X connect 11 0 10 0;
#X connect 12 0 15 0;
#X connect 13 0 8 0;
#X restore 105 135 pd >or<?;
#X obj 105 163 <;
#X obj 135 162 >;
#X obj 144 207 r \$0-left-pointer;
#X obj 114 243 f;
#X connect 0 0 4 0;
#X connect 2 0 9 0;
#X connect 3 0 5 1;
#X connect 4 0 5 0;
#X connect 5 0 6 0;
#X connect 5 1 6 1;
#X connect 5 2 7 0;
#X connect 5 3 7 1;
#X connect 6 0 2 0;
#X connect 7 0 2 0;
#X connect 8 0 9 1;
#X connect 9 0 1 0;
#X restore 235 231 pd \$0-pivot-order?;
#X obj 280 264 r \$0-right-index;
#X text 502 225 <== Don't swap if the last left pointer points to a
value that is already in order with the pivot.;
#X text 539 310 <== When the last left pointer is adjacent to the pivot
(on the right) \, schedule the left pointer for the next partition.
;
#X connect 0 0 4 0;
#X connect 1 0 9 0;
#X connect 3 0 7 0;
#X connect 4 0 3 0;
#X connect 5 0 7 0;
#X connect 6 0 14 0;
#X connect 9 0 8 0;
#X connect 9 1 6 0;
#X connect 9 2 2 0;
#X connect 10 0 4 1;
#X connect 11 0 6 1;
#X connect 12 0 3 1;
#X connect 13 0 15 1;
#X connect 14 0 16 0;
#X connect 14 1 15 0;
#X connect 14 2 8 1;
#X connect 15 0 8 1;
#X connect 16 0 5 0;
#X connect 17 0 5 1;
#X restore 64 630 pd \$0-tail;
#X text 143 632 <== put the rest here to save space;
#X connect 0 0 10 0;
#X connect 1 0 6 1;
#X connect 2 0 13 0;
#X connect 3 0 5 1;
#X connect 3 0 22 0;
#X connect 4 0 19 0;
#X connect 5 0 3 0;
#X connect 6 0 7 0;
#X connect 7 0 9 0;
#X connect 8 0 11 0;
#X connect 9 0 8 0;
#X connect 9 1 24 0;
#X connect 10 0 5 1;
#X connect 10 1 4 0;
#X connect 10 1 29 0;
#X connect 11 0 30 0;
#X connect 11 1 30 1;
#X connect 12 0 6 1;
#X connect 13 0 14 0;
#X connect 13 1 17 0;
#X connect 14 0 15 0;
#X connect 15 0 6 0;
#X connect 15 1 5 0;
#X connect 16 0 14 1;
#X connect 18 0 1 0;
#X connect 18 0 0 0;
#X connect 20 0 3 1;
#X connect 21 0 7 1;
#X connect 23 0 8 1;
#X connect 25 0 12 0;
#X restore 109 435 pd \$0-partition-loop;
#X obj 401 412 r \$0-swap;
#N canvas 670 232 607 336 \$0-manual-sort 0;
#X obj 27 58 inlet;
#N canvas 207 434 411 426 \$0-sort-2 0;
#X obj 49 78 inlet;
#X obj 49 100 t b b;
#X obj 49 128 v \$0-left;
#X obj 296 117 v \$0-right;
#X obj 49 184 tabread \$0-table;
#X obj 167 184 tabread \$0-table;
#X obj 197 327 tabwrite \$0-table;
#X obj 49 327 tabwrite \$0-table;
#N canvas 399 288 584 529 swap? 0;
#X obj 40 52 inlet;
#X obj 153 52 inlet;
#X obj 40 272 spigot 1;
#X obj 256 272 spigot;
#X obj 361 224 unpack 0 0;
#X msg 361 178 1 0;
#X msg 412 196 0 1;
#X obj 463 93 select 0;
#X obj 361 71 select asc desc;
#X obj 40 437 outlet;
#X obj 153 437 outlet;
#X obj 256 300 swap;
#X obj 153 271 spigot 1;
#X obj 317 273 spigot;
#X obj 361 45 r \$0-direction;
#X connect 0 0 2 0;
#X connect 0 0 3 0;
#X connect 1 0 12 0;
#X connect 1 0 13 0;
#X connect 2 0 9 0;
#X connect 3 0 11 0;
#X connect 4 0 2 1;
#X connect 4 0 12 1;
#X connect 4 1 3 1;
#X connect 4 1 13 1;
#X connect 5 0 4 0;
#X connect 6 0 4 0;
#X connect 7 0 5 0;
#X connect 7 1 6 0;
#X connect 8 0 5 0;
#X connect 8 1 6 0;
#X connect 8 2 7 0;
#X connect 11 0 9 0;
#X connect 11 1 10 0;
#X connect 12 0 10 0;
#X connect 13 0 11 1;
#X connect 14 0 8 0;
#X restore 152 296 pd swap?;
#X obj 152 273 min;
#X obj 197 273 max;
#X obj 49 205 t f f;
#X obj 49 155 t f f;
#X text 46 47 This one is easy. =o);
#X connect 0 0 1 0;
#X connect 1 0 2 0;
#X connect 1 1 3 0;
#X connect 2 0 12 0;
#X connect 3 0 6 1;
#X connect 3 0 5 0;
#X connect 4 0 11 0;
#X connect 5 0 9 1;
#X connect 5 0 10 1;
#X connect 8 0 7 0;
#X connect 8 1 6 0;
#X connect 9 0 8 0;
#X connect 10 0 8 1;
#X connect 11 0 9 0;
#X connect 11 1 10 0;
#X connect 12 0 4 0;
#X connect 12 1 7 1;
#X restore 27 146 pd \$0-sort-2;
#N canvas 335 422 791 492 \$0-sort-3 0;
#X obj 39 23 inlet;
#X obj 39 45 t b b;
#X obj 39 73 v \$0-left;
#X obj 462 62 v \$0-right;
#X obj 306 130 - 1;
#X obj 207 415 tabwrite \$0-table;
#X obj 45 429 tabwrite \$0-table;
#X obj 363 333 tabwrite \$0-table;
#N canvas 399 288 584 529 swap? 0;
#X obj 40 52 inlet;
#X obj 153 52 inlet;
#X obj 40 272 spigot 1;
#X obj 256 272 spigot;
#X obj 361 224 unpack 0 0;
#X msg 361 178 1 0;
#X msg 412 196 0 1;
#X obj 463 93 select 0;
#X obj 361 71 select asc desc;
#X obj 40 437 outlet;
#X obj 153 437 outlet;
#X obj 256 300 swap;
#X obj 153 271 spigot 1;
#X obj 317 273 spigot;
#X obj 361 45 r \$0-direction;
#X connect 0 0 2 0;
#X connect 0 0 3 0;
#X connect 1 0 12 0;
#X connect 1 0 13 0;
#X connect 2 0 9 0;
#X connect 3 0 11 0;
#X connect 4 0 2 1;
#X connect 4 0 12 1;
#X connect 4 1 3 1;
#X connect 4 1 13 1;
#X connect 5 0 4 0;
#X connect 6 0 4 0;
#X connect 7 0 5 0;
#X connect 7 1 6 0;
#X connect 8 0 5 0;
#X connect 8 1 6 0;
#X connect 8 2 7 0;
#X connect 11 0 9 0;
#X connect 11 1 10 0;
#X connect 12 0 10 0;
#X connect 13 0 11 1;
#X connect 14 0 8 0;
#X restore 188 316 pd swap?;
#X obj 188 293 min;
#X obj 233 293 max;
#N canvas 399 288 584 529 swap? 0;
#X obj 40 52 inlet;
#X obj 153 52 inlet;
#X obj 40 272 spigot 1;
#X obj 256 272 spigot;
#X obj 361 224 unpack 0 0;
#X msg 361 178 1 0;
#X msg 412 196 0 1;
#X obj 463 93 select 0;
#X obj 361 71 select asc desc;
#X obj 40 437 outlet;
#X obj 153 437 outlet;
#X obj 256 300 swap;
#X obj 153 271 spigot 1;
#X obj 317 273 spigot;
#X obj 361 45 r \$0-direction;
#X connect 0 0 2 0;
#X connect 0 0 3 0;
#X connect 1 0 12 0;
#X connect 1 0 13 0;
#X connect 2 0 9 0;
#X connect 3 0 11 0;
#X connect 4 0 2 1;
#X connect 4 0 12 1;
#X connect 4 1 3 1;
#X connect 4 1 13 1;
#X connect 5 0 4 0;
#X connect 6 0 4 0;
#X connect 7 0 5 0;
#X connect 7 1 6 0;
#X connect 8 0 5 0;
#X connect 8 1 6 0;
#X connect 8 2 7 0;
#X connect 11 0 9 0;
#X connect 11 1 10 0;
#X connect 12 0 10 0;
#X connect 13 0 11 1;
#X connect 14 0 8 0;
#X restore 45 398 pd swap?;
#X obj 45 375 min;
#X obj 90 375 max;
#N canvas 399 288 584 529 swap? 0;
#X obj 40 52 inlet;
#X obj 153 52 inlet;
#X obj 40 272 spigot 1;
#X obj 256 272 spigot;
#X obj 361 224 unpack 0 0;
#X msg 361 178 1 0;
#X msg 412 196 0 1;
#X obj 463 93 select 0;
#X obj 361 71 select asc desc;
#X obj 40 437 outlet;
#X obj 153 437 outlet;
#X obj 256 300 swap;
#X obj 153 271 spigot 1;
#X obj 317 273 spigot;
#X obj 361 45 r \$0-direction;
#X connect 0 0 2 0;
#X connect 0 0 3 0;
#X connect 1 0 12 0;
#X connect 1 0 13 0;
#X connect 2 0 9 0;
#X connect 3 0 11 0;
#X connect 4 0 2 1;
#X connect 4 0 12 1;
#X connect 4 1 3 1;
#X connect 4 1 13 1;
#X connect 5 0 4 0;
#X connect 6 0 4 0;
#X connect 7 0 5 0;
#X connect 7 1 6 0;
#X connect 8 0 5 0;
#X connect 8 1 6 0;
#X connect 8 2 7 0;
#X connect 11 0 9 0;
#X connect 11 1 10 0;
#X connect 12 0 10 0;
#X connect 13 0 11 1;
#X connect 14 0 8 0;
#X restore 185 231 pd swap?;
#X obj 185 208 min;
#X obj 230 208 max;
#X obj 351 79 t f f;
#X obj 39 126 tabread \$0-table;
#X obj 185 147 tabread \$0-table;
#X obj 343 130 tabread \$0-table;
#X obj 185 172 t f f;
#X obj 39 97 t f f;
#X obj 39 150 t f f;
#X obj 45 333 t f f;
#X text 478 216 <== Sort right and center.;
#X text 478 296 <== Sort left and right -- right is now ready.;
#X text 478 378 <== Sort left and center -- both are ready.;
#X connect 0 0 1 0;
#X connect 1 0 2 0;
#X connect 1 1 3 0;
#X connect 2 0 22 0;
#X connect 3 0 20 0;
#X connect 3 0 7 1;
#X connect 3 0 17 0;
#X connect 4 0 5 1;
#X connect 4 0 19 0;
#X connect 8 0 24 0;
#X connect 8 1 7 0;
#X connect 9 0 8 0;
#X connect 10 0 8 1;
#X connect 11 0 6 0;
#X connect 11 1 5 0;
#X connect 12 0 11 0;
#X connect 13 0 11 1;
#X connect 14 0 13 1;
#X connect 14 0 12 1;
#X connect 14 1 10 1;
#X connect 14 1 9 1;
#X connect 15 0 14 0;
#X connect 16 0 14 1;
#X connect 17 0 4 0;
#X connect 17 1 20 0;
#X connect 18 0 23 0;
#X connect 19 0 21 0;
#X connect 20 0 16 1;
#X connect 20 0 15 1;
#X connect 21 0 15 0;
#X connect 21 1 16 0;
#X connect 22 0 18 0;
#X connect 22 1 6 1;
#X connect 23 0 9 0;
#X connect 23 1 10 0;
#X connect 24 0 12 0;
#X connect 24 1 13 0;
#X restore 66 120 pd \$0-sort-3;
#X obj 27 92 moses 2;
#X text 24 19 Here we manually sort partitions of size 2 or 3 This
should be more efficient than scheduling extra partitioning.;
#X connect 0 0 3 0;
#X connect 3 0 1 0;
#X connect 3 1 2 0;
#X restore 97 466 pd \$0-manual-sort;
#X obj 70 291 -;
#X obj 70 323 moses 3;
#X obj 109 349 moses 4;
#X obj 148 380 t b b;
#X obj 109 380 t b;
#X text 501 460 <== swapping engine;
#X text 172 346 <== no need to find pivot for partitions of size 4
\, since both partitions of the next round will be sorted manually.
;
#X msg 89 63 0 \$1;
#X obj 401 437 unpack 0 0;
#X obj 203 34 r \$0-schedule;
#X obj 70 37 t b f b;
#X obj 70 140 until;
#X obj 70 349 t b f;
#X obj 70 498 s \$0-schedule;
#X obj 70 170 t b b;
#X obj 70 263 swap;
#X text 131 317 <== more efficient to manually sort partitions of size
3 or smaller (especially for larger lists).;
#N canvas 464 376 995 572 \$0-queue 0;
#X obj 47 109 inlet;
#X obj 47 510 outlet;
#X obj 238 479 outlet;
#X obj 47 188 list-len;
#X obj 248 175 s \$0-queue-table;
#X obj 74 158 list prepend 0;
#X obj 47 131 t a a;
#X obj 477 33 table \$0-queue-table 200;
#X obj 248 110 inlet;
#X msg 248 142 const 0;
#X obj 238 430 == 0;
#X obj 238 453 sel 1;
#X obj 211 382 tabread \$0-queue-table;
#X obj 47 382 tabread \$0-queue-table;
#X obj 74 335 + 1;
#X obj 211 407 t f f;
#X obj 177 280 f;
#X obj 47 282 f;
#X obj 250 280 +;
#X obj 76 282 + 2;
#X msg 192 127 0;
#X obj 47 212 t b b f;
#X obj 495 121 list split 2;
#X obj 495 99 list prepend;
#X text 493 68 [inlet];
#X text 496 80 |;
#X text 557 68 [inlet];
#X text 560 80 |;
#X text 493 217 |;
#X text 491 231 [outlet];
#X text 583 156 |;
#X text 581 170 [outlet];
#X obj 584 138 t b;
#X text 624 93 <== this is an equivalent construction using a [list]
sequence.;
#X text 370 378 <== after the index for the current partition is passed
\, grab the two adjacent values and pass them out.;
#X obj 211 510 outlet;
#X obj 495 200 unpack 0 0;
#X text 550 216 |;
#X text 548 230 [outlet];
#X text 292 276 <== Two counters \, one to supply partition boundary
locations for writing (right) \, and one for reading (left).;
#X text 111 312 <== (no trigger needed as both sides lead to cold inlets)
;
#X text 308 429 <== as long as there is a partition \, the right value
should never == 0... if it does \, the table is sorted \, so we stop
the main loop and send out the list.;
#X text 49 11 This is the schedule queue for partitions. It would take
much less code to do this with a [list] sequence instead of a table
\, but the table is faster. The [list] sequence is also easier to understand
at first. The size of the table needs to be \, in the worst case \,
2(n-1) where n is the size of the list to be sorted. In this case we
simply use 2n \, as we need some zeroes at the end. This could probably
be done better.;
#X connect 0 0 6 0;
#X connect 3 0 21 0;
#X connect 5 0 4 0;
#X connect 6 0 3 0;
#X connect 6 1 5 0;
#X connect 8 0 9 0;
#X connect 8 0 20 0;
#X connect 9 0 4 0;
#X connect 10 0 11 0;
#X connect 11 0 2 0;
#X connect 12 0 15 0;
#X connect 13 0 1 0;
#X connect 14 0 12 0;
#X connect 15 0 35 0;
#X connect 15 1 10 0;
#X connect 16 0 18 0;
#X connect 17 0 19 0;
#X connect 17 0 14 0;
#X connect 17 0 13 0;
#X connect 18 0 16 1;
#X connect 18 0 5 1;
#X connect 19 0 17 1;
#X connect 20 0 17 1;
#X connect 20 0 16 1;
#X connect 20 0 5 1;
#X connect 21 0 17 0;
#X connect 21 1 16 0;
#X connect 21 2 18 1;
#X connect 22 0 36 0;
#X connect 22 1 23 1;
#X connect 22 2 32 0;
#X connect 23 0 22 0;
#X restore 203 80 pd \$0-queue;
#X text 216 229 <== values used in each partition and every loop --
easier to store a value than to send it.;
#X text 166 500 <== send a bang to the scheduler if we've just manually
sorted something. A bang will not add a partition to the queue \, but
will increment the index to grab the next partition.;
#X text 284 80 <== the "queue" for scheduling partitions.;
#X connect 0 0 18 0;
#X connect 1 0 23 0;
#X connect 2 0 23 1;
#X connect 6 0 16 0;
#X connect 8 0 9 0;
#X connect 9 0 20 0;
#X connect 9 1 10 0;
#X connect 10 0 12 0;
#X connect 10 1 11 0;
#X connect 11 0 5 0;
#X connect 11 1 4 0;
#X connect 12 0 5 0;
#X connect 15 0 25 0;
#X connect 16 0 3 0;
#X connect 16 1 3 1;
#X connect 17 0 25 0;
#X connect 18 0 19 0;
#X connect 18 1 15 0;
#X connect 18 2 25 1;
#X connect 19 0 22 0;
#X connect 20 0 21 0;
#X connect 20 1 7 0;
#X connect 22 0 1 0;
#X connect 22 1 2 0;
#X connect 23 0 8 0;
#X connect 23 1 8 1;
#X connect 25 0 1 0;
#X connect 25 1 2 0;
#X connect 25 2 19 1;
#X restore 264 249 pd \$0-main-loop;
#X text 51 25 Sort a list of numbers using a quicksort.;
#X connect 0 0 8 0;
#X connect 2 0 4 0;
#X connect 3 0 5 0;
#X connect 4 0 6 0;
#X connect 5 0 4 0;
#X connect 5 1 4 1;
#X connect 7 2 21 0;
#X connect 8 0 19 0;
#X connect 8 1 9 0;
#X connect 9 0 8 1;
#X connect 11 0 7 0;
#X connect 11 1 10 0;
#X connect 12 0 1 0;
#X connect 13 0 16 0;
#X connect 14 0 13 0;
#X connect 15 0 14 1;
#X connect 16 0 12 0;
#X connect 18 0 11 0;
#X connect 19 0 14 0;
#X connect 19 1 18 0;
#X connect 21 0 22 0;