BubbleSort

babuschka

Top Contributor
Hallo, ich habe versucht, den BubbleSort zu implementieren.

Ist das okay?

Ich sehe den Fehler nicht, komme aber auf falsche Ergebnisse.


Java:
class BubbleSort{

 static int aux;
 
 

 public static void bubbleSorting(int[] array) {


 for( int i = 0; i<=array.length-2;i++ ) {

       for( int j = 0; j<=array.length-i-2; j++ ) {

              if( array[j] > array[j+1] ) {

                       array[j] = aux;
 
                       array[j] = array[j+1];

                       array[j+1] = aux;
		}


		       
             }

                   }

                
        
             
		

	}

}
 
G

gassssssst

Gast
Ich glaube deine innere For Schleife ist falsch. Die muss von der aktuellen Position (i) bis zum Ende des arrays gehen (array.length). Die aktuelle Bedingung macht so keinen Sinn.
 

Lliror

Neues Mitglied
Java:
int help_z = 0;
boolean tausch = false;
int z = 0;

do{
        tausch = false;
        for(z=0; z<zeit.length-1;z++){
            if(zeit[z] > zeit[z+1]){
                help_z = zeit[z];
                zeit[z] = zeit[z+1];
                zeit[z+1] = help_z;
                tausch = true;
            }
        }
   }
   while(tausch == true);

Das war meine Art. Vieleicht hilft es dir weiter.
 

Kiri

Bekanntes Mitglied
das
Java:
array[j] = aux;
sollte auch eher so
Java:
aux = array[j];
aussehen
 

babuschka

Top Contributor
Habe versucht, Eure Tipps umzusetzen.

Java:
class BubbleSort{

  int aux;

  public static void bubbleSort(int[] array ) {

    for( int i = array.length-2; i >=0; i--) {

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

          if( array[j] > array[j+1] ) {
    
                  aux = array[j];
                
                  array[j] = array[j+1];

                  array[j+1] = aux;
             }
        }
     }
    }
 }

Besser? :oops:
 
H

hüteüberhüte

Gast
Besser kann man so nicht sagen. Wenn die Arraylänge n ist, kann die innere Schleife problemlos n-mal durchlaufen werden. Beim ersten mal wandert das größte Element nach hinten, dann das zweitgrößte usw.
Zeilen 13-17 vertauschen benachbarte Elemente. Sieht richtig aus.
 

Kiri

Bekanntes Mitglied
Also, hättest du bei deiner 1. Variante lediglich meinen Hinweis ausgeführt, würde es auch funktionieren. Aber deine letzte Variante funktioniert auch.
 
R

Ralle502

Gast
Der Bubblesort läuft recht langsam, wenn man jedes Element sofort tauscht. Ich habe hier ein Beispiel aus alten Basic Zeiten in Java umgesetzt, bin aber auch totaler Anfänger in Java, so dass vielleicht noch Optimierungen möglich sind.
Die Tabelle wird durchsucht und lediglich der Index des größten Wertes gemerkt. Der Tausch findet dann nur einmal je Durchlauf der äußeren Schleife statt.

Java:
public static int[] bubbleSorting(int[] array) {
		
		int tmp;
		int jj;
		int k;
				
		for( int i = 0; i<= array.length-2;i++ ){
			k=i; 		// Index für den festen Vergleichsindex
			jj = i;		// Führt den Index des größten Wertes im durchsuchten array
			for( int j = i+1; j <= array.length-1; j++ ){
				if( array[jj] > array[j]) jj = j; // Größten Wert im array, nur merken! 
			}
			// Arrayinhalt tauschen, wenn Hilfsindex jj geändert wurde
			if (k != jj) {
				tmp = array[k];
				array[k] = array[jj];
				array[jj] = tmp;
			}
		} // Ende for( int i = 0; i<= array.length-2;i++ )
		
		return array;
	}
 
H

hüteüberhüte

Gast
Dann ist es kein Bubble Sort mehr, sondern Selection Sort. Betrachtet man die Laufzeit in der O-Notation, so ergibt sich kein Unterschied, da die innere Schleife genauso oft ausgeführt werden muss. Allerdings gibt es von beiden Sortierverfahren zwei Varianten bezüglich der Laufzeit der inneren Schleife. Entweder wird die innere Schleife n-mal ausgeführt, oder - weil nach jeder Ausführung das nächstgrößere Element einsortiert ist - nur i-mal. Außerdem lassen sich beide Sortierverfahren stabil implementieren, wobei Selection Sort mit einer Nur-größer- bzw. Nur-kleiner-Prüfung grundsätzlich instabil ist.
 
H

hüteüberhüte

