Java Bubble сортировать по рандомизированному ListArray

Question

Я практикую Java и могу получить сортировку пузырьков, работающих с массивом int []. Я видел, могу ли я сделать более трудный пример для себя, поэтому я сделал случайную длину ArrayList со случайными числами в каждом элементе.

Проблема заключается в том, что сортировка пузырьков иногда не печатается после вызова bubbleSort2. И по какой-то причине я не могу использовать foreach-loop в методе bubbleSort2.

Также дайте мне знать, если мое использование List и ArrayList в порядке.

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:

я понял мою проблему. Как указано здесь и друзьями в другом месте, я иногда попадаю в бесконечный цикл, когда условие if никогда не выполняется. Итак, строка кода mostRightSwap = 0; добавляется для фальсификации условия while перед оператором if только в том случае, если инструкция if не выполняется.

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

Если вы уже используете список, почему не просто использовать предопределенный метод более Collections для сортировки данных.

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

Answer 2

Ваша проблема в том, что вы работаете в бесконечном цикле. Ваше условие остановки, если самый правый поменявшийся элемент не является первым элементом, попробуйте продублировать массив. Но представьте себе такой сценарий со следующими элементами.

[1, 5, 31, 17, 20]. Как ты думаешь, что произойдет? Первый элемент никогда не будет заменен, и вы застряли в бесконечном цикле, так как ваше внешнее условие цикла никогда не остановит цикл, потому что первый элемент является самым низким. Я предпочел бы простое логическое значение, которое проверяет, было ли что-то заменено для внешнего цикла while.

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

Несколько вещей, чтобы отметить здесь.

Во-первых, если вы используете Java 8 вы можете создать свой случайный список более легко с:

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

Во-вторых, Collections имеет метод swap.

В-третьих, я не вижу, как закончится ваш вид пузыря. Например, если вы пройдете список, который уже отсортирован, то mostRightSwap останется установленным в размере - 1, и цикл не будет завершен.