1// quicksort 2 3function 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 15function 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 20function 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 35