Best case of pairwise comparisons of an array with 6 elements, using quicksort

Question

I am analysing the following question:

Question 5B

Assume that you use quicksort to sort an array with 6 elements, and use the first element as pivot. How many pairwise comparisons will be made...

    a) ...in the worst case? Answer: 15 (5+4+3+2+1) and 20 (6+5+4+3+2) are accepted

    b) ...in the worst case? Answer: 8 (5+2+1), 10 (6+3+1) and 11 (6+3+2) are accepted

I am trying to understand the answer "8 (5+2+1)". I can't visualize a best case of 8 comparisons. If the array for example is [4,1,2,3,5,6] (pivot is 4), it checks 1-6, 2-6, 3-6, 5-6 and then swap 5 and 4 and then there are two subarrays [1,2,3] and [5,6] which has 2 and 1 comparisons?

Can someone please give an example and show how the best case can be 8 comparisons?

I tried different orders and searched on the web...

Answer 1

With Lomuto's Quicksort algorithm, using the leftmost value as pivot value, we can get as low as 8 comparisons for an array like [3, 1, 2, 5, 4, 6].

In the first iteration all values will be compared with the pivot 3 (5 comparisons), and the pivot will be moved: swapped with 2, and we get:

[2, 1, 3, 5, 4, 6]

The deeper run will have the left partition [2, 1], where only 1 comparison is needed, and the pivot 2 will move to where the 1 is.

The right partition [5, 4, 6] will need 2 comparisons and put the pivot value 5 in the middle.

That leaves us with partitions that have size 1, so no comparisons occur.

Here is a JavaScript implementation of that Lomuto Quicksort algorithm, which perofrms the sort for the above mentioned array and outputs the most relevant actions to confirm 8 comparisons are needed:

// Lomuto algorithm, with pivot at left side
function quickSort(arr, low, high) {

    function partition(arr, low, high) {
        let count = 0;
        const pivot = arr[low];
        let i = low;
        for (let j = low + 1; j <= high; j++) {
            count++; // Count next comparison
            console.log("compare", arr[j], "with pivot", pivot);
            if (arr[j] <= pivot) {
                i++;
                console.log("set partition index at", i);
                if (i < j) {
                    console.log("swap index", i, "with index", j);
                    [arr[i], arr[j]] = [arr[j], arr[i]];
                    console.log("swap result: ", ...arr);
                }
            }
        }
        console.log("swap pivot", pivot, "with partition index", i);
        [arr[i], arr[low]] = [arr[low], arr[i]];
        console.log("swap result: ", ...arr);
        return [i, count];
    }
    if (low >= high) return 0;
    
    const [i, count] = partition(arr, low, high);
    return count + quickSort(arr, low, i - 1) + quickSort(arr, i + 1, high);
}

const arr = [3, 1, 2, 5, 4, 6];
console.log("INITIAL:", ...arr);
const count = quickSort(arr, 0, arr.length - 1);
console.log("SORTED:", ...arr);
console.log("COMPARISONS:", count);