3. Erklärung zu diesem Bubblesort

Erklärung zu diesem Bubblesort

  • S

    Ich habe hier eine Implementation von Bubblesort die mir nicht ganz schlüssig ist
    auch Ausgaben in den Interationen schaffen keine Abhilfe, hoffe mir kann jdm
    mal kurz erklären wieso dies funktioniert, auf dem Papier funktioniert es nämlich
    nicht, meinem Verständnis nach.

    for (int j = zahl.length -2; j >= 0; j--) {
			for (int i = 0; i <= j; i++) {
				if (zahl[i] > zahl [i+1]) {
				hilf = zahl[i];
				zahl [i] = zahl[i+1];
				zahl [i+1] = hilf;
			    }
		    }
		}

    Meine Implementation sieht so aus:

    for (int i = 0; i < zahl.length-1; i++) {
			for (int loop = i+1; loop < zahl.length; loop++) {
				if (zahl[loop] < zahl[i]) {
					temp = zahl[i];
					zahl[i] = zahl[loop];
					zahl[loop] = temp;
				}
			}
		}

    Syntax sollte keinem Probleme bereiten, denke ich

    0
  • T

    Vielleicht hilft das hier weiter. Zumindest wird da die gleiche Variante benutzt.

    0
  • V

    Ich würde sagen das ist die Optimierung des Bubble Sort. Und zu dem habe ich folgende Beschreibung hier:
    "Nach dem ersten Komplettdurchlauf durch die Tabelle steht der größte Wert bereits in der letzten Komponente, so dass diese nicht erneut verglichen werden muss (und nach dem zweiten Komplettdurchlauf steht der größte Wert in der letzten Komponente, usw.)"
    Er könnte auch bis length-1 benutzen und dann bis > laufn lassen statt length-2 und dann bist >=.
    Hier mal wie es in Pascal-Pseudocode aussieht, dabei fängt ein Array mit Index 1 an, wobei n der anzahl indexe entspricht (z.B. array von 1-6, dann ist n=6):

    repeat
  tausch:=false
  i:=1
  while i<n
  do if f[i+1]<[i]
     then Tausche die Inhalte von f[i] und f[i+1]
          tausch:=true
     end if
     i:=i+1
  end while
  n:=n+1 // diese zeile fehlt im optimierten bubble sort
until not tausch

    Code-Hacker

    0
  • S

    Nachdem Beispiel in C++ ist es klar 🙂
    Hatte viel zu kompliziert gedacht, weil ich ursprünglich annahm in seinem Code
    steckt nen Fehler weil das eine i eher wie nen j an der Tafel aussah.
    So ist es natürlich logisch 🙂

    0
  • S

    Wollte dieses Beispiel von Vollcard nach Java portieren habe mir jedoch ne
    Endlosschleife gebaut, aber verstehe nicht wieso:

    void bubbleSort(int *array,int size)
{
   int obergrenze=size-1;
   while(obergrenze>0)
   {
      int letzterAustausch=0;
      for(int pos=0;pos<obergrenze;++pos)
      {
         if(array[pos]>array[pos+1])
         {
            swap(&array[pos],&array[pos+1]);
            letzterAustausch=pos;
         };
      };
      obergrenze=letzterAustausch;
   };
};

    Meine Java-Version

    int hilf;
		int obergrenze = zahl.length-1;
		int last_change = 0; 

		while (obergrenze > 0) {

			for (int i = 0; i < obergrenze; i++) {
				if (zahl[i] > zahl [i+1]) {
					hilf = zahl[i];
					zahl [i] = zahl[i+1];
					zahl [i+1] = hilf;
					last_change = i;
				}
			}
			obergrenze = last_change;
		}

    Edit:
    Habe ihn eben gefunden,das int last_change = 0; muss innerhalb der while-schleife
    sein, aber ich verstehe nicht wieso 😕

    Edit2:
    Kann es sein, dass sonst last_change immer den Wert den es einmal in i erhalten
    hat behält und somit immer größer 0 ist?

    0
Anmelden zum Antworten