Java Bubble sort auf randomisierten ListArray

Question

Ich übe Java und kann eine Bubble-Sortierung auf einem int [] -Array erhalten. Ich sah, ob ich ein schwierigeres Beispiel für mich selbst machen könnte, also habe ich eine ArrayList mit zufälliger Länge mit Zufallszahlen in jedem Element erstellt.

Das Problem ist, wenn Blasensortierung durchgeführt wird, manchmal wird nichts gedruckt, nachdem bubbleSort2 aufgerufen wird. Und aus irgendeinem Grund kann ich keine foreach-Schleife in der bubbleSort2-Methode verwenden.

Lassen Sie mich auch wissen, wenn meine Verwendung von List und ArrayList in Ordnung ist.

import java.util.ArrayList; 
import java.util.List; 

public class BubbleSort 
{ 

    public static void main(String[] args) 
    { 
     List<Integer> myList2 = new ArrayList<Integer>(); 
     int min = 2; 
     int max = 30; 
     for (int i=0; i<(int)(Math.random() * (max - min) + min); i++) 
     { 
      myList2.add((int)(Math.random() * 100)); 
     } 

     System.out.println("Unsorted list 2"); 
     for (int element: myList2) 
     { 
      System.out.print(element + " "); 
     } 
     System.out.println(""); 

     System.out.println("Bubble sorted list 2 (BubbleSort2)"); 
     bubbleSort2(myList2); 
     for(int element: myList2) 
     { 
      System.out.print(element + " "); 
     } 
    } 

    public static void swap2(List<Integer> x, int i, int j) 
    { 
     Integer temp = x.get(i); 
     x.set(i, x.get(j)); 
     x.set(j, temp); 
    } 

    public static void bubbleSort2(List<Integer> x) 
    { 
     int mostRightSwap = x.size() - 1; 
     while (mostRightSwap > 0) 
     { 
      for (int i=0; i<x.size()-1; i++) 
      { 
       if (x.get(i) > x.get(i + 1)) 
       { 
        swap2(x, i, i + 1); 
        mostRightSwap = i; 
       } 
      } 
     } 
    } 

} 

Update:

Ich habe mein Problem gelöst. Wie hier und von Freunden an anderer Stelle erwähnt, falle ich manchmal in eine Endlosschleife, wenn die if-Bedingung niemals erfüllt wird. Also eine Zeile Code mostRightSwap = 0; wird hinzugefügt, um die while-Bedingung vor der if-Anweisung zu fälschen, falls die if-Anweisung nicht ausgeführt wird.

public static void bubbleSort(List<Integer> x) 
    { 
     int mostRightSwap = x.size() - 1; 
     while (mostRightSwap > 0) 
     { 
      int right = mostRightSwap; 
      mostRightSwap = 0; 
      for (int i=0; i<right; i++) 
      { 
       if (x.get(i) > x.get(i+1)) 
       { 
        swap2(x, i, i+1); 
        mostRightSwap = i; 
       } 
      } 
     } 
    } 

Answer 1

Wenn Sie bereits eine Liste mit warum nicht einfach vordefinierte Methode über Collections verwenden, um die Daten zu sortieren.

List<Integer> x = new ArrayList(); 
Collections.sort(x); 
Collections.reverse(x); 

Answer 2

Ihr Problem ist im Grunde, dass Sie in eine Endlosschleife laufen. Ihre Stoppbedingung ist, wenn das am besten getauschte Element nicht das erste Element ist, versuchen Sie, das Array zu blasen. Stellen Sie sich nun ein Szenario mit folgenden Elementen vor.

[1, 5, 31, 17, 20]. Was denkst du wird passieren? Das erste Element wird niemals vertauscht, und Sie bleiben in einer Endlosschleife stecken, da Ihre äußere while-Schleife die Schleife niemals stoppen wird, weil das erste Element das niedrigste ist. Ich würde eher einen einfachen Boolean vorschlagen, der prüft, ob etwas für die äußere while-Schleife ausgetauscht wurde.

public static void bubbleSort2(List<Integer> x) 
{ 
    boolean swapped = false; 
    do 
    { 
     swapped = false; 
     for (int i=0; i<x.size()-1; i++) 
     { 
      if (x.get(i) > x.get(i + 1)) 
      { 
       swap2(x, i, i + 1); 
       swapped = true; 
      } 
     } 
    } while(swapped); 
} 

Answer 3

Ein paar Dinge zu beachten, hier.

Erstens, wenn Sie mit Java 8 können Sie Ihre zufällige Liste leichter mit erstellen:

Random rand = new Random(); 
List<Integer> list = rand.ints(rand.nextInt(30) + 2, 1, 100) 
    .collect(Collectors.toList()); 

Zweitens Collections hat eine swap Methode.

Drittens kann ich nicht sehen, wie Ihre Blase Art enden soll. Wenn Sie beispielsweise eine Liste übergeben, die bereits sortiert ist, bleibt mostRightSwap auf der Größe -1 und die Schleife wird nicht beendet.