Quicksort

[funnybox2006]

Hallo,

 

ich habe eine Programmier Aufgabe bearbeitet in der es darum ging Quicksort auf verschiedene unsortierte Dateien(Tabellen) anzuwenden.

Dabei werden 4 Dateien mit float Zufallszahlen erzeugt (Das Erzeugen übernimmt ein fertiges Programm vom Dozent).

 

Datei1: 10000 Zufallszahlen

Datei2: 30000

Datei3: 40000

Datei4: 20000

 

Bei diesen Dateien sollen nun die Anzahl der Vergleiche und die Anzahl der Durchgeführten Tauschvorgänge gemessen werden.

Wieviele müssten das denn ca. sein. Auf jeden Fall meinte der Dozent, dass an meinem Algorithmus was nicht stimmen kann, da die Anzahl der Tauschvorgänge bzw. Vergleiche um ein vielfaches zu hoch sei.

 

Leider habe ich keine Ahnung wieviel das sein müsste...

Vielleicht kann ja jemand helfen.

 

Gruß, Funnybox

[Creamy]

Also Quicksort hat im best case und average Case eine Laufzeit von n log(n), und im worst case von n²

 

Für eine detailasuwertung müsste man wissen, wie du dein Pivotelement wählst. Du kannst dir ja jedesmal an einem Vergleichsvorgang einen Counter einbauen den du dann erhöhst, genau so bei Tauschvorgängen.

 

Dann weisst du exakt wieviel du hast.

 

Aber wie gesagt, es sollten auf keinen Fall mehr als n² Operationen benötigt sein.

 

Quicksort an sich hast du verstanden nach dem divide & conquer Ansatz?

[funnybox2006]

Hi, danke für die Antwort.

 

Ja hab den Quicksort verstanden! Genau das mit dem Counter erhöhen mache ich auch bei Vergleichen und Tauschvorgängen. Gebe die Werte dann in der Console aus. Trotzdem meinte der Dozent, dass die Anzahl viel zu hoch sei.

 

Dabei habe ich eigentlich die Standardimplementierung des Quicksort genutzt, die überall zu finden ist.

 

Bringt es dir was wenn ich meinen C++ Datei mit dem Quicksort hier mal poste?

 

Gruß, funnybox

[Creamy]

Jo mach ruhig, vielleicht kuckt sichs noch einer an Packs aber bitte in CODE Tags.

 

Was sind denn deine Werte?

[funnybox2006]

Alles klar, ich poste den Code heute Abend wenn ich zu Hause bin!

Danke soweit schonmal.

Meine Werte sind float Zufallszahlen. Ich poste den Code der die Zafallszahlen generiert dann ebenfalls mal.

[funnybox2006]

Hier mal der Algorithmus:

 

ULARGE_INTEGER Sortierungsalgorithmen::Quiksort (Messung * Tabelle, long links, long rechts)
{
	ULARGE_INTEGER Aufwand;
	Aufwand.HighPart = 0;
	Aufwand.LowPart = 0;
	Messung temp;
	ULARGE_INTEGER rauf,runter;// Rückgabewerte der Rekursion


     int i=links, j=rechts;
     Messung x=Tabelle[(links+rechts)/2];

     //  Aufteilung
     while (i<=j)
     {    
	while (Tabelle[i].operator <(x)) 
    {	
		Aufwand.LowPart++; //Vergleich
		i++;
	}
	while (Tabelle[j].operator >(x))
	{	
		Aufwand.LowPart++; // Vergleich
		j--;
	}
       if (i<=j)
       {
		temp = Tabelle[j];
		Tabelle[j] = Tabelle[i];
		Tabelle[i] = temp;
           i++; j--;
		Aufwand.HighPart++; // Tauschvorgang
       }
     }

     rauf.HighPart = 0;
  rauf.LowPart = 0;
  runter.HighPart = 0;
  runter.LowPart = 0;

     // Rekursion
     if (links<j) 
	  rauf = Quiksort(Tabelle, links, j);

  if (i<rechts) 
	  runter = Quiksort(Tabelle, i, rechts);

  Aufwand.HighPart += rauf.HighPart+runter.HighPart;
  Aufwand.LowPart += rauf.LowPart+runter.LowPart;

  return Aufwand;
}

 

