Click here to Skip to main content
15,867,453 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
Hi all,
I've been wrestling with a quicksort implementation in JavaScript all day. I've almost got it, but I seem to be missing something...
I want the algorithm to be stable (i.e. the relative order of items with the same key is kept).
It currently seems everything gets sorted save for a single item. I've been looking for the problem, but I can't find it.
I'm pretty sure it has something to do with the while loops though (the commented whiles are the raw quicksort implementations, which work, the current ones should make it stable). The idea is that items that are equal to the pivot do not get switched around, but now we have to check if the current index isn't the pivot.

Any help is greatly appreciated, thanks!
HTML
<script>
    function quicksort (items, map, startIndex, endIndex, compare) {
        var low = startIndex;
        var high = endIndex;
        var pindex = Math.floor((low + high) / 2);
        var pivot = map[pindex];

        while (low <= high) {
            while (items[map[low]].value <= items[pivot].value && low < pindex) {
            //while (items[map[low]].value < items[pivot].value) {
                low += 1;
            }
            while (items[map[high]].value >= items[pivot].value && high > pindex) {
            //while (items[map[high]].value > items[pivot].value) {
                high -= 1;
            }
            if (low <= high) {
                var temp = map[low];
                map[low] = map[high];
                map[high] = temp;
                low += 1;
                high -= 1;
            }
        }

        if (low < endIndex) {
            quicksort(items, map, low, endIndex);
        }
        if (high > startIndex) {
            quicksort(items, map, startIndex, high);
        }
    }

    // test above code.
    var size = 7;
    var ints = new Array(size);
    var intMap = new Array(size);
    var i = 0;
    for (i; i < size; i += 1) {
    	ints[i] = {
    		id: i,
    		value: Math.floor((Math.random() * 10) + 1)
    	};
    	intMap[i] = i;
    }
    ints[4].value = ints[size - 1].value;
    quicksort(ints, intMap, 0, size - 1);
    var sorted = intMap.map(function (i) {
    	return ints[i];
    });
    // Sorted should be sorted by value and then id,
    // there is at least one double value.
    // In my tests a single value is unsorted every time.
</script>


What I have tried:

Been debugging all day, been looking at other implementations on various websites, tried different implementations, asked this question here on CP.
Posted
Updated 30-Oct-16 7:06am
v2

Found it!
After hours of trying I decided to leave the problem alone for a while and now, after a few weeks, I fixed it in like 5 minutes.
The while loops should look like this:
C#
while (items[map[low]].value < items[pivot].value || (items[map[low]].value === items[pivot].value && map[low] < pivot)) {
    low += 1;
}
while (items[map[high]].value > items[pivot].value || (items[map[high]].value === items[pivot].value && map[high] > pivot)) {
    high -= 1;
}
The idea is that when an item has the same value as the pivot it only gets moved when the original index (contained in map) is lower or higher than the pivot respectively.

I can't believe I've wasted hours looking for this... :doh:
 
Share this answer
 
Quote:
Been debugging all day
This sentence tells that you don't know how to use the debugger.
The debugger will not find bugs by magic ! it only allow you to see what your code is doing !
You have to take advantage of it!

Quote:
I want the algorithm to be stable (i.e. the relative order of items with the same key is kept).

First, if you look at documentation Quicksort - Wikipedia[^], you will see that by definition, QuickSort is not stable !

Advices:
- This:
JavaScript
var i = 0;
for (i; i < size; i += 1) {

should be rewritten as:
JavaScript
for (i=0; i < size; i += 1) {

or
JavaScript
for (i=0; i < size; i ++) {

because it is considered easier to read.
- You should write a wrapping function which take a list as parameter and return a sorted list as result. It simplify reuse and testing.
-Take a sheet of paper build a test list and plan what would do the program to solve the problem, then, as you run the test, use the debugger to check if the program behave as expected.
Start with small test lists:
{1}
{1, 5}
{5, 1}
{1, 4, 9}
{1, 9, 4}
{4, 1, 9}
{9, 4, 1}
...

[UpDate]
Why do you have this line ?
JavaScript
ints[4].value = ints[size - 1].value;

For me, it kills ints[4].

I have doubt about your test to pindex on the 2 while loops.
[UpDate]
Try to sort this sequence: {0, 2, 4, 6, 1, 3, 5}
If there is a problem, it will confirm the doubt I expressed in previous update.
Let me know the result.
 
Share this answer
 
v6
Comments
Sander Rossel 17-Oct-16 11:33am    
So... Your advice is to "fix" a while loop (that isn't even in my algorithm) and keep trying? That's not really the "help" I was hoping for...

I do know how debuggers work (and, unfortunately, Chrome is not my definition of a good debugger), I've successfully used them for years (and sometimes, like now, less successful).
And I also know quicksort in its simplest form isn't stable, hence my attempt to get it that way.
I guess I'll try again tonight with a fresh look on the matter.
Patrice T 17-Oct-16 18:05pm    
Where did I said a "while loop" ?
Sander Rossel 18-Oct-16 3:09am    
for*...
Sander Rossel 18-Oct-16 7:14am    
I just noticed your update.
I'm simply setting the value of ints[4] to that of ints[size - 1] to assure I have a duplicate value (with different id's).
For debugging purposes it's easier to have a fixed list rather than Math.random(), but I just wrote the example to show that the algorithm doesn't work.
The problem is with the quicksort function, not the code that tests it.

I'm actually starting to think the problem may be that if the values are the same, but the indexes aren't I should not only not skip the value, but also check if the index is higher or lower and then swap based on that. I tried it, but it didn't work, so perhaps I'm missing something else as well.
What I'm not missing is the headache this gives me though... Algorithms never was my strong point.

I've currently got another, much slower, implementation that's stable, but not quite so quick...
Chris Maunder 30-Oct-16 13:55pm    
Is a comment "This sentence tells that you don't know how to use the debugger" really necessary? Does it help provide an answer? Or is it merely there to make the poster feel bad?

If the question is bad, delete it or edit it to make it better.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900