| 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 |