Kodierung Bubble Sort mit Java

Question

Ich weiß nicht, ob ich diese Kodierung richtig gemacht habe, aber kann jemand bestätigen, ob meine doBubbleSort-Methode und ihre Implementierung in der Hauptmethode korrekt programmiert sind? Meine Codierung erfordert, dass ich ein Array der Größe 20 erstelle und es mit zufälligen Ganzzahlen zwischen 1 und 1000 beziehe, ohne sie hart zu codieren. Das Ergebnis sollte die ursprüngliche unsortierte Liste von ganzen Zahlen anzeigen; und dann jeden Durchlauf des Blasensortieralgorithmus in einer separaten Zeile anzeigen. Ich muss das Programm wiederholen, bis der Benutzer das Programm beendet. ** Ich habe Änderungen vorgenommen, um sicherzustellen, dass die von mir verwendeten Variablen gemäß ArrayLists deklariert werden.

Ein Beispiel, wie ich meine ausgegeben werden soll, wie kommen unten gezeigt wird (obwohl es nur 5 ganze Zahlen zeigt, wenn ich versuche, 20 zu tun):

unsortiert Liste: 68 3 298 290 1
Pass 1: 3 68 290 1 298
Pass 2: 3 68 1 290 298
Durchlauf 3: 3 1 68 290 298
Pass 4: 1 3 68 290 298

// Used to capture keyboard input 
import java.util.*; 

// Our class called BubbleSort 
public class BubbleSort { 

    // Create doBubbleSort method 
    public static void doBubbleSort(ArrayList<Integer> arr) { 
     boolean needNextPass = true; 
     while (needNextPass) { 
      // Array may be sorted and next pass not needed 
      needNextPass = false; 
      // Swap list 
      for (int i = 0; i < arr.size()-1; i++) { 
       if (arr.get(i) > arr.get(i+1)) { 
        int temp = arr.get(i); 
        arr.set(i, arr.get(i+1)); 
        arr.set(i+1, temp); 
        printOut(i+1, arr); // using printOut method 
        needNextPass = true; // Next pass still needed 
       } 
      } 
     } 
    } 

    private static void printOut(int pass, ArrayList<Integer> list) { 
     System.out.print("PASS " + pass + ": "); 
     for (int i = 0; i < list.size()-1; i++) { 
      System.out.print(list.get(i) + ", "); 
     } 
     // Shows very last integer with a period 
     System.out.print(list.get(list.size()-1) + "."); 
     System.out.println(); 
    } 

    // Main method 
    public static void main(String[] args) { 
     ArrayList<Integer> array = new ArrayList<Integer>(); // Declare and instantiate a new ArrayList object 
     Scanner userChoice = new Scanner(System.in); // User input for quitting program 
     String choice = ""; // Will hold user choice to quit program 
     boolean inputFlag = false; // True if input is valid, false otherwise 

     // Repeat program until user chooses to quit 
     while (inputFlag = true) { 
      System.out.print("\nWould you like to continue the program? (Y/N): "); 
      choice = userChoice.nextLine(); 
      if (choice.equalsIgnoreCase("Y")) { 
       try { 
        /* Create an array of size 20 and populate it with random integers between 1 and 1000. 
        Do not ask user for the numbers and do not hard code them */ 
        for (int i = 0; i < 20; i++) { 
         int integer = (int)(1000.0 * Math.random()); 
         array.add(integer); 
        } 
        System.out.print("\nUNSORTED LIST: "); 

        //Display the 20 size of the unsorted ArrayList 
        for (int i = 0; i < array.size() - 1; i++) { 
         System.out.print(array.get(i) + ", "); 
        } 
        // Shows very last integer with a period 
        System.out.print(array.get(array.size() - 1) + "."); 
        System.out.println(); 
        doBubbleSort(array); 
       } 

       catch (IndexOutOfBoundsException e) { 
        System.out.println("\nThere is an out of bounds error in the ArrayList."); 
       } 
      } 
      else if (choice.equalsIgnoreCase("N")) { 
       break; 
      } 
      // Error message when inputting anything other than Y/N 
      else { 
       System.out.println("\nERROR. Only Y, y, N, or n may be inputted."); 
       System.out.println("Please try again."); 
      } 
     } 
    } 
} 

Answer 1

Mit Ihrer Implementierung gehen, da Sie scheinen, dies neu zu lernen, gibt es ein paar Dinge, die Sie ändern sollten. Da Sie ein int-Array für die doBubbleSort-Methode verwenden, sollten Sie auch ein int-Array in der main-Methode verwenden.

