快速排序算法中的问题...... [英] Problem in quicksort algorithm...

问题描述

大家好，

我一整天都在用JavaScript快速实施。我几乎得到了它，但我似乎错过了一些东西......

我希望算法稳定（即保持具有相同键的项目的相对顺序）。

目前看来，除了单个项目，所有内容都会被排序。我一直在寻找这个问题，但我找不到它。

我很确定它与while循环有关（评论时是原始的quicksort实现，哪个工作，现在应该使它稳定）。这个想法是，与枢轴相等的项目不会被切换，但现在我们必须检查当前索引是否不是枢轴。



任何非常感谢帮助！谢谢！

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!

<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>

我的尝试：



一直在调试整天，一直在寻找各种网站上的其他实现，尝试了不同的实现，在CP上问这个问题。

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.

推荐答案

找到它！

经过几个小时的尝试后，我决定将问题单独解决一段时间，现在，几周后，我将其固定在5分钟内。

while循环应该是好的就是这样：

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:

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;
}

这个想法是当一个项目与枢轴具有相同的值时，它只会在原始索引（包含在地图中）分别低于或高于枢轴时被移动。 />


我无法相信我浪费时间寻找这个...：doh：

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:

Quote：

一整天调试

这句话告诉你不知道如何使用调试器。

调试器将没有发现魔法的错误！它只允许你看看你的代码在做什么！

你必须利用它！

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!

引用：

我希望算法稳定（即保持具有相同键的项目的相对顺序）。

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

首先，如果您查看文档 Quicksort - Wikipedia [ ^ ]，根据定义，你会看到QuickSort不稳定！



建议：

- 这个：

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

Advices:
- This:

var i = 0;
for (i; i < size; i += 1) {

应改写为：

should be rewritten as:

for (i=0; i < size; i += 1) {

或

or

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

因为它被认为更容易阅读。

- 您应该编写一个包装函数，它将列表作为参数并返回一个排序列表作为结果。它简化了重用和测试。

-拿一张纸构建一个测试列表并计划解决问题的程序，然后，在运行测试时，使用调试器检查是否程序按预期运行。

从小测试列表开始：

{1}

{1,5}

{5,1}

{1,4,9}

{1,9,4}

{4,1， 9}

{9,4,1}

...



[UpDate]

为什么你有这条线？

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 ?

ints[4].value = ints[size - 1].value;

对我而言，它会杀死整数[ 4] 。



我怀疑你对2的 pindex 的测试while循环。

[UpDate]

尝试对此序列进行排序：{0,2,4,6,1,3,5}

如果有问题，它将确认我在之前的更新中表达的疑问。

让我知道结果。

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.

这篇关于快速排序算法中的问题......的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！