OLD | NEW |
| (Empty) |
1 // quicksort | |
2 | |
3 function sort_quick(sort, left, right) { | |
4 if (arguments.length == 1) { | |
5 left = 0; | |
6 right = sort.size - 1; | |
7 } | |
8 if (left < right) { | |
9 var pivot = left + Math.floor(Math.random()*(right-left)); | |
10 //var pivot = Math.floor(left + (right-left)/2); | |
11 partition(sort, left, right, pivot); | |
12 } | |
13 } | |
14 | |
15 function partition(sort, left, right, pivot) { | |
16 sort.swap(pivot, right); | |
17 sort.add_work(function(){partition_step(sort, left, right, pivot, left, left);
}); | |
18 } | |
19 | |
20 function partition_step(sort, left, right, pivot, i, j) { | |
21 if (i < right) { | |
22 if (sort.compare(i, right) <= 0) { | |
23 sort.swap(i, j); | |
24 j++; | |
25 } | |
26 i++; | |
27 sort.add_work(function(){partition_step(sort, left, right, pivot, i, j)}); | |
28 } else { | |
29 sort.swap(j, right); | |
30 sort.add_work(function(){sort_quick(sort, left, j-1)}); | |
31 sort.add_work(function(){sort_quick(sort, j+1, right)}); | |
32 } | |
33 } | |
34 | |
OLD | NEW |