Die Implementierung von bubblesort muss ebenfalls geändert werden. Sie sollten zuerst sorgfältig in seine Logik schauen. Es ist nicht notwendig, jedes Mal das gesamte Array durchzugehen.

// Create doBubbleSort method 
public static void doBubbleSort(int[] arr) { 
    boolean needNextPass = true; 
    // Array may be sorted and next pass not needed 
    // Swap list 
    for (int i = 0; i < arr.length - 1; i++) { 
     if (needNextPass) { 
      needNextPass = false; 
      for (int j = arr.length - 1; j > i; j--) { 
       int temp; 
       if (arr[j] < arr[j - 1]) { 
        temp = arr[j - 1]; 
        arr[j - 1] = arr[j]; 
        arr[j] = temp; 
        needNextPass = true; // Next pass still needed 
       } 
      } 
      printOut(i + 1, arr); // using printOut method 
     } 
    } 
} 

Und dann, das Array drucken.

private static void printOut(int pass, int[] list) { 
    System.out.print("PASS " + pass + ": "); 
    for (int i = 0; i < list.length - 1; i++) { 
     System.out.print(list[i] + ", "); 
    } 
    // Shows very last integer with a period 
    System.out.print(list[list.length - 1] + "."); 
    System.out.println(); 
} 

Jetzt die wichtigste Methode. Ich habe den Eingabehandhabungsteil zum erneuten Ausführen des Programms geändert und ein int-Array verwendet, wie Sie es ursprünglich gepostet hatten.

// Main method 
public static void main(String[] args) { 
    int[] array = new int[20]; // Declare and instantiate a new ArrayList object 
    Scanner userChoice = new Scanner(System.in); // User input for quitting program 
    boolean inputFlag = true; // True if input is valid, false otherwise 
    String choice; 

    // Repeat program until user chooses to quit 
    while (inputFlag == true) { 

     try { 
      /* Create an array of size 20 and populate it with random integers between 1 and 1000. 
      Do not ask user for the numbers and do not hard code them */ 
      for (int i = 0; i < 20; i++) { 
       int integer = (int) (1000.0 * Math.random()); 
       array[i] = integer; 
      } 
      System.out.print("\nUNSORTED LIST: "); 

      //Display the 20 size of the unsorted ArrayList 
      for (int i = 0; i < array.length - 1; i++) { 
       System.out.print(array[i] + ", "); 
      } 
      // Shows very last integer with a period 
      System.out.print(array[array.length - 1] + "."); 
      System.out.println(); 
      doBubbleSort(array); 
     } catch (IndexOutOfBoundsException e) { 
      System.out.println("\nThere is an out of bounds error in the ArrayList."); 
     } 

     System.out.print("\nWould you like to continue the program? (Y/N): "); 
     choice = userChoice.nextLine(); 

     while (!(choice.equalsIgnoreCase("Y")) && !(choice.equalsIgnoreCase("N"))) { 
      // Error message when inputting anything other than Y/N 
      System.out.println("\nERROR. Only Y, y, N, or n may be inputted."); 
      System.out.println("Please try again."); 
      choice = userChoice.nextLine(); 
     } 

     if (choice.equalsIgnoreCase("N")) { 
      inputFlag = false; 
     } 

    } 
} 

}

Answer 2

Sie haben zu viel Kesselblech-Code für Bubble-Sort geschrieben. Verwenden Sie für die Blasensortierung die rekursive Methode. Ich schrieb für Sie einfache Blasenverfahren, das tun, was Sie mit dem Ausgang wollen

private int[] bubbleSort(int[] arr){ 

    int c; 
    boolean isArranged = false; 

    for (int i = 0; i < arr.length; i++) { 
     if (i < (arr.length - 1) && arr[i] > arr[i+1]){ 
      c = arr[i]; 
      arr[i] = arr[i+1]; 
      arr[i+1] = c; 
      isArranged = true; 
     } 
    } 

    if (isArranged){ 
     return bubbleSort(arr); 
    }else{ 
     return arr; 
    } 
} 

Rufen Sie diese wie:

Scanner in = new Scanner(System.in); 
    int length = in.nextInt(); 
    int[] arr = new int[length]; 

    for (int i = 0; i < length; i++) { 
     arr[i] = in.nextInt(); 
    } 

    Main main = new Main(); 

    int[] newArr = main.bubbleSort(arr); 

    for (int i = 0; i < newArr.length; i++) { 
     System.out.print(newArr[i] + " "); 
    } 

Sie Arraylist schreiben kann stattdessen Array int.