Sortieralgorithmen - Bewegungen und Vergleiche

[witch doctor]

In Informatik hatten wir mal die Aufgabe versch. Sortieralgorithmen (Sortieren durch Einfügen, durch auswahl, Bubblesort etc)

theoretisch auf ein Feld anzuwenden und dann zu ermitteln wieviel Bewegungen und Vergleiche dieser Algorithmus benötigt.

Ich komme da nur nie drauf! Den Algorithmus stumpf auszuführen ist ja nicht das Problem, aber auf die Vergleiche und Bewegungen zu kommen!

Wer kennt sich damit aus und könnte mir helfen? Ich schicke dann auch gerne meine Unterlagen per mail.

[Der Kleine]

Sind die Algorithmen verstanden?

Falls ja, einfach per Hand (also Zettel und Stift) mal durchspielen für drei Werte, dann vier Werte usw.

Es sollte nicht so schwer fallen.

Falls weiterhin Interesse besteht, habe erst Ende nächster Woche Zeit ein wenig per PM zu diskutieren.

[witch doctor]

Ich denke schon, dass ich die Algorithmen verstanden habe.

Ich mache ja auch die gleichen Schritte, wie die anderen.

Jedoch komme ich nicht auf dei Bewegungen und Vergleiche, weil ich nicht weiß wie die die ermittelt (nicht rechnerisch!) haben. Ich weiß nicht, wo die überall Bewegungen und Vergleiche sehen.

Werde hier noch einen Algorithmus vorstellen.

[Guybrush Threepwood]

Du mußt doch einfach nur zwei Variablen um 1 hochzählen. Die eine jedesmal wenn

du zwei Werte in deinem Array vergleichst und die andere wenn du zwei Werte

tauschst. Oder hab ich dich falsch verstanden?

Gruß

Guybrush

[gajUli]

Originally posted by Guybrush Threepwood

Du mußt doch einfach nur zwei Variablen um 1 hochzählen. Die eine jedesmal wenn

du zwei Werte in deinem Array vergleichst und die andere wenn du zwei Werte

tauschst. Oder hab ich dich falsch verstanden?

Das frag ich mich auch, aber er soll es wohl theoretisch machen.

[witch doctor]

Ja ich soll es theoretisch machen.

Hier die Aufgabenstellung:

Wenden Sie die folgenden Sortierverfahren auf das Feld

[36, 6, 11, 14, 6, 22, 29, 30]

an und zählen Sie die Anzahl der benötigten Vergleiche und Bewegungen

a) Direktes Einfügen

Ist das Verfahren stabil?

Direkte Auswahl

Ist das Verfahren stabil?

c) Direkter Austausch

Ist das Verfahren stabil?

d) Shakersort

Ist das Verfahren stabil?

e) Quicksort mit Auswahl des jeweils mittleren Elements als Vergleichswert,

Ist das Verfahren stabil?

f) Quicksort mit Auswahl über Dreiermedian,

Ist das Verfahren stabil?

[nic_power]

Falls Du eine Bibliothek in der nähe hast, wirf mal einen Blick in das Standardwerk zu diesem Thema: http://www.amazon.de/exec/obidos/ASIN/0201896850/ref=pd_sim_dp_2/302-6861104-0080059

Leider sind die Bücher (drei Bände) sehr teuer.

Nic

[Buell]

Originally posted by gajUli

Das frag ich mich auch, aber er soll es wohl theoretisch machen.

Zieh Dir das rein:

AD_Script

Den Prof kannst jederzeit anmailen. Kenn ihn persönlich.

Buelli

[witch doctor]

Danke.

Das Script werde ich mir auf jeden Fall ausdrucken und durchlesen.

[hmaas]

Hi,

schau mal unter:

http://www.informatik.fh-trier.de/projekte/vivaldi/beispiele_vivaldi.html

sind verschiedene Sortiermechanismen dargestellt. Besonders interessant sind die Java-Simulationen, wo die Funktionsweise der Sortierung sehr gut dargestellt wird.

Gruß Pönk

[witch doctor]

Ich habe mir gerade mal das Skript von Prof. Kopp durchgelesen bzw. das Quicksort - Verfahren.

Folgendes verstehe ich nicht:

if (right>left)

muss das nicht ungekehrt heißen, also right < left?

