public
Last active

quick sort

  • Download Gist
quicksort.js
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
function swap(items, firstIndex, secondIndex){
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
}
 
function partition(items, left, right) {
var index = Math.floor((right + left) / 2),
pivot = items[index],
i = left,
j = right;
 
while (i < j) { // i <= j to i < j
 
while (items[i] < pivot) {
i++;
}
 
while (items[j] > pivot) {
j--;
}
 
if (i < j) { // i <=j to i < j
swap(items, i, j);
if (i === index) { // update pivot pointer
index = j;
} else if (j === index) {
index = i;
}
 
i++;
j--;
}
}
 
return index; // return i to return index
}
 
function quickSort(items, left, right) {
var index;
 
if (items.length > 1) {
 
index = partition(items, left, right);
 
if (left < index - 1) {
quickSort(items, left, index - 1);
}
 
if (index + 1 < right) { // index < right to index + 1 < right
quickSort(items, index + 1, right); // index to index + 1
}
 
}
 
return items;
}
 
 
console.log(quickSort([1, 2, 3, 4, 5], 0, 4));
console.log(quickSort([5, 4, 3, 2, 1], 0, 4));
console.log(quickSort([2, 2, 2, 2, 2], 0, 4));
console.log(quickSort([2, 3, 1], 0, 2));
console.log(quickSort([2, 1, 3], 0, 2));

你的 index 返回 pivot 的位置,而 Zakas 的返回 pivot 的下一个位置。所以,我能看出来的,此处的 quickSort 和 Zakas 写的唯一的差别就是,前者不会将 pivot 列入下一次的递归中,而后者做了这部分没必要的工作。不过你们都做了一部分没必要的工作,就是 swap 中多了一次赋值。在快排中有种方法可以避免交换,节省循环中的一次赋值……

Haven't been able to determine why yet, but your quick sort is failing in the following:

var arr = [ 0.13837, 0.70843, 0.63302, 0.00802, 0.00141 ];

console.log(quickSort(arr, 0, 4));

// output: [ 0.00141, 0.13837, 0.00802, 0.63302, 0.70843 ]

@trevnorris thanks for the test case, there does exist a problem with the return value of function partition. Pointer i maybe not the right pointer to pivot when an exchange occurs between the pivot and some other item.

I have update the code to fix it, please try. Thank you so much.

Your code still has a bug, you can easily find it if you do random testing

quickSort(items, left, index-1); // here should be quickSort(items, left, index);

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.