Java Quicksort Algorithm не работает должным образом

Question

У меня есть два Arraylists, которые должны сортироваться по убыванию из-за значений во втором Arraylist (который является типом double). В принципе, значения первого Arraylist не рассматриваются, но элементы в первом Arraylist сопоставляются с таковыми во втором, поэтому оба массива должны сортироваться из-за значений в Arraylist2. (Я надеюсь, что это более или менее ясно)

Проблема:

Как-то, когда я распечатать значения Arraylist2 (с двойными значениями) после того, как неоспоримые отсортированы они полностью не отсортированы, но имею разные чем перед сортировкой. Я также написал несколько debug system.outs, которые показывают мне, что алгоритм работает, но я понятия не имею, почему он не правильно сортируется, я надеюсь, что кто-то может увидеть, где проблема.

Код:

Вызов + 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;  
    } 

Пример вывода: (первая является несортированный Список_массивов, второй отсортированный один)

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 

Answer 1

Это было долгое время, так как я кодифицированы алгоритмы сортировки (о, радостей полных интерфейсов), но это кажется мне странным

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

бы не лучше быть

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

Во всяком случае , совет. Вместо того, чтобы пытаться сортировать 10 номеров и просто сообщать о выходе, попробуйте с 3 или 4 и более серьезно отнеситесь к внутренней работе вашего кода (на каждом шаге, который выбирается, какие результирующие подсписки и т. Д.).

Answer 2

Я только начинаю, так что я раньше не смотрел на быструю сортировку, но я думаю, что у меня все получилось. Просто нужно было настроить 4 строки, которые я прокомментировал. Кроме того, я изменил l налево, r на правый, i на a и j на z, чтобы немного облегчить мне отслеживание. Как я уже сказал, я все еще ноб, в первый год работы в качестве основного специалиста, поэтому я не могу прокомментировать, насколько хороша реализация. Мне показалось хорошей проблемой для меня, и я попытаюсь немного поучиться. Надеюсь, это поможет вам, если вы не будете слишком «вот ответ».

Изменения:

1. Offset левый и правый счетчики далее «снаружи» от 1 до счета для них получение увеличиваться и уменьшаться до сравнения. Кажется, не разобрал весь диапазон так, как это было. Возможно, изменили внутренность do.. 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