Denn wenn rechts hinter dem Pivotelement ein kleineres Element auftaucht vertausche ich es doch mit dem größeren linken Element. Oder verstehe ich das jetzt komplett falsch?

Jedoch haben wir diesen Algorithmus ähnlich geschrieben.

Ich stelle mal zwei Varianten vor und schreibe dran, was ich nicht verstehe.

Erstmal ein ziemlich grober Algorithmus

quicksort (links, rechts)

Vergleichswert = A[(rechts-links+1)/2] // sollte dies nicht einfach

[witch doctor]

Irgendwie war die Nachbearbeitungszeit vorbei.

Dumm gelaufen.

Hier mein Post nochmal, der letzte war nämlich nicht komplett.

Ich habe mir gerade mal das Skript von Prof. Kopp durchgelesen bzw. das Quicksort - Verfahren.

Folgendes verstehe ich nicht:

if (right>left)

muss das nicht ungekehrt heißen, also right < left?

Denn wenn rechts hinter dem Pivotelement ein kleineres Element auftaucht vertausche ich es doch mit dem größeren linken Element. Oder verstehe ich das jetzt komplett falsch?

Jedoch haben wir diesen Algorithmus ähnlich geschrieben.

Ich stelle mal zwei Varianten vor und schreibe dran, was ich nicht verstehe.

Erstmal ein ziemlich grober Algorithmus

quicksort (links, rechts)

Vergleichswert = A[(rechts-links+1)/2]

// sollte dies nicht einfach A[(links+rechts)/ 2 ] lauten?

do //Warum eine do-while Schleife? Macht das Sinn?

