CODEWITHSUNDEEP
algorithmsortingquicksort
James Franks
James Franks

Reputation: 63

Quicksorting an array of the same numbers

I'm attempting to learn the workings of the Quicksort algorithm. I'm doing this by reading the CLR algorithms book. I can't seem to figure out how the algorithm works for an array of the same numbers and I wasn't able to find any examples online. For example what would the progression of the quicksort algorithm be for this:

{5h, 5i, 5j, 5k, 5m, 5n}

where the characters (h,i,j,k,m,n) are merely there to differentiate between the various 5's Thanks in advance for your assistance!

Upvotes: 2

Views: 154

Answers (2)

goat
goat

Reputation: 31813

That damn book could have been much easier to digest had they used sensible variable names, but I guess they didn't want to diverge from the normal single letter variable convention used for all the math.

I tried to keep their function and variables names and pretty much copy the code, including the "arrays start at 1" convention they use. I mimicked the non random pivot version.

demo: http://jsfiddle.net/p7R99/

or just put the following in a .html file

<pre id="out">
</pre>

<script>
function QUICKSORT(A, p, r) {
    if (p < r) {
        var q = PARTITION(A, p, r);
        output("q=" + q + " and A=" + arr(A) + "\n");
        QUICKSORT(A, p, q - 1);
        QUICKSORT(A, q + 1, r);
    }
}

function PARTITION(A, p, r) {
    var x = A[r];
    var i = p - 1;
    for (var j = p; j < r - 1; j++) {
        if (intval(A[j]) <= intval(x)) {
            i = i + 1;
            swap(A, i, j);
        }
    }
    swap(A, i + 1, r);
    return i + 1;
}

function intval(str) {
    return parseInt(str, 10);
}



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

function output(msg) {
    var ele = document.getElementById("out");
    ele.innerHTML += msg;
}
function arr(A) {
    return A.slice(1).join(" ");
}


var A = [undefined, "5h", "5i", "5j", "5k", "5m", "5n"];
QUICKSORT(A, 1, A.length);
</script>

result

q=1 and A= 5i 5j 5k 5m 5n 5h
q=6 and A= 5i 5j 5k 5m 5h 5n
q=4 and A= 5i 5j 5m 5k 5h 5n
q=2 and A= 5j 5i 5m 5k 5h 5n

Upvotes: 1

Arun Manivannan
Arun Manivannan

Reputation: 4313

This is one of the few cases when quicksort could give a O (n^2) performance since (with a less careful implementation) there is a possibility that one of your partition might end up being empty.

If you know about the input before hand and they are mostly same, you might want to consider Counting sort or a three way quicksort

Upvotes: 0

Related Questions