Sortierverfahren

[Gerlon]

Guten Tag,

ich probiere mich gerade an den verschiedenen Sortierverfahren.
Habe die auch denke richtig implementiert, Ergebnis sieht zumindest vernünftig aus.
Nun geht es mir darum die Effektivität zu testen.
Habe dazu Zeit, Anzahl der Verschiebungen und allgemeine Anzahl der Aufrufe versucht zu bestimmen und diese zu vergleichen.
Wollte nun hier einmal nachfragen ob das realistisch aussieht oder ob ich eventuell an falschen Stellen die Counter gesetzt habe.
Bei Selection Sort bin ich mir nicht so sicher, aber normal überprüft er doch jede Position und somit dachte ich das bei 1000 Elementen er das auch 1000x macht. Hoffe ich irre mich nicht total ^_^
Aufjedenfall dachte ich das die Aufrufe = Verschiebungen sein müssen.

ANZAHL Vergleiche bubble-sort: 955044 Selection-sort:1000 quicksort:1343
Anzahl Verschiebungen bubble sort: 251207 Selection-sort:1000 quicksort:3080
Benötigte Zeit von Bubble sort zum Sortieren 27 ms Selection-sort:22 quicksort: ms 1 ms

Das sind die Ergebnisse für 1000 Elemente. Sind Zufallswerte die Überprüft werden das ist mir klar, aber das Verhältnis sollte ja ungefähr immer ähnlich sein von Aufrufen und Verschiebungen, hoffe jemand versteht was ich möchte und das reicht.
Sonst kann ich auch gerne noch Code posten!

mit freundlichen Grüßen

Gerlon

 

[hüteüberhüte]

Problem: Sobald du die Anzahl der Aufrufe oder Verschiebungen "zählst", ist deine Zeitmessung ungenau (denn das Zählen benötigt auch Operationen).

Zeig uns doch mal deine Implementierungen, dann können wir schnell sagen, ob Fehler drin enthalten sind.

Weiteres (zur Laufzeit): Sortierverfahren ? Wikipedia

 

[Timothy Truckle]

[OT]

"Simplicity is the ultimate sophistication" - Leonardo da Vinci

Wenn Du Leonardo schon übersetzt, warum dann nicht in's deutsche?[/OT]
bye
TT

 

[pro2]

Na ja, nur mal eine Randbemerkung, aber wenn du Zeiten haben willst, dann fang doch bei 100k Elementen und mehr an und nicht bei 1k.^^

 

[hüteüberhüte]

[OT]

[OT]Wenn Du Leonardo schon übersetzt, warum dann nicht in's deutsche?[/OT]
bye
TT

Das gehört jetzt nicht zum Thema, ich habe aber sogar gefragt, ob ich die Sig. verwenden darf.

lg[/OT]

 

[Gerlon]

Naja ich möchte eigentlich nicht unbedingt Zeiten wissen, die Tendenz reicht und die ist gegeben, habe mich eventuell etwas unpassend ausgedrückt.
Die Vergleiche und Aufrufe sind mir erstmal wichtiger!
Und da sind glaube noch einige Fehler.

 

[Gerlon]

Gut ich denke ich habe es jetzt verbessert.
Selection sort unterscheidet nun auch richtig wenn Elemente schon richtig vorhanden sind..

Eine Frage bleibt mir noch, es stimmt aber das Quicksort meist mehr Verschiebungen als Aufrufe hat oder nicht?
Bei kleineren sind diese doch eher gleich.
Aber bei größeren Datenmengen ist mir das zumindest aufgefallen das es oftmals doppelt oder 3x soviele Verschiebungen sind.
Kann das jemand bestätigen?

 

[hüteüberhüte]

Eine Frage bleibt mir noch, es stimmt aber das Quicksort meist mehr Verschiebungen als Aufrufe hat oder nicht?

Das ist zu ungenau. Bei Quicksort wird nur ge/vertauscht, wenn zwei Elemente in der falschen Hälfte stehen, ist z.B. bereits sortiert, dann wird natürlich weniger getauscht. Genau so ist es glaub ist auch mit der Anzahl der Aufrufe.

 

[Gerlon]

