BubbleSort optimieren ???

[Thanni]

hallo ihrse

kann man das noch weiter optimieren ?
wenn ja, wie wo und warum?
vielleicht bei den array zugriffen ? muss ich das array überhaupt zurück über geben oder wird eh nur eine referenz übergeben und das ausgangsarray ist eh schon sortiert ?

    //sortiert ein unsortiertes array mit strings und gibt es zurück
    private String[] sort(String[] tmp){
        int lastChange=tmp.length-1, i, limit;
        String temp;
        
        while(lastChange!= 0){
            limit=lastChange;
            lastChange=0;
            
            for(i=0; i<limit; i++){
                if(tmp[i].compareTo(tmp[i+1])>0){
                    lastChange=i;
                    temp=tmp[i+1];
                    tmp[i+1]=tmp[i];
                    tmp[i]=temp;
                }
            }
        }
        return(tmp);
    }

gruß thanni

 

[citizen_erased]

du könntest mit StringBuffer anstelle von String arbeiten, solange die zeichenketten bearbeitet werden

 

[bygones]

du könntest mit StringBuffer anstelle von String arbeiten, solange die zeichenketten bearbeitet werden

wo wird den der String verändert ??

Mir fällt auf die schnelle aber nichts ein - wie willst du die array zugriffe optimieren ?!

Aber brauchst nicht den String[] nicht zurückgeben - wenn du die Methode mit einem String[] aufrust, ist dieser aufgrund der referenzen dann sortiert !

 

[citizen_erased]

wo wird den der String verändert ??

                   temp=tmp[i+1];
                    tmp[i+1]=tmp[i];
                    tmp[i]=temp;

ein String-Objekt ist unveränderlich. soll der inhalt verändert werden, muss ein neues String-Objekt geschaffen werden und die referenz wird von der alten adresse zur neuen "umgeboben".
beim stringbuffer-objekt muss nur der inhalt ausgetauscht werden.

 

[bygones]

also entweder irre ich mich jetzt total, aber bei der Operation werden die Objekte an sich nicht verändert !!

Hierbei handelt es sich einfach um eine Veränderung der Referenzen, die Objekte an sich bleiben gleich, daher würde ein Array von StringBuffern nichts ändern - die Operation sähe genauso aus !!

 

[citizen_erased]

 temp=tmp[i+1];

hier wird dem String-Objekt temp der inhalt des String-Objektes temp[i+1] zugewiesen. das geht aber nicht direkt. es wird zunächst ein neues String-Objekt erzeugt.

aus "java ist eine insel":

Die Klasse String repräsentiert Zeichenketten, die sich nicht ändern, zum Beispiel in einem println()-Aufruf. Mit Objekten vom Typ String lässt sich suchen und vergleichen, aber es können keine Zeichen im String verändert werden. Es gibt einige Methoden, die scheinbar Veränderungen an Strings vornehmen, aber sie erzeugen in Wahrheit neue String-Objekte, die die veränderten Zeichenreihen repräsentieren. So entsteht beim Aneinanderhängen zweier String-Objekte als Ergebnis ein drittes String-Objekt für die zusammengefügte Zeichenreihe. Die Klasse StringBuffer repräsentiert im Gegensatz dazu dynamische, beliebig änderbare Zeichenreihen.

 

[bygones]

Sorry, aber so ist das meiner Ansicht nach nicht gemeint.

Was die Klasse String angeht hast du recht. Jede Änderung in einem String Objekt führt dazu, dass ein neues String Objekt alloziert wird.

Hier ist es aber meiner Ansicht nach nur ein Referenz verschieben:

String temp;
temp = tmp[i+1]

Die Referenz, die auf tmp die zuerst auf null zeigte, zeigt nun auf tmp[i+1]. D.h. es werden keine Objektinformationen modifiziert.
temp und tmp sind ja nur Referenzen auf Strings im Speicher. Die Strings an sich bleiben immer gleich, die Referenzen auf sie werden nur umhergeschoben !!

Anders sähe das aus wenn es irgendwie so hieße.

String temp;
temp = tmp[i+1].substring(0,5);

Wie würde das deiner Meinung nach mit StringBuffern aussehen ???

Gibt es irgendjemand der einer der beiden Meinungen bestätigen kann ??

 

[Beni]

