Bubble Sort wirft Ausnahme

Question

Ich schreibe ein Programm für Klasse, um die Fähigkeit zu zeigen, die Blasensortierung zu codieren. Ich habe tagelang daran gearbeitet und kann es anscheinend nicht bekommen. Zumindest kompiliert es jetzt, aber löst eine Ausnahme aus.
Ich habe den Teil kommentiert, mit dem ich Probleme habe, das tatsächliche Austauschen der Elemente im Array.

Das Programm soll ein Array von 20 randoms Ganzzahlen erzeugen, und sortieren Sie sie dann mithilfe der Bubble-Sortierung, Drucken jedes Durchlaufs, wie es geht, bis es abgeschlossen ist.

import java.util.*; 


public class BubbleSorting { 


public static void bubbleSort(ArrayList<Integer> arr) { 
    int n = arr.size(); 
    int temp = 0; 

    for (int i = 0; i < n; i++) { 

    //this is the chunk of code that I am having problems with 
    for (int j = i; j < (n-1); j++) { 
     if (arr.get(n-1) < arr.get(j)) 
      temp = arr.get(j-1); 
      arr.set(j-1, arr.get(j)); 
      arr.set(j, temp); 
    } 

    } 
} 

private static void printOut(int pass, ArrayList<Integer> array) { 
    System.out.print("Pass " + pass + ": "); 
    for (int i = 0; i < array.size() - 1; i++) { 
    System.out.print(array.get(i) + ", "); 
    } 

    System.out.print(array.get(array.size() - 1) + "."); 
    System.out.println(); 


} 


public static void main(String[] args) { 
    ArrayList<Integer> array = new ArrayList<Integer>(); 
    Scanner sc = new Scanner(System.in); 
    String userInput = ""; 
    boolean endLoop = false; 

    do{ 
    try{ 

     for (int i = 0; i < 20; i++) { 
      int element = (int)(1000.0 * Math.random()); 
      array.add(element); 
     } 
     System.out.print("\nUnsorted Array: "); 

       //Displays the unsorted ArrayList 
     for (int i = 0; i < array.size() - 1; i++) { 
      System.out.print(array.get(i) + ", "); 
     } 

     System.out.print(array.get(array.size() - 1) + "."); 
     System.out.println(); 
     bubbleSort(array); 
    } 
    catch (IndexOutOfBoundsException e) { 
     System.out.println("\nThere is an out of bounds error in the ArrayList."); 
    } 



    System.out.print("\nEnter Y to continue or N to quit: "); 
     userInput = sc.nextLine(); 

    if (userInput.equalsIgnoreCase("Y")) { 
     endLoop = false; 

    } 
    else if (userInput.equalsIgnoreCase("N")) { 
     endLoop = true; 
    } 

    else { 
     System.out.println("\nYou did not enter Y or N."); 
     System.out.println("Please try again."); 
    } 

    }while(endLoop == false); 


    } 
} 

Answer 1

Versuchen Sie, den folgenden Code:

public static void bubbleSort(ArrayList<Integer> list){ 
     for(int i = 0; i < list.size(); i++) { 
      for(int j = 1; j < (list.size() -i); j++) { 
       if(list.get(j - 1) > list.get(j)) { 
        int temp = list.get(j-1); 
        list.set(j-1, list.get(j)); 
        list.set(j, temp); 
       }     
      } 
     }  
    } 

Sie haben zwei Fehler ... zuerst in der ersten für seine Schleife for(int j = 1; j < (list.size() -i); j++) während Sie int j=i und zweite schrieb ist nicht deckten die geschweiften Klammern {} in if loop condition.Cheers

Answer 2

Junge Sie verpasst die Klammer in der If-Anweisung.

//this is the chunk of code that I am having problems with 
       for (int j = i; j < (n - 1); j++) { 
        if (arr.get(n - 1) < arr.get(j)) {//<------here this one 
         temp = arr.get(j - 1); 
         arr.set(j - 1, arr.get(j)); 
         arr.set(j, temp); 
        }//<----this too 
       } 

---

nur die erste Anweisung nach dem, wenn in Betracht gezogen wird, wenn Sie nicht die Halterung setzen.

Answer 3

Möglicherweise haben Sie ein Missverständnis, wie Blasensortieren funktioniert. Hier ist ein Beispiel dafür, wie Blasensortierung funktioniert (aus this link)

Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest 
number to greatest number using bubble sort. In each step, elements written 
in bold are being compared. Three passes will be required. 

First Pass 
(5 1 4 2 8) (1 5 4 2 8), Here, algorithm 
compares the first two elements, and swaps since 5 > 1. 
(1 5 4 2 8) (1 4 5 2 8), Swap since 5 > 4 
(1 4 5 2 8) (1 4 2 5 8), Swap since 5 > 2 
(1 4 2 5 8) (1 4 2 5 8), Now, since these elements are already in order 
(8 > 5), algorithm does not swap them. 

Second Pass 
(1 4 2 5 8) (1 4 2 5 8) 
(1 4 2 5 8) (1 2 4 5 8), Swap since 4 > 2 
(1 2 4 5 8) (1 2 4 5 8) 
(1 2 4 5 8) (1 2 4 5 8) 
Now, the array is already sorted, but the algorithm does not know if it is 
completed. The algorithm needs one whole pass without any swap to know it is 
sorted. 

Third Pass 
(1 2 4 5 8) (1 2 4 5 8) 
(1 2 4 5 8) (1 2 4 5 8) 
(1 2 4 5 8) (1 2 4 5 8) 
(1 2 4 5 8) (1 2 4 5 8) 

Nun vergleicht diese Linie des Denkens, um Ihren Code hier:

for (int i = 0; i < n; i++) { 

    //this is the chunk of code that I am having problems with 
    for (int j = i; j < (n-1); j++) { 
     if (arr.get(n-1) < arr.get(j)) 
      temp = arr.get(j-1); 
      arr.set(j-1, arr.get(j)); 
      arr.set(j, temp); 
    } 

} 

Nun, wenn Sie das Array in dem Beispiel verwenden (5 1 4 2 8) und stecken Sie das in Ihren Code, es wird am Ende 8 zu jeder gegebenen Zahl zu vergleichen, und da 8 bereits der größte ist, wird die if-Anweisung immer falsch sein; Es wird keine Sortierung stattfinden. Vergleichen Sie stattdessen zwei benachbarte Indizes gleichzeitig und verwenden Sie einen booleschen Wert, um anzugeben, ob ein Austausch stattgefunden hat. Angesichts dieser Art von Funktionalität tauscht die Sortierung die größtmögliche Anzahl so weit wie möglich bis zum Ende des Arrays aus. Sobald also kein Austausch mehr möglich war, wissen Sie, dass das Array sortiert wurde. Daher soll die innere Schleife nur bis zum bereits sortierten Teil reichen, nicht weiter. Wenn Sie sortierte Werte vergleichen, endet die Sortierung früh. Verwenden Sie diese Denkweise und wenden Sie sie auf Ihren Code an.