Gast
Sehe gerade, dass selbst wenn die innere Schleife bei beiden Sortierverfahren nur i-mal ausgeführt wird, sich die Laufzeit in der O-Notation gegenüber der n-maligen Ausführung nicht unterscheidet: Sortierverfahren ? Wikipedia Über O(n) im best case bei Bubble Sort lässt sich auch streiten, denn zumindest entstehen bei der Ausführung der inneren Schleife O(n²) Vergleiche, zwar keine Vertauschungen, aber Vergleiche.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
S Generischer Bubblesort Java Basics - Anfänger-Themen 19
S BubbleSort für ArrayLists Java Basics - Anfänger-Themen 3
H Bubblesort-Algorithms Java Basics - Anfänger-Themen 14
I Bubblesort Java Basics - Anfänger-Themen 1
L Bubblesort in Batch Script Java Basics - Anfänger-Themen 15
D Bubblesort Java Basics - Anfänger-Themen 2
G Bubblesort Array der Größe 10 Java Basics - Anfänger-Themen 1
M Bubblesort ohne Array Java Basics - Anfänger-Themen 30
V_Fynn03 Erste Schritte BubbleSort Quelltext funktioniert noch nicht Java Basics - Anfänger-Themen 1
H Bubblesort-Zwei Integer auf Dekade vergleichen. Java Basics - Anfänger-Themen 6
R Erste Schritte Einsteiger-Video Bubblesort Bewertung Java Basics - Anfänger-Themen 11
D Array/Bubblesort Fehlermeldungen Java Basics - Anfänger-Themen 1
U BubbleSort Problem Java Basics - Anfänger-Themen 2
L Array und Bubblesort Java Basics - Anfänger-Themen 4
L Frage zu BubbleSort Algorithmus Java Basics - Anfänger-Themen 2
T BubbleSort Java Basics - Anfänger-Themen 9
O Bubblesort allgemeiner schreiben Java Basics - Anfänger-Themen 5
J Interface Bubblesort soll Arrays beliebiger Referenztypen sortieren können. Java Basics - Anfänger-Themen 5
N Mein Bubblesort sortiert mein Array nicht Java Basics - Anfänger-Themen 2
E BubbleSort Java Basics - Anfänger-Themen 2
J Erste Schritte Bubblesort Java Basics - Anfänger-Themen 6
G Array mit BubbleSort sortieren Java Basics - Anfänger-Themen 2
N Bubblesort Programm funktioniert nicht Java Basics - Anfänger-Themen 19
R BubbleSort Java Basics - Anfänger-Themen 4
R BubbleSort Java Basics - Anfänger-Themen 15
A BubbleSort Java Basics - Anfänger-Themen 7
R BubbleSort Java Basics - Anfänger-Themen 6
C Klassen BubbleSort was passiert mit dem Index ? Java Basics - Anfänger-Themen 2
B Sortiermethode bei Bubblesort Java Basics - Anfänger-Themen 15
G Bubblesort - Falsche Sortierung Java Basics - Anfänger-Themen 6
M Laufzeitanalyse Bubblesort Java Basics - Anfänger-Themen 7
T BubbleSort Java Basics - Anfänger-Themen 2
P BubbleSort-Methode Java Basics - Anfänger-Themen 18
M BubbleSort (Sortieralgorithmus) Java Basics - Anfänger-Themen 28
B Bubblesort Java Basics - Anfänger-Themen 70
G Bubblesort ohne Schleifen Java Basics - Anfänger-Themen 10
F Bubblesort, Insertsort Java Basics - Anfänger-Themen 2
K BubbleSort Hausaufgabe Java Basics - Anfänger-Themen 20
B Bubblesort-Algorithmus und Testklasse Java Basics - Anfänger-Themen 5
c_sidi90 Array mit Bubblesort sortieren Java Basics - Anfänger-Themen 8
B Java Bubblesort Java Basics - Anfänger-Themen 5
F Bubblesort---Frage von Anfänger Java Basics - Anfänger-Themen 2
E BubbleSort kleiner Fehler? Java Basics - Anfänger-Themen 14
B BubbleSort Java Basics - Anfänger-Themen 5
L Bubblesort: Exception in Thread "main" Java Basics - Anfänger-Themen 5
K Einfaches Bubblesort Java Basics - Anfänger-Themen 11
W Problem mit BubbleSort und Array Java Basics - Anfänger-Themen 10
Spin taschenrechner incl bubblesort Java Basics - Anfänger-Themen 5
G Bubblesort Java Basics - Anfänger-Themen 2
Binary.Coder Bubblesort in einfachen unmissverständlichen Sätzen Java Basics - Anfänger-Themen 2
B Bubblesort Verfahren Java Basics - Anfänger-Themen 2
C Bubblesort Java Basics - Anfänger-Themen 5
I BubbleSort-Algorithmus Java Basics - Anfänger-Themen 8
G Bubblesort Java Basics - Anfänger-Themen 23
G Bubblesort Java Basics - Anfänger-Themen 15
kulturfenster BubbleSort Java Basics - Anfänger-Themen 7
T Bekomme Fehler mit Bubblesort Java Basics - Anfänger-Themen 2
T Zahlen mit Bubblesort sortieren Java Basics - Anfänger-Themen 2
D Bubblesort und Array Java Basics - Anfänger-Themen 6
T Bubblesort Java Basics - Anfänger-Themen 5
L Bubblesort funzt nicht Java Basics - Anfänger-Themen 3
N bubblesort Java Basics - Anfänger-Themen 4
T BubbleSort optimieren ??? Java Basics - Anfänger-Themen 26

Ähnliche Java Themen

Neue Themen


Oben