deathbyaclown hat recht. Hier wird absolut nichts an den Strings verändert. Man kann es einfach testen:

String[] test = new String[ 3 ];
test[0] = new String( "a" );
test[1] = new String( "a" );
test[2] = test[1];

System.out.println( test[0] == test[1] );  // false
System.out.println( test[0] == test[2] );  // false
System.out.println( test[1] == test[2] );  // true, weil es derselbe String ist

mfg Beni

 

[citizen_erased]

ich glaube, ihr habt recht

Der Wert einer String-Variablen ist eine Referenz und kann verändert werden, so dass er z.B. auf einen anderen String zeigt. Dagegen ist der Zielwert einer String-Variablen (der eigentliche String) unveränderbar. Wenn man den Zielwert verändern möchte, sollte man StringBuffer-Objekte verwenden.

durch die zuweisung ändert sich die referenz. das geht dann wohl....

 

[bygones]

Der Wert einer String-Variablen ist eine Referenz und kann verändert werden, so dass er z.B. auf einen anderen String zeigt. Dagegen ist der Zielwert einer String-Variablen (der eigentliche String) unveränderbar. Wenn man den Zielwert verändern möchte, sollte man StringBuffer-Objekte verwenden.

Das sagt doch das, was ich sage !

Mit dem Aufruf:

String temp;
temp = tmp[i+1];

Verändere ich eine String Variable (also eine Referenz - siehe oben). Sie zeigt nun auf einen anderen String.

Der Zielwert wird hier gar nicht angefasst !!

String einString = "Das ist ein String";

Hier ist "einString" die Stringvariable bzw. die Referenz. Die kann man auf beliebige String objekte zeigen ohne ein neues String Objekt zu erzeugen !

"Das ist ein String" ist dagegen der Zielwert. Würdest du den verändern, so erzeugst du ein neues String Objekt !!

String einString = "Das ist ein String";
String einAndererString = "Das ist ein anderer String";
einString = einAndererString; // <-- hier wird die Referenz verändert, kein neues Objekt
einAndererString = einAndererString.substring(5); // <-- hier greifst du auf den Zielwert zu und änderst ihn --> neues Objekt

Als weiteren Beweis nimm Benis bespiel. Würde mit " = " ein neues Objekt angelegt, so würde der vergleich " == " false liefern - was er aber nicht tut !!

[EDIT: Hey, dass ist nicht fair - seinen Post zu ändern, wären ich drauf antworte :cry: :wink: - ich hoffe du verstehst auch warum]

 

[Thanni]

Mir fällt auf die schnelle aber nichts ein - wie willst du die array zugriffe optimieren ?!

hm vielleicht ne array list oder collection ? was ist denn das schnellste?

Aber brauchst nicht den String[] nicht zurückgeben - wenn du die Methode mit einem String[] aufrust, ist dieser aufgrund der referenzen dann sortiert !

gut dachte ich mir schon fast habe mich gewundert warum beim debuggen schon das richtige drinstand


und zum thema stringbuffer
wenn string keine refferenz wäre und ich buffer nehmen müsste ... müsste ich trotzdem einen string dem array zuweisen und mit dem befehl ...tmp=buffer.toString() lege ich doch sicher einen neuen string an auch wenn der nur temporär ist und die refferenz kommt wieder in das array ? also hätte ich nichts gekonnt

optimierung in der hinsicht das array vielleicht von vorne und hinten gleichzeitig zu sortieren ?
auch wenn ich mir nicht vorstellen kann wie

oder bei 2 gleichen strings noch was geschicktes einbauen damit zb

i=0 b
i=1 a
i=2 a

das b nicht mit beiden a's durchgetauscht werden muss


eine optimiereung habe ich ja schon eingebaut (lastChange) so das sich die zu sortierenden werte mit zunehmender sortierung verringert

gruß thanni

oder gibt es eine schnellere methode 2 strings zu tauschen ? bei zahlen müsste das ja so gehen :
int a=3,b=4;

b^=a;
a^=b;
b^=a; aber xor klappt bei strings ja nicht

 

[Roar]

genau. mach doch einfach ne ArrayList, pack die String[] elemente da rein und dann sort(); und ferti ist :] da braucht man kann bubblesort mehr

 

[Anubis]

VIEL schneller ist der Quicksort:

