CODEWITHSUNDEEP
typescriptalgorithmpartitioningquickselect
Rando Coder
Rando Coder

Reputation: 83

Issue implementing Hoare's algorithm in Typescript

While trying to create a QuickSelect algorithm, I have decided to implement it using Hoare's partition scheme as shown below:

function partition<ElementType>(array: Array<ElementType>, startIndex: number, endIndex: number) {
    // const pivotValue = array[Math.floor(Math.random() * (endIndex - startIndex  + 1)) + startIndex];
    const pivotValue = array[startIndex];

    var leftIndex = startIndex - 1;
    var rightIndex = endIndex + 1;

    while (true) {
        ++leftIndex;
        while (array[leftIndex] < pivotValue)
            ++leftIndex;

        --rightIndex;
        while (array[rightIndex] > pivotValue)
            --rightIndex;

        if (leftIndex >= rightIndex)
            return rightIndex;

        const aux = array[leftIndex];
        array[leftIndex] = array[rightIndex];
        array[rightIndex] = aux;
    }
}

Because I had issues with its results, I switched the pivot from a random value to the leftmost in the array to make it deterministic and follow the wiki implementation.

However when calling the function on the array [2, 1, 6, 2, 5] (with startIndex=0 and endIndex=4), the function seems to return 1, and the array unchanged, which according to my understanding should mean that the element at index 1 (1) is in its final place in the array. However this is not correct, as obviously its index should be 0. Following the wiki implementation by hand and also debugging, this seems to be the correct behaviour of the algorithm, which means I have either made an error during implementation or my understanding of what the algorithm does is wrong. My question is which one is it, and why?

Upvotes: 0

Views: 36

Answers (0)

Related Questions