Hm naja ich habe die Abfrage einmal im Swap part und einmal die Anzahl am Anfang der gesamten Methode gemacht.

	public static void quickSort(Comparable[] produkte) {
		quickSort(produkte, 0, produkte.length-1);
	   }
	   
	   public static void quickSort (Comparable[] produkte, int lowIndex, int highIndex){
		   counterqsanzahl++;//Aufrufe
		
		   if (lowIndex>=highIndex){
		   return;
		   }
		    
		   int pivotIndex=getMedianIndexAsPivotIndex(lowIndex, highIndex);

		   Comparable pivot=produkte[pivotIndex];

		   swapItemsWithIndices(produkte, pivotIndex, highIndex);  

		   int i=lowIndex-1;
		   int j=highIndex;
		    
		   do{
			//<<--- oder hier
		   do {i++;} while (produkte[i].compareTo(pivot)<0);

		   do {j--;} while (produkte[j].compareTo(pivot)>0 &&(j>lowIndex));
		    
		   if (i<j){
			  
		   swapItemsWithIndices(produkte, i, j);
		   }

		   } while (i<j);
		    
		   swapItemsWithIndices(produkte, highIndex, i);
		   quickSort(produkte, lowIndex, i-1); 
		   quickSort(produkte, i+1, highIndex);
		   }
		 
	
		  private static void swapItemsWithIndices(Comparable[] comparableArray, int firstItem, int secondItem) {
			  counterqs++;//Verschiebungen
		
		   final Comparable tempItem=comparableArray[firstItem];
		   comparableArray[firstItem]=comparableArray[secondItem];
		   comparableArray[secondItem]=tempItem;
		
		  }

		   private static int getMedianIndexAsPivotIndex(int lowIndex, int highIndex) {
		   return lowIndex+((highIndex-lowIndex)/2);
		   }
		  
}

so sieht es bisher aus, habe es oben eingeordnet für die Aufrufe und noch einen 2. Kommentar eingefügt wo ich denke es auch noch sein könnte, weiß es aber leider nicht wie hier genau gezählt werden muss
bisher sind die Aufrufe jedenfalls meist deutlich geringer als die Verschiebungen!
Bei den anderen beiden Sortierverfahren war es ja nicht sonderlich schwer aber hier bin ich irgendwie verwirrt ^^

 

[Timothy Truckle]

[OT]

Das gehört jetzt nicht zum Thema, ich habe aber sogar gefragt, ob ich die Sig. verwenden darf. lg

Hätte nicht gedacht, dass Du schon soooo alt bist.. :lol:[/OT]

bye
TT

 

[hüteüberhüte]

[OT]

[OT]Hätte nicht gedacht, dass Du schon soooo alt bist.. :lol:[/OT]

bye
TT

Naja, ich weiß einigermaßen, was sich gehört und was nicht. Du scheinst das (mit 11?) noch nicht so genau zu wissen.

Grüßle LIIII[/OT]

 

[Gerlon]

Schön das hier nur Random Posts gemacht werden..

 

[Logaff]

hiho,

ich hab noch meine Implementierungen für Sortierverfahren aus der Uni hier liegen. Dort sollten auch semptliche Sachen gezählt werden. Wenn du willst kann ich sie dir senden

 

[Gerlon]

Gerne Hab dich bei Skype mal angeschrieben.
Habe jetzt zwar was, aber als Vergleich denke nicht schlecht. Bin nach wie vor nicht sicher mit Quicksort ^_^

Hast du eventuell mal eine Double Linked List sortiert ?

 

[Gerlon]

Ich versuche gerade noch eine DoubleLinkedList zu sortieren. Und zwar mit BubbleSort.

	    boolean changed = false;
	    do {
	        changed = false;
	        
	        for (int a = 0; a < produkte.length - 1; a++) {
	        	counterbubbleanzahl++;
	            if (produkte[a].compareTo(produkte[a + 1]) > 0) {
	            	Comparable tmp = produkte[a];
	                produkte[a] = produkte[a + 1];
	                produkte[a + 1] = tmp;
	                changed = true;
	                counterbubble++;
	            }
	        }
	    } while (changed);

den hier habe ich für int Werte genutzt, da aber meine Liste aus Objekten besteht weiß ich nicht so recht wie ich das anpassen soll
Hoffe das jemand eine Idee hat ^^ bin leider gerade ratlos
schon ein wenig rumprobiert kam aber noch nicht sonderlich viel bei rum ;/

 

[Logaff]

Ne Double Linked List hab ich nicht sortiert ist aber vom prinzip einfach.....man hat ja immer Grundoperationen beim Sortieren wie z.B. swap (vertauschen 2er elemente). Also Implementierst du dir eine Methode swap für deine Linked List (pointer werden umgehängt) und gut ist. Und kannst nach Aussen zu tun als wenn alles Normal ist