public void quickSort(int L, int R) {
	int P = array[(L+R)/2];
	int l = L;
	int r = R;

	if (L < R) {
		while( l <= r) {
			while(array[l] < P) l++;
			while(P < array[r]) r--;

			if (l <= r) {
				int tmp = array[l];
				array[l] = array[r];
				array[r] = tmp;
			}
		}
		quickSort(L,r);
		quickSort(l,R);
	}
}

Teste mal dein Bubble-Sort bei 100.000 Elementen und dann mal den QuickSort mit 100.000 Elementen. Du wirst den Unterschied merken.

 

[Thanni]

genau. mach doch einfach ne ArrayList, pack die String[] elemente da rein und dann sort(); und ferti ist :] da braucht man kann bubblesort mehr

kleiner scherzkeks
ich wollte keinen vorhandene sort methode nutzen
sondern selber eine machen und meine geht ja ich will sie halt nur verbessern
is ja nur ne denksport aufgabe zu rumtesten ist ja nicht so das ich das brauchen würde

@anubis erläuter mal dein code wo hast du dein array mit den werten wo übergibst du das ?

 

[Roar]

achsoo das hab ich gar nicht gewusst *g*
schau mal bei deinem sdk im demo verzeichnis bei den applets. da ist ein beispiel zu quicksort, bubblesort und noch son ding. das kann evtl. weiterhelfen

 

[citizen_erased]

[EDIT: Hey, dass ist nicht fair - seinen Post zu ändern, wären ich drauf antworte  :cry:  :wink: - ich hoffe du verstehst auch warum][/quote]

moin!
ja, mir ist die sache beim schreiben klar geworden. das war eine gewinnbringende diskussion (jedenfalls für mich).
mehr davon!

 

[bygones]

Mir fällt auf die schnelle aber nichts ein - wie willst du die array zugriffe optimieren ?!

hm vielleicht ne array list oder collection ? was ist denn das schnellste?

Davon würde ich abraten. Z.b. Arraylist ist nichts anderes als eine Liste von Object Arrays. Bei jedem Zugriff auf ein Element wird getestet, ob der gegebenen Index innerhalb des Ranges liegt. Somit würdest du keinen gewinn zu einem normalen Zugriff bekommen, sondern eher einen Verlust !

Zum optimieren:
Nimm nicht Bubbelsort - Quicksort oder MergeSort sind wesentlich schneller:

Allgemein sind meines Wissens Quicksort und MergeSort am Besten, da sie auch im Avergage Case ne Komplexität von O(n log n) haben !

Achja, und ich würde nicht einen String[] übergeben, sondern ein Comparable[] - dann kann deine Methode alle Objekte sortieren, die das Interface Comparable implementieren - somit bist du nicht auf Strings angwiesen

 

[Thanni]

wie gesagt es war nur zum testen und bissel rumspielen
ich wollte ja unbedingt bubbelsort nehmen nicht quick da ich eh nicht weiss wie der allgo richtig funktioniert gibts irgendwo ein PAP ? zu quicksort aus dem code werde ich nicht wirklich schlau


und ich habe halt string genommen weil ich eine textarea voll schreibe und die sachen da drin sortiere und da sind eh nur strings drin



gruß thanni

 

[Anubis]

@anubis erläuter mal dein code wo hast du dein array mit den werten wo übergibst du das ?

Also: Der Einfachheit halber bin ich von einem Integer Array ausgegangen. Das Array kann irgendwie reingeschriben werden, oder gelesen werden. Ich zeige nur eine Methode.

l und r sind Indexvariablen für das Teilen. Als Referensvariable nehme ich das Mittlere Element P. l wird so lange erhöht mit array[l] nicht merh kleiner ist als P. Bei r solagne runter bis array[r] nicht mehr grösser ist als P. Dann wird vertauscht. Das geht solange, bis l >= r.
Dann wird das selbe nochmal von L bis r und von l bis R gemacht.

Ps: Dass programm mit quickSort(0,array.length-1) aufrufen, sonst funktioniert es nicht richtig.

 

[Thanni]

achsoo das hab ich gar nicht gewusst *g*
schau mal bei deinem sdk im demo verzeichnis bei den applets. da ist ein beispiel zu quicksort, bubblesort und noch son ding. das kann evtl. weiterhelfen