{

r:=rechts;

l:=links;

while (A[r]> Vergleichswert do r:=r-1;

while (A[l] < Vergleichswert do l:= l-1;

/* Ich glaube, dass habe ich verstanden.

* Das stellt doch lediglich die Bewegung der Elemente

* dar, oder? Also wenn das rechte Element größer ist

* als der Vergleichswert, dann gehe ein Element weiter.

* Falls ich das falsch verstanden haben sollte,

* korrigiert mich bitte.

*/

if l < r then tausche (l,r);

// Wieso l < r ?

// Müsste es nicht r < l heißen?

// Ich meine ich tausche doch den kleineren

// rechten Wert mit dem größeren linken Wert.

// Oder verstehe ich das falsch?

while (l < r) ; }

// Warum Solange l < r ?

if (links < r) then quicksort (links, r);

if (rechts > l ) then quicksort(l, rechts);

// An dieser Stelle war meine Verwirrung komplett.

// Ich verstehe hier schon die Rekursion und weiß

// selbstverständlich was eine Rekursion ist.

// Was ich da nicht verstehe, sind die beiden

// If-Bedingungen.

// Warum if (links < r) ?

// Warum if (rechts > l) ?

Sorry, aber ich bin total am verzweifeln bei den

Sortieralgorithmen.

Wie wichtig sind die eigentlich? Sehr wichtig, oder?

Hier das ganze nochmal als PASCAL-Programm, welches ich auch nicht wirklich verstanden habe.

Bitte helft mir!!!

Kennt einer zufällig noch eine einfache Java-Unsetzung?

Ich lerne eigentlich JAVA, werde aber bei Algorithmen

mit Pascal zugeschmissen.

Ich komme da total durcheinander.

[hmaas]

Originally posted by witch doctor

Kennt einer zufällig noch eine einfache Java-Unsetzung?

Ich lerne eigentlich JAVA, werde aber bei Algorithmen

mit Pascal zugeschmissen.

Hast du dir eigentlich meinen o.g. link mal angeschaut?

Ich finde es dort sehr ANSCHAULICH dargestellt inclusive Code (denke ist C++, kann aber auch JAVA sein)

Gruß Pönk

[witch doctor]

Originally posted by Pönk

Hast du dir eigentlich meinen o.g. link mal angeschaut?

Ich finde es dort sehr ANSCHAULICH dargestellt inclusive Code (denke ist C++, kann aber auch JAVA sein)

Gruß Pönk

Ja habe ich danach gemacht.

Aber wirklich verstehe ich die algorithmen noch nicht.

Die Animation schaue ich mir nochmal in Ruhe an.

Ist wirklich gut.

Das Programm war Java. Aber wirklich verstanden habe ich es nicht.

[witch doctor]

Aber die Animationen sind genial, wo man genau die Vergleiche und Bewegungen sieht. Danke!! Werde ich sofort weiterempfehlen. :uli

Das Script allerdings auch!

[witch doctor]

Ich verstehe den Algorithmus ab hier nicht

do // Warum eine do-while Schleife?

{

while (x < middleElement)

{

i++;

}

while (middleElement < x[j])

{

j--;

}

if (i <= j) //Verstehe ich nicht. Wenn das linke

// Element kleiner gleich den rechten

// Element ist dann mache das.

// Das linke Element muss doch

// kleiner gleich dem rechten Element

// sein, oder?

{

elementType tmp = x;

x = x[j];

x[j] = tmp;

i++;

j--;

}

} while (i <= j)

if (left < j)

{

quick(x, left, j); //Warum vergleiche ich

// links mit dem rechten

// Element?

}

if (i < right) //Und warum vergleiche ich

// rechts mit dem linken

// Element.

{

quick(x, i, right);

}

}

Helft mir! Ich stehe da komplett auf dem Schlauch! :confused:

[SgtBadAzz]

Originally posted by witch doctor

Ich verstehe den Algorithmus ab hier nicht

...

while (x < middleElement)

{

i++;

}

while (middleElement < x[j])

{

j--;

}

...

Helft mir! Ich stehe da komplett auf dem Schlauch! :confused:

Der 2. Vergleich in der While ist doch falsch oder ? Es muesste doch > oder >=.

die Do-While ist deshalb da , um damit die Sotierroutine durch laufen wird und am Ende wird überprüft ob alles sortiert wurde oder eben nicht.

Kratz Kratz ... wie heisst denn der Algorithmus eigentlich ... ist das eine Art Quicksort ... schon so lange her.

Frank

[witch doctor]

Es ist Quicksort und der Vergleich ist anscheinend richtig.

Ich habe den so in zig Büchern gefunden.

Folgende Variante habe ich auch gefunden, die ich nicht verstehe:

quicksort (links, rechts)

Vergleichswert = A[(rechts-links+1)/2]

// sollte dies nicht einfach A[(links+rechts)/ 2 ] lauten?

do //Warum eine do-while Schleife? Macht das Sinn?

{

r:=rechts;

l:=links;

while (A[r]> Vergleichswert do r:=r-1;

while (A[l] < Vergleichswert do l:= l-1;

/* Ich glaube, dass habe ich verstanden.

* Das stellt doch lediglich die Bewegung der Elemente

* dar, oder? Also wenn das rechte Element größer ist

* als der Vergleichswert, dann gehe ein Element weiter.

* Falls ich das falsch verstanden haben sollte,

* korrigiert mich bitte.

*/

if l < r then tausche (l,r);

// Wieso l < r ?

// Müsste es nicht r < l heißen?

// Ich meine ich tausche doch den kleineren

// rechten Wert mit dem größeren linken Wert.

// Oder verstehe ich das falsch?

while (l < r) ; }

// Warum Solange l < r ?

if (links < r) then quicksort (links, r);

if (rechts > l ) then quicksort(l, rechts);

// An dieser Stelle war meine Verwirrung komplett.

// Ich verstehe hier schon die Rekursion und weiß

// selbstverständlich was eine Rekursion ist.

// Was ich da nicht verstehe, sind die beiden

// If-Bedingungen.

// Warum if (links < r) ?

// Warum if (rechts > l) ?

Dann habe ich noch folgende Variante auf einer Web-Seite gefunden:

Die folgende Funktion quicksort sortiert ein Teilstück des Arrays a vom Index lo bis zum Index hi.

Die Sortierfunktion ist in der Klasse QuickSorter gekapselt. Die Methode sort übergibt das zu sortierende Array an das Array a und ruft quicksort mit dem unteren Index 0 und dem oberen Index a.length-1 auf.

Die hier der Übersichtlichkeit halber verwendete Hilfsfunktion exchange(i, j) vertauscht die Array-Elemente a und a[j].

Die Anweisung zum Sortieren eines Arrays b mit Quicksort lautet

new QuickSorter().sort(;

Es folgt das Programm.

public class QuickSorter

{

private int[] a;

public void sort(int[] a0)

{

a=a0;

quicksort(0, a.length-1);

}

private void quicksort (int lo, int hi)

{

int i=lo, j=hi;

int x=a[(lo+hi)/2];

// Aufteilung

while (i<=j)

{

while (a<x) i++;

while (a[j]>x) j--;

if (i<=j)

{

exchange(i, j);

i++; j--;

}

}

// Rekursion

if (lo<j) quicksort(lo, j);

if (i<hi) quicksort(i, hi);

}

private void exchange(int i, int j)

{

int t=a;

a=a[j];

a[j]=t;

}

} // end class QuickSorter

Könnt ihr mir den erklären?

[Klotzkopp]

Originally posted by witch doctor

// Wieso l < r ?

// Müsste es nicht r < l heißen?

// Ich meine ich tausche doch den kleineren

// rechten Wert mit dem größeren linken Wert.

// Oder verstehe ich das falsch?

Hier werden nicht die Werte verglichen. r und l sind die aktuellen "Suchpositionen". Die beiden Schleifen, die dieser Abfrage jeweils vorausgehen, stellen sicher, dass diese Positionen auf Werten stehen, die ausgetauscht werden müssen (weil diese beiden Schleifen nach genau solchen Werten suchen). Der Austausch darf aber nur gemacht werden, wenn l und r nicht inzwischen "aneinander vorbei gelaufen sind". Daher vorher der Test auf l < r.

[witch doctor]

Also wenn r < l wäre, wären die Zeiger "aneinander vorbeigelaufen" ?

Aber wieso tausche ich dann?

Auch verstehe ich die Anwendung der Rekursion dort nicht.

[Klotzkopp]

Originally posted by witch doctor

Also wenn r < l wäre, wären die Zeiger "aneinander vorbeigelaufen" ?

Ja.

Aber wieso tausche ich dann?

Weil l und r die Positionen von zwei Zahlen sind, die vertauscht werden müssen. Wieso sie das sind, ergibt sich aus den beiden while-Schleifen davor. l und r laufen aufeinander zu. Dabei bleibt l stehen, wenn der Wert an der Position l nicht kleiner als das Vergleichselement ist, und r bleibt stehen, wenn der Wert an der Position r nicht größer als das Vergleichselement ist.

Daher gilt nach den while-Schleifen: A[l] >= Vergleichswert >= A[r]. Darum wird getauscht.

Auch verstehe ich die Anwendung der Rekursion dort nicht.

Naja, nachdem sich l und r begegnet sind, sind wir ja noch nicht fertig. Wir wissen nur, alles was links von l steht, ist kleiner als der Vergleichswert, und alles was rechts von r steht, ist größer als der Vergleichswert. Also werden beide Unterbereiche nochmal sortiert. Das geht üblicherweise solange, bis die Bereiche so klein geworden sind, dass die Sortierung trivial wird (2 Werte oder weniger).

[witch doctor]

Es wird schon klarer!

Ich schaue mir den ALgorithmus nochmal in Ruhe an und melde mich nochmal bei Fragen!

Aber erstmal danke!!!

(Bitte nicht als Spam werten! )

[SgtBadAzz]

Originally posted by witch doctor

Es ist Quicksort und der Vergleich ist anscheinend richtig.

Könnt ihr mir den erklären?

Ahh ok die beiden Vergleiche in den WHiles sind richtig.

Das ist das Prinzip Teile usw.. ... wusste ich doch das es

Quicksort ist ... wie oft durfte ich mich mit dem *******

rumquälen.

Frank

[larzerrus]

wer kann mir den mergesort in java erklären? habe echt keine ahnung wie der funktionieren soll und wie ich den in java realisieren soll?

wäre sehr dankbar über hilfe? :)

[witch doctor]

Originally posted by Pönk

Hi,

schau mal unter:

http://www.informatik.fh-trier.de/projekte/vivaldi/beispiele_vivaldi.html

sind verschiedene Sortiermechanismen dargestellt. Besonders interessant sind die Java-Simulationen, wo die Funktionsweise der Sortierung sehr gut dargestellt wird.

Gruß Pönk

Ich wollte nur sagen, dass ich diese Seite liebe!!!

Die ist super verständlich aufgemacht!!!

Danke!!!