CODEWITHSUNDEEP
javascriptarraysalgorithmperformancequicksort
Viet
Viet

Reputation: 6943

Big O question for QuickSort with Javascript

I'm working with QuickSort and I tested these 2 algorithms on LeetCode for this problem. Both algorithms work, but one seems to be significantly faster than the other one and I don't understand why.

This one exceeds time limit of LeetCode:

function quickSort(array) {
    quickSortHelper(array, 0, array.length - 1);
    return array;
}

function quickSortHelper(array, start, end) {
    // Edge case
    if(start >= end) return;
    // Always choose the pivot index at the beginning of the array.
    const pivot = start;
    // The left index is next to the pivot on the right.
    let left = start + 1;
    let right = end;

    while (right >= left) {
        if (array[left] > array[right] && array[right] < array[pivot])
            swap(left, right, array);
        if (array[left] < array[pivot]) left += 1;
        if (array[right] > array[pivot]) right -= 1;
    }

    swap(pivot, right, array);

    // Always sort the smaller sub-array first
    const leftIsSmaller = right - 1 - start < end - (right + 1);

    if (leftIsSmaller) {
        quickSort(array, start, right - 1);
        quickSort(array, right + 1, end);
    }
    else {
        quickSort(array, right + 1, end);
        quickSort(array, start, right - 1);
    }
}

function swap(a, b, array) {
    [array[a], array[b]] = [array[b], array[a]];
    return array;
}

Big O:

This one doesn't exceed LeetCode time limit and it's significantly faster than most of the submissions. The 2 while loops inside the big while loop (to me) seem to be slower but it's actually faster.

function quickSort(array) {
    sortHelper(array, 0, array.length - 1);
    return array;
}

function sortHelper(array, start, end) {
    if (start >= end) return;
    let i = start;
    let j = end;
    let base = array[i];

    while (i < j) {
        while (i < j && array[j] >= base) j -= 1; // This makes sense but why this while loop has to happen before the other while loop?
        array[i] = array[j]; // this line
        while (i < j && array[i] <= base) i += 1;
        array[j] = array[i]; // and this line. don't they make you lose access to the values in the array?
    }
    array[i] = base;
    sortHelper(array, start, i - 1);
    sortHelper(array, i + 1, end);
}

Why is that?

Upvotes: 3

Views: 164

Answers (1)

trincot
trincot

Reputation: 350137

There is no difference in time complexity, but the first version often performs the same (or opposite) data comparisons more than once. This is not happening in the second version.

For example, imagine that for the following if, the first expression is true, and the second false, and this during several iterations:

 if (array[left] > array[right] && array[right] < array[pivot])

...then it really is a waste that this first expression is checked that many times, given that left does not change from one iteration to the next when this first expression is true.

Take for example this extreme example array: [1, 6, 3, 2, 5, 4]

The pivot is 1.

During all iterations the right index will decrease until it reaches the left side. The number of comparisons per iteration is 4, and so for the 5 iterations together it is 20.

Now look at the faster algorithm. There the number of comparisons for the same input is 5 for the first inner loop and 0 for the second inner loop (I only count data comparisons).

This is an extreme example (20 versus 5), but it happens to a less degree also with more random inputs.

Upvotes: 3

Related Questions