so ich habe die bubblesort klasse mal verändert...
tauscht bitte mal bei euch das ganze gegen das hier aus und vergleicht mal habe ich die pause an die falsche stelle gepackt ??? oder ist meine tatsächlich schneller als der quicksort ???

void sort(int a[]) throws Exception {
	 //3 bubbels eine von vorne eine vonhinten die sich überkreuzen und einen große die das ganze ergänzt
        int lastChangeUp=a.length-1, lastChangeDown=0;
        int i, k, limitForUp, limitForDown;
        boolean finish=false;
        int temp;
        
        while(finish==false){
            
            finish=true;
            limitForUp=lastChangeUp;
            limitForDown=lastChangeDown;
            lastChangeUp=limitForDown;
            lastChangeDown=limitForUp;
            for(i=limitForDown, k=limitForUp; (i<limitForUp || k>limitForDown); i++, k--){
               	if (stopRequested) {
		    return;
		}
                if(i<=k){
                    if(a[i]>a[k]){
                        temp=a[k];
                        a[k]=a[i];
                        a[i]=temp;
                        finish=false;
                 
                    }
                }
                else{
                    if(a[i]< a[k]){
                        temp=a[k];
                        a[k]=a[i];
                        a[i]=temp;
                        finish=false;
                   
                    } 
                } 
                                
                if(a[i]>a[i+1]){
                    lastChangeUp=i;
                    temp=a[i+1];
                    a[i+1]=a[i];
                    a[i]=temp;
                    finish=false;
                  
                }
                if(a[k]<a[k-1]){
                    lastChangeDown=k;
                    temp=a[k];
                    a[k]=a[k-1];
                    a[k-1]=temp;
                    finish=false;
               
                }
            pause(limitForDown,limitForUp);     
            }
        } 
        return;
    }

