2

I have two Arraylists, which should be sort descending due to the values in the second Arraylist(which is type double). Basically the values of the first Arraylist are not regarded, but the elements in the first Arraylist map to the ones in the second one, so both Arrays should get sortet due to the values in Arraylist2. (I hope this is more or less clear)

Problem:

Somehow when I print out the values of Arraylist2 (with the double values) after beeing sorted they are totally not sorted, but have a different sequence than before sorting. I also wrote some debug system.outs, which shows me the algoritm is running, but I have no idea, why it won`t sort correctly, I hope somebody can see where the problem is.

Code:

Call + Outputcode:

            String str = "";
        // DEBUG //
        for(int k = 0; k < test.size(); k++) {
            str += " " + test.get(k);   
        }
        System.out.println(str);
        System.out.println("------------------------------------------------------------------/r/n");
        sort(items, test, 0 ,(test.size() -1));
        String str2 = "";
        for(int k = 0; k < test.size(); k++) {
            str2 += " " + test.get(k);  
        }
        System.out.println(str2);
        // DEBUG //

Quicksort algoritm:

public void sort(ArrayList<Item> items, ArrayList<Double> nutzen, int l, int r) {
        if(l < r) {
            double pivot = nutzen.get(r);
            int p = partition(items, nutzen, l, r, pivot);
            sort(items, nutzen, l, p-1);
            sort(items, nutzen, p+1, r);
        }
    }

    private int partition(ArrayList<Item> items, ArrayList<Double> nutzen, int l, int r, double pivot) {
        int i = l;
        int j = r-1;
        do {
            do {
                i = i + 1;
            } while(i < r && nutzen.get(i) > pivot);
            do {
                j = j - 1;
            } while(j > l && nutzen.get(i) < l);
            if(i < j) {
                // Tausche Daten
                double tmp  = nutzen.get(i);
                Item tmp2 = items.get(i);
                nutzen.set(i, nutzen.get(j));
                nutzen.set(j, tmp);
                items.set(i, items.get(j));
                items.set(j, tmp2);
            }
        } while(i < j); 
        if (nutzen.get(i) > pivot) {
            double tmp  = nutzen.get(i);
            Item tmp2 = items.get(i);
            nutzen.set(i, nutzen.get(r));
            nutzen.set(r, tmp);
            items.set(i, items.get(r));
            items.set(r, tmp2);
        }
        return i;       
    }

Sample Output: (first is the unsorted Arraylist, second the sorted one)

 0.22540250447227192 0.5289855072463768 0.3245742092457421 0.35105028644175684 0.3773755656108597 0.2041172365666434 0.4091826437941473 0.33037437282902354 0.4383735705209657 0.28473648186173856 0.3422330097087379 0.25703446095478977 0.3373493975903614 0.2701873935264055 0.3221397891448653 0.34912891986062716 0.3018603018603019 0.31361550229474755 0.35785288270377735 0.27435456110154904 0.22781065088757396 0.27684563758389263 0.21881770349736923 0.4226451927769644 0.24628854206318995 0.3256219991270188 0.3844096293465801 0.3178254051228437 0.398093508851566 0.3544702638834187 0.20851528384279475 0.4041025641025641 0.21713772992373262 0.26014028667276606 0.3591307662981319 0.23153252480705622 0.27023319615912206 0.24333719582850522 0.29892573563755254 0.31568998109640833 0.27108784176847006 0.34125412541254124 0.279090113735783 0.3737704918032787 0.3326703132769766 0.22776967930029154 0.22143195827406353 0.27614293221229635 0.22866611433305717 0.533879374534624 0.28534031413612565 0.20782003213711836 0.21262837580829214 0.2137904468412943 0.2898398529797847 0.24622641509433962 0.3927108927108927 0.26053042121684866 0.3005334914048607 0.23183297180043383 0.24539571926331508 0.3479899497487437 0.4193054136874362 0.31155589123867067 0.31771595900439237 0.3897529734675206 0.3561643835616438 0.31221719457013575 0.477299880525687 0.2683881064162754 0.30484160191273163 0.20526154787396758 0.2362366474938373 0.3485633537447009 0.24390243902439024 0.2618308766485648 0.382782475019216 0.23864915572232645 0.466403162055336 0.31514030218933087 0.3074433656957929 0.3438485804416404 0.28774928774928776 0.29548816568047337 0.34277286135693213 0.5334967320261438 0.32756539235412474 0.2945334590009425 0.20973389355742297 0.25292242295430395 0.2336989640463132 0.328060522696011 0.4326647564469914 0.30530226274907124 0.3326499231163506 0.3077194219245682 0.2322235922729141 0.25569544364508395 0.3788049605411499 0.2476489028213166
------------------------------------------------------------------
 0.22540250447227192 0.5289855072463768 0.466403162055336 0.4383735705209657 0.3897529734675206 0.4193054136874362 0.4226451927769644 0.29548816568047337 0.3479899497487437 0.3438485804416404 0.477299880525687 0.3561643835616438 0.4041025641025641 0.3326703132769766 0.3844096293465801 0.4091826437941473 0.34277286135693213 0.398093508851566 0.3485633537447009 0.3927108927108927 0.4326647564469914 0.3005334914048607 0.28534031413612565 0.31155589123867067 0.31771595900439237 0.31221719457013575 0.30484160191273163 0.3074433656957929 0.31514030218933087 0.5334967320261438 0.32756539235412474 0.2898398529797847 0.25292242295430395 0.28774928774928776 0.533879374534624 0.2945334590009425 0.20973389355742297 0.27614293221229635 0.26053042121684866 0.2683881064162754 0.3737704918032787 0.279090113735783 0.34125412541254124 0.27108784176847006 0.31568998109640833 0.29892573563755254 0.2336989640463132 0.27023319615912206 0.328060522696011 0.3591307662981319 0.26014028667276606 0.30530226274907124 0.3544702638834187 0.3178254051228437 0.3256219991270188 0.3326499231163506 0.3077194219245682 0.27684563758389263 0.2322235922729141 0.27435456110154904 0.35785288270377735 0.31361550229474755 0.3018603018603019 0.34912891986062716 0.3221397891448653 0.2701873935264055 0.3373493975903614 0.25703446095478977 0.3422330097087379 0.28473648186173856 0.33037437282902354 0.25569544364508395 0.3773755656108597 0.35105028644175684 0.3245742092457421 0.2618308766485648 0.382782475019216 0.23864915572232645 0.24390243902439024 0.2362366474938373 0.20526154787396758 0.24539571926331508 0.23183297180043383 0.24622641509433962 0.2137904468412943 0.21262837580829214 0.20782003213711836 0.22866611433305717 0.22143195827406353 0.22776967930029154 0.24333719582850522 0.23153252480705622 0.21713772992373262 0.20851528384279475 0.24628854206318995 0.21881770349736923 0.22781065088757396 0.2041172365666434 0.3788049605411499 0.2476489028213166
4

2 回答 2

1

我已经很久没有编写排序算法了（哦，完整 API 的乐趣），但这让我觉得很奇怪

       } while(j > l && nutzen.get(i) < l);

不是更好吗

       } while(j > l && nutzen.get(i) < pivot);

无论如何，一个建议。与其尝试对 10 个数字进行排序并仅报告退出，不如尝试使用 3 或 4 并更认真地调试代码的内部工作（在每个步骤中，选择哪个枢轴，生成的子列表是什么等）。

于 2013-06-10T18:11:31.250 回答
0

我才刚刚开始，所以我以前没有真正看过快速排序，但我想我已经成功了。只需要调整我评论的 4 行。此外，我将 l 更改为 left，r 更改为 right，i 更改为 a，j 更改为 z，以便我更容易跟踪。正如我所说，我仍然是一个菜鸟，在我作为 Comp sci 专业的第一年，所以我无法评论实施的好坏。这对我来说似乎是一个很好的问题，可以努力学习一点。希望它对您有所帮助，而不会太“这就是答案”-ish。

变化：

  1. 将左右计数器进一步“向外”偏移 1，以说明它们在比较之前递增和递减。似乎没有按原样解析整个范围。可以将内部 do..while 循环更改为 while 循环以获得相同的效果。
  2. 改为。l_ pivot您正在比较一个值和一个索引。i 是正确的，所以我认为这只是一个哎呀。
  3. 改为。if (nutzen.get(a) > pivot)_ if (nutzen.get(a) < pivot)在这一点上，我需要花更多时间找出原因，而且我还有其他事情需要做。我所知道的是，它并没有以另一种方式工作，呵呵。

我没有疯狂地测试它，但它似乎确实有效。我复制了大约 6 个您的示例值并进行了尝试，并且成功了。祝你好运！

private static int partition(ArrayList<Double> items, ArrayList<Double> nutzen, int left, int right, double pivot) {
    int a = left-1; //offset to account for do..while incrementing prior to comparison
    int z = right; //offset to account for do..while decrementing prior to comparison
    do {
        do {
            a++;
        } while(a < right && nutzen.get(a) > pivot);

        do {
            z--;
        } while(z > left && nutzen.get(z) < pivot); //compare to pivot, not index

        if(a < z) {
            double tmp  = nutzen.get(a);
            Double tmp2 = items.get(a);
            nutzen.set(a, nutzen.get(z));
            nutzen.set(z, tmp);
            items.set(a, items.get(z));
            items.set(z, tmp2);
        }
    } while(a < z);

    if (nutzen.get(a) < pivot) {  //changed > to <
        double tmp  = nutzen.get(a);
        Double tmp2 = items.get(a);
        nutzen.set(a, nutzen.get(right));
        nutzen.set(right, tmp);
        items.set(a, items.get(right));
        items.set(right, tmp2);
    }
    return a;       
}

.22540250447227192 0.5289855072463768 0.3245742092457421 0.35105028644175684 0.3773755656108597 0.2041172365666434
------------------------------------------------------------------
0.5289855072463768 0.3773755656108597 0.35105028644175684 0.3245742092457421 0.22540250447227192 0.2041172365666434
于 2013-06-10T20:24:06.713 回答