CodeCrack CodeCrack - 3 months ago 11
Javascript Question

Why isn's this QuickSort with randomized pivot working right?

For some reason if I use end or mid pivot, the algorithm works properly but if I used a randomized pivot using Math.random(), the results show up wrong and different each time.

function quick_sort(A, start, end) {
if (start < end) {
var pIndex = partition(A, start, end);
quick_sort(A, start, pIndex - 1);
quick_sort(A, pIndex + 1, end);
}
}

function partition(A, start, end) {
var randomIndex = Math.floor(Math.random() * end + 1);
swap(A, randomIndex, end);
var pivot = A[end];
var pIndex = start;

for (var i = start; i < end; i++) {
if (A[i] <= pivot) {
swap(A, pIndex, i);
pIndex++;
}
}
swap(A,end, pIndex);
return pIndex;
}

function swap(A, i, j) {
var tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}

var A = [12,-3, -123, 0, 11, 1, 2, 6, 4];
console.log(A);
quick_sort(A,0, A.length-1);
console.log(A);


Output

~ node test.js
[ 12, -3, -123, 0, 11, 1, 2, 6, 4 ]
[ -123, -3, 0, 1, 6, 4, 2, 11, 12 ]
~ node test.js
[ 12, -3, -123, 0, 11, 1, 2, 6, 4 ]
[ -123, 4, 0, 6, -3, 1, 2, 11, 12 ]

Answer

This line is incorrect:

var randomIndex = Math.floor(Math.random() * end + 1);

Because you're selecting a pivot in [1 ... end] without taking the start index into account. (The start index can be anywhere in the array when the call quick_sort(A, pIndex + 1, end) is processed.)

It should be:

var randomIndex = Math.floor(start + Math.random() * (end - start + 1));
Comments