gruß thanni gibts das was ich hier fabrizierrt habe schon unter einem anderen namen ??
is glaube aber noch irgendwo ein kleiner fehler drin manchmal wird nicht richtig sortiert bzw etwas bleibt übrig ;(

 

[Anubis]

Vielleicht bist du glücklich mit deinem Bubble-Sorter. Ich wärs nicht weil
1. zu großer Quelltext.
2. zu langsam.

Vergleich doch mal deinem Quellcode mit meinem, Thanni. Du wirst sehen, dass er wesendlich kürzer ist und obendrein noch schneller.
Aber du sagtest ja dass du einen Bubble-Sorter optimieren willst.

Mal ein paar zahlen:
Bei 100000 Elementen:
Bubblesort: mindestens 5000050000 Arrayzugriffe
Quicksort: etwa 166097 Arrayzugriffe
_______________________________________________
Bubble-Sort braucht 30103 mal länger.

Wie bin ich drauf gekomen:
Bubblesort hat eine Laufzeit von (n²+n)/2
Quicksort hingegen n*log n (Basis 2)
--------
100000 Eigesetzt ergibt die obigen werte.

====> Du kannst deinen Bubble-Sort erheblich optimieren, indem du ihn durch ein Quicksort ersetzt.

 

[Thanni]

Vielleicht bist du glücklich mit deinem Bubble-Sorter. Ich wärs nicht weil
1. zu großer Quelltext.
2. zu langsam.

Vergleich doch mal deinem Quellcode mit meinem, Thanni. Du wirst sehen, dass er wesendlich kürzer ist und obendrein noch schneller.
Aber du sagtest ja dass du einen Bubble-Sorter optimieren willst.

Mal ein paar zahlen:
Bei 100000 Elementen:
Bubblesort: mindestens 5000050000 Arrayzugriffe
Quicksort: etwa 166097 Arrayzugriffe
_______________________________________________
Bubble-Sort braucht 30103 mal länger.

Wie bin ich drauf gekomen:
Bubblesort hat eine Laufzeit von (n²+n)/2
Quicksort hingegen n*log n (Basis 2)
--------
100000 Eigesetzt ergibt die obigen werte.

====> Du kannst deinen Bubble-Sort erheblich optimieren, indem du ihn durch ein Quicksort ersetzt.

langsam ? nicht das was da als letztes von mir gepostet wurde tausch doch mal das mit dem normalen bubbelsort aus und guck/starte das beispiel vom sdk dann nochmals, also meins war ANSCHEIND schneller als der quicksort
ich meine auch mal gelesen zu haben das der quicksort im ungüstigstenfall so langsam wie dernormale bubbelsort ist
nur mein 3er bubbelsort hat immer nen guten durchschnitt

ps bitte probiert es mal aus vielleicht habe ich auch ur falsch geguckt

gruß thanni

 

[Anubis]

Ich hab deinen mal als Application ausprobiert. Bei 100000 Elementen braucht deiner Stolze 19 sekunden. Der Quicksort braucht dafür nur 0.18 Sekunden.

 

[Grizzly]

VIEL schneller ist der Quicksort:[...]
Teste mal dein Bubble-Sort bei 100.000 Elementen und dann mal den QuickSort mit 100.000 Elementen. Du wirst den Unterschied merken.

Ich hab' mal Spasses halber die QuickSort-Methode in ein kleines Programm übernommen. Aber irgendwie scheint die Methode nicht richtig zu arbeiten. Sie bleibt immer an irgendeinem Wert hängen und ruft sich dann endlos rekursiv auf. Irgendwann kommt dann natürlich ein Overflow.

Hier mal den Code (mit einigen Debugging-Ausgaben):

public class Test {

	public static void main(String[] args) {
		int[] array = new int[]{10, 7, 8, 1, 4};
		System.out.println(getArrayString(array));
		quickSort(0, array.length - 1, array);
		System.out.println(getArrayString(array));
	}
	
	public static void quickSort(final int le, final int re, int[] array) {
		int p = array[(le + re) / 2];
		int li = le;
		int ri = re;
		
		System.out.println("quickSort(" + le + ", " + re + ")");
		if (le < re) {
			System.out.print("\tp = " + p);
			System.out.print("; li = " + li + " / " + array[li]);
			System.out.println("; ri = " + ri + " / " + array[ri]);
			while (li <= ri) {
				while (array[li] < p) li++;
				while (p < array[ri]) ri--;
				System.out.print("\tp = " + p);
				System.out.print("; li = " + li + " / " + array[li]);
				System.out.println("; ri = " + ri + " / " + array[ri]);
				
				if (li <= ri) {
					swap(li, ri, array);
					System.out.println("\t" + getArrayString(array));
				}
			}
			quickSort(le, ri, array);
			quickSort(li, re, array);
		}
	}
	
	public static void swap(final int i1, final int i2, int[] array) {
		int tmp;
		
		tmp = array[i1];
		array[i1] = array[i2];
		array[i2] = tmp;
	}
	
	public static String getArrayString(int[] array) {
		StringBuffer sb;
		
		sb = new StringBuffer();
		sb.append("Array = {");
		for (int index = 0; index < array.length; index++) {
			sb.append(array[index]);
			if (index < array.length - 1) {
				sb.append(", ");
			}
		}
		sb.append("}");
		return sb.toString();
	}
}

Hat die Methode einen Fehler oder liegt der Fehler bei mir? ???:L

 

[Anubis]

Mein Fehler in dem vertauschensteil
Du müsstest folgenden Teil ändern:

if (li <= ri) { 
	swap(li, ri, array); 
	System.out.println("\t" + getArrayString(array)); 
}

nach

if (li <= ri) { 
	swap(li, ri, array); 
	li++;
	ri--;
	System.out.println("\t" + getArrayString(array)); 
}

Sonst hast du eine Endlos Aufteilungs Schleife, der Rekursionsteil wird nie aufgerufen werden. Aber es ist keine Endlosrekursion.

Sorry mein Fehler im Code, ich hab ihn einfach aus dem Kopf geschrieben und was vergessen.

 

[Grizzly]

[...]
Sonst hast du eine Endlos Aufteilungs Schleife, der Rekursionsteil wird nie aufgerufen werden. Aber es ist keine Endlosrekursion.[...]

Ähh, meinte ich doch... :wink:

[...]Sorry mein Fehler im Code, ich hab ihn einfach aus dem Kopf geschrieben und was vergessen.

Danke für die Berichtigung. Bis jetzt kannte bzw. konnte ich nur BubbleSort :### . Jetzt bin ich schon wieder etwas schlauer

 

[Thanni]

Ich hab deinen mal als Application ausprobiert. Bei 100000 Elementen braucht deiner Stolze 19 sekunden. Der Quicksort braucht dafür nur 0.18 Sekunden.

schicke deine application mal an thanatos@gmx.org

bitte