Und hier das Programm des Dozenten der 4 Dateien mit Zufallszahlen generiert. Ein Eintrag in der "Tabelle" ist vom Typ Messung.

 

#include <windows.h>


class Messung
{
BYTE		Messstelle;
float		Messwert;  
LONGLONG	Timestamp;
char		Reserve [1000];

public:

Messung ();
};

Messung::Messung ()
{
SYSTEMTIME st;
FILETIME   ft;
LONGLONG * t = (LONGLONG *) &ft;
Messstelle	= rand();
Messwert	= (float) rand () / 1000;
GetSystemTime (&st);
SystemTimeToFileTime (&st,&ft);
Timestamp = * t + rand ();
}

#define Anzahl_1 1000//00
#define Anzahl_2 3000//00
#define Anzahl_3 4000//00
#define Anzahl_4 2000//00

Messung Tabelle_1 [Anzahl_1];
Messung Tabelle_2 [Anzahl_2];
Messung Tabelle_3 [Anzahl_3];
Messung Tabelle_4 [Anzahl_4];

int main ()
{
DWORD size = sizeof (Messung);
DWORD geschrieben;
HANDLE Datei;
Datei = CreateFile ("MesswertTabelle_1.dat",
							GENERIC_WRITE,
							0,
							NULL,
							CREATE_ALWAYS,
							0,
							NULL);

WriteFile (Datei,Tabelle_1,Anzahl_1 * size,&geschrieben,NULL);

CloseHandle (Datei);

Datei = CreateFile ("MesswertTabelle_2.dat",
							GENERIC_WRITE,
							0,
							NULL,
							CREATE_ALWAYS,
							0,
							NULL);

WriteFile (Datei,Tabelle_2,Anzahl_2 * size,&geschrieben,NULL);

CloseHandle (Datei);

Datei = CreateFile ("MesswertTabelle_3.dat",
							GENERIC_WRITE,
							0,
							NULL,
							CREATE_ALWAYS,
							0,
							NULL);

WriteFile (Datei,Tabelle_3,Anzahl_3 * size,&geschrieben,NULL);

CloseHandle (Datei);

Datei = CreateFile ("MesswertTabelle_4.dat",
							GENERIC_WRITE,
							0,
							NULL,
							CREATE_ALWAYS,
							0,
							NULL);

WriteFile (Datei,Tabelle_4,Anzahl_4 * size,&geschrieben,NULL);

CloseHandle (Datei);

return 0;
}

[Creamy]

Ich denke das Problem liegt in der Wahl deines Anfangselements.

 

(links+rechts)/2

 

Ist nicht so optimal. Besser ist da der Median.

Ich bin aber auch nicht so fit in C++

Java ist eher mein Ding

 

Analysier mal deinen Algo im Debugger und arbeite mal Schritt für Schritt mit ner gleichen Menge als Input ab, dann siehst du meistens schnell wos klemmt.

[funnybox2006]

Mhm hab jetzt mal n paar Durchläufe gemacht. Die Anzahl der Tauschvorgänge bleibt immer unter n*log(n).

n*log(n) ist ja der Worst Case. Verstehe also nicht was der Dozent will !? Muss glaub ich da nochma nachhaken.

[DonCamillo]

Die Wahl des Pivot ist sicherlich entscheidend.

Bei mir ist das Pivotelement in der Regel das erste oder zweite Element in der Liste.

 

 

typename Iter::value_type pivot;
equal_to<typename Iter::value_type> eq;

pivot=*beg;
for(it=beg;it!=end&&eq(*it,*beg);++it);
if(it==end) return;
pivot=max(pivot,*it);

[funnybox2006]

@DonCamillo: Was issn das fürne Syntax? Sieht C ähnlich aber isses doch nicht wirklich oder!?

 

Jetzt mal allgemein:

Was ist denn die klügste Wahl des Pivotelementes wenn es darum geht zufällige unsotierte Listen zu sortieren?

Das erste oder zweite Element nehmen wie DonCamillo vorschlägt oder den Median aus links rechts und mitte zu bilden wie Creamy sagt.

 

Btw: Wie bildet man den Median aus 3 Werten? Werd aus wikipedia nicht so richtig schlau.

 

Gruß, Funnybox

[DonCamillo]

C++

Der Code stammt aus meinem Quicksort unter Verwendung von Iteratoren und braucht für 140.000 int Werte ca. 50ms.

 

Ein Algorithmus sollte natürlich möglichst schnell sein, deshalb ist der Aufwand zur Optimierung des Pivotelementes meist größer als der letztendliche Nutzen. Beim Quicksort genügt die Auswahl eines zufälligen Elementes. Ich gehe dabei aber sicher, dass es noch mindestens ein kleineres gibt, damit keine Liste leer bleibt. Eine Vorsortierung kann ein Quicksort sowieso nicht berücksichtigen.

[poci]

Hab nur mal schnell überflogen und wollte nur mal anmerken, dass man nicht den Median nehmen sollte, da es einfach schon ein Aufwand von O(n) mit sich bringt. Das Element in der Mitte ist schon OK

[Aikonia]

Btw: Wie bildet man den Median aus 3 Werten? Werd aus wikipedia nicht so richtig schlau.

 

Also Median kenn ich so, man ordnet die Werte der Größe nach und streicht dann immer Abwechselnd am Anfang und am Ende ne Zahl weg, also einfach die mittlere nehmen...., kenn das jetzt nur noch von Kennzahlen aus´m QM, hat halt den Vorteil, dass dabei Ausreisser nicht berücksichtigt werden.

 

z.B.: 4,9,7, sortiert: 4,7,9 -> Also Median ist dann 7, wenn zwei übrig bleiben, dann nimmt man davon den Mittelwert.

 

 

Grüße

[Creamy]

Hab nur mal schnell überflogen und wollte nur mal anmerken, dass man nicht den Median nehmen sollte, da es einfach schon ein Aufwand von O(n) mit sich bringt. Das Element in der Mitte ist schon OK

 

Na dann hör mal ne Vorlesung über Entwurf und Analyse von Algortihmen, dann wirst du merken, das ein linearer Aufwand vernachlässigbar ist

Man muss natürlich in größeren Dimensionen denken, also 10000 Zahlen zu sortieren

 

Ich persönlich finde ja Heapsort noch das beste, gerade weil das die Datenstruktur der Halde so genial aufgebaut ist.

 

Wegen dem Median, bei nicht allzuvielen Aussreissern ist die Wahl des logisch mittleren Elements durchaus ausreichend.

 

Aber worum gehts jetzt hier?

Komplexität von Sortieralgorithmen? Oder um Funnybox` Implementierung?

[poci]

Ich habe natürlich schon "Algorithmen und Datenstrukturen" besucht. Ich muss dir allerdings recht geben das es is allgemeinen Fall vernachlässigbar ist. Beim QuickSort mit Medianbestimmung jedoch nicht.

[Creamy]

Bei richtig großen n ist aber die Effizienz eines 3er Medians wesentlich höher. Den Beweis hab ich noch irgendwo hier... Perplexerweise bricht das bei nem 5er Median wieder stark ein...

 

Naja, Komplexitätstheorie ist ne Lehre für sich

 

Aber schön, das es hier auch Leute gibt, mit denen man über sowas diskutieren kann

[funnybox2006]

Naja - es geht ja darum, dass n*log(n) nicht überschritten wird. Und das tut es in meiner Lösung nicht. Also das Ergebnis von n*log(n) bezieht sich doch auf die Anzahl der Tauschvorgänge richtig !?