Skip to content

Instantly share code, notes, and snippets.

@springuper
Created December 1, 2012 13:41
Show Gist options
  • Save springuper/4182296 to your computer and use it in GitHub Desktop.
Save springuper/4182296 to your computer and use it in GitHub Desktop.
quick sort
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));
@trevnorris
Copy link

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 ]

@springuper
Copy link
Author

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

@JacksonGL
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment