Quicksort Algo in den Folien

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Siehe mein Edit, da hast du eine mögliche Lösung, die Quicksort selbst korrigiert.

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Beitrag von bruse »

Twister11 hat geschrieben:Ja wenn ich anfange da irgendwie am Quicksort noch andere Sorts reinzuwursten, dann kann ich es auch gleich sein lassen und direkt MergeSort benutzen.
Es gibt für jede Pivotstrategie Eingaben, für die diese Strategie nicht gut funktioniert. Man kann halt nicht alles haben, und QUciksort hat im Worst case nun mal eine quadratische Laufzeit. Was man machen kann, ist den Worst case unwahrscheinlich machen (gute Pivotauswahlstrategie) und, falls man erkennt, dass man eben doch im worst case gelandet ist, das Problem an einen besseren Algorithmus abzugeben. Und da bietet sich zB. Heapsort mit seiner garantierten Laufzeit an.
Eine andere Variante ist zB. mit Quicksort nur grob vorzusortieren und dann mit Insertion sort den Rest zu machen. Stichwort Cutoff. Sedgewick diskutiert das recht ausführlich, oder jeder andere von dir vorgezogene Autor eines guten Algo&DatStruk Buches.

Die einzig wahre Pivotstrategie, die immer n-log-n-Laufzeit zu Tage födert, gibt es nicht (kann man IMHO zeigen) und wenn es sie gäbe, wofür würdet ihr noch Heapsort zB lernen? ;-) Wenn das Pferd tot ist, steig vom Sattel.

Benutzeravatar
Twister11
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 26. Nov 2005 14:18
Kontaktdaten:

Beitrag von Twister11 »

So, habs nun nochmal neu gemacht und jetzt geht er :)
Kein PLAN woran es genau lag.
[php]
public class Quicksort {

/**
* Sorts a List by using quicksort.
* @param unsorted a (potentially) unsorted list of elements
* @return the sorted list with all elements from unsorted
*/
public static <E extends Comparable<E>> List<E> sort(List<E> unsorted) {
quicksort(unsorted, 0, unsorted.size()-1, 0);
return unsorted;
}

private static <E extends Comparable<E>> void quicksort(List<E> list, int left, int right, int pivotPosition) {
if(left >= right) return;
// Initialize
E pivot = list.get(pivotPosition);
int goUp = left;
int goDown = right;
E swap;
int nextPivot;

while(goUp <= goDown) {
// "goUp" moves up the list until an element bigger than pivot is found.
while(list.get(goUp).compareTo(pivot) < 0) goUp++;
// "goDown" moves down the list until an element smaller or equal to pivot is found.
while(list.get(goDown).compareTo(pivot) > 0) goDown--;

if(goUp<=goDown){
// Swap the found elements.
swap = list.get(goUp);
list.set(goUp, list.get(goDown));
list.set(goDown, swap);
goUp++;
goDown--;
}
}

if(left < (goDown)) { // left side
nextPivot = left+((int)Math.random())%(goDown-left);
quicksort(list, left, goDown, nextPivot);
}
if(goUp < right) { // right side
nextPivot = goUp+((int)Math.random())%(right-goUp);
quicksort(list, goUp, right, nextPivot);
}
}
}
[/php]

Benutzeravatar
Twister11
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 26. Nov 2005 14:18
Kontaktdaten:

Beitrag von Twister11 »

Lernen wir im laufe des Studium irgendwann mal HASKELL? :)
Hab naemlich unter anderem nen Quicksort in HASKELL gefunden :)

quicksort [] = []
quicksort (x:xs) = quicksort (filter (< x) xs) && [x] && quicksort (filter (>= x) xs)

Und ohne dieses "filter" zu benutzen ist es auch nur:

quicksort [] = []
quicksort (x:xs) = quicksort [ i | i <- xs, i < x ] && [x] && quicksort [ i | i <- xs, i >= x ]

Das ist so krank :) ...ach uebrigens aehnlich billig muesste es doch auch mit SCHEME gehen, wobei da die Klammerungen ein wenig GAY waere :)

Tillmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 5. Dez 2003 21:27
Wohnort: Frankfurt

Beitrag von Tillmann »

Twister11 hat geschrieben:Lernen wir im laufe des Studium irgendwann mal HASKELL? :)
Ich kann es nur empfehlen, denn
  • Haskell ist sehr expressiv: man kann mit wenig Code viel ausdrücken
  • Haskell ist sehr modern: An Haskell wird aktiv geforscht, viele neue Ideen sickern aus der Welt Haskell-Welt (und der Welt der funktionalen Sprachen allgemein) erst langsam in die objektorientierte Welt durch.
  • Die Haskell-Community ist einfach genial, auch blöde Fragen werden schnell, freundlich und hilfreich beantwortet, in Mailinglisten und Chats bekommt man leicht Kontakt auch zu den führenden Leuten in der Szene.
Hier an der TU habe ich Haskell bisher nur am Fachgebiet Softwaretechnik / Aspekt-orientierte Programmierung erlebt, in den Veranstaltungen "Konzepte der Programmiersprachen" und "Programmanalyse und -transformation". Besonders "Konzepte der Programmiersprachen" kann ich jedem empfehlen, der sich für Programmiersprachen interessiert, da wird ein wirklich fundierte Grundlage gelegt.

Code: Alles auswählen

quicksort [] = []
quicksort (x:xs) = quicksort (filter (< x) xs) && [x] && quicksort (filter (>= x) xs)
Das funktioniert aber so nicht, statt der && muß es ++ heißen, damit dieser Code kompilierbar ist.
Twister11 hat geschrieben:...ach uebrigens aehnlich billig muesste es doch auch mit SCHEME gehen
Folgender Code funktioniert mit DrScheme (Sprache "Standard (R5RS)") und entspricht recht genau dem oben angegebenen Haskell-Programm. Die Funktionen curry, fold und filter gehören natürlich in eine allgemeine Bibliothek. Und sind darin auch bestimmt zu finden, aber ich verstehe zu wenig von Scheme, um Bibliotheken zu nutzen.

Code: Alles auswählen

(define (curry f x)
  (lambda (y) (f x y)))

(define (fold f y xs)
  (if (null? xs) y (f (car xs) (fold f y (cdr xs)))))

(define (filter p xs)
  (fold (lambda (x ys) (if (p x) (cons x ys) ys)) () xs))

(define (quicksort x)
  (cond ((null? x) ())
        (#t (append (quicksort (filter (curry > (car x)) (cdr x)))
                   (list (car x))
                   (quicksort (filter (curry <= (car x)) (cdr x)))))))
Wie zu erwarten war, läßt sich dieselbe Idee auch in Scheme problemlos umsetzen, er Code ist aber doch um einige Zeilen und viele Klammern länger. Zum fairen Vergleich noch die Definition von filter in Haskell, die allerdings auch automatisch zur Verfügung steht, ohne das man irgendwelche Bibliotheken explizit einbinden muß:

Code: Alles auswählen

filter p xs = [x | p x, x <- ys]
Wer sich näher für Haskell interessiert:

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag von banshee »

Tillmann hat geschrieben:
  • Haskell ist sehr expressiv: man kann mit wenig Code viel ausdrücken
ist jetzt halt die frage ob das ein vorteil sein soll :P

hcdenton
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 21. Dez 2006 17:15

Beitrag von hcdenton »

Ich hoffe, sed kommt auch nochmal in irgendeiner Vorlesung dran... ;)
Bild

Benutzeravatar
Wang Tang
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 5. Dez 2006 17:57

Beitrag von Wang Tang »

also in LA 1 & 2 bei uns Mathematikern hat Bokowski schon öfter mal Haskell benutzt um uns was zu zeigen.. nur gerafft hats keiner :D

qveXx
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 2. Dez 2005 19:02

Beitrag von qveXx »

Habe den aus dem Härder auch 1:1 in Java übernommen, mit Ausnahme der Wahl des Pivot-Elements, da habe ich der Einfachheit halber das größere der ersten beiden Elemente genommen und musste feststellen das es bei speziellen Fällen zu einer Endlosschleife gekommen ist. Z.B. wenn das kleinste Element ganz links ist, dann ist qwik(left, i-1) zwar abgebrochen, aber qwik(i, right) hat wieder die selben Grenzen aufgerufen und es wurde wieder das selbe Pivot Element genommen. Um den Fehler unter Java zu beseitigen habe ich am Ende noch eine Abfrage reingebaut, ob i == links für den zweiten Fall, falls das true war, dann habe ich qwik(i+1, right) aufgerufen.
Bin mir jetzt nicht ganz sicher wie es diesbezgl beim Härder und C++ aussieht, aber könnte sein, dass der Fehler da auch auftritt.

Benutzeravatar
Twister11
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 26. Nov 2005 14:18
Kontaktdaten:

Beitrag von Twister11 »

@Tillmann, ich weiss das da ++ stehen muss, aber aus irgendeinem Grund akzeptiert der Editor hier im Forum keine + Zeichen und wandelt sie in ein "Space" um.
Deshalb hab ich && geschrieben :)

@Tillmann, wow :) ich muss unbedingt Vorlesungen zu dem Thema besuchen. Das interessiert mich doch sehr.
Jemand mal was von CLEAN gehoert? Angeblich von Haskell abgeleitet.

Auch ERLANG hoert sich interessant an, aber da es nur dynamische Typisierung unterstuetzt fand ich das auf den ersten Blick nicht so gut. Grade eine funktionale Sprache die so ausdrucksstark ist und angeblich starke Typisierung ...so hiess das doch glaube ich :) ...unterstuetzt hoert sich echt interessant an.

Fragt sich nur wie einfach oder schwierig es ist in Projekten Haskell und Java oder Haskell und XY einzusetzen... waere schon schade, das die starke Verbreitung von bestimmten Sprachen nach dem Studium dann wohl krasse Einschraenkungen erzwingt was vorlieben fuer Programmiersprachen angeht :)

Gibt es irgendwo nachzulesen welche Sprachen Google offiziell verwendet?
Hab irgendwo mal gelesen das Haskell nicht dazu gehoeren wuerde. Aber dann muss es ja irgendwo nachzulesen sein :P

Tillmann
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 131
Registriert: 5. Dez 2003 21:27
Wohnort: Frankfurt

Beitrag von Tillmann »

Twister11 hat geschrieben:Jemand mal was von CLEAN gehoert? Angeblich von Haskell abgeleitet.
Clean wurde 1987 auf derselben Konferenz vorgestellt, auf der beschlossen wurde, mit dem Design von Haskell zu beginnen.
Twister11 hat geschrieben:Fragt sich nur wie einfach oder schwierig es ist in Projekten Haskell und Java oder Haskell und XY einzusetzen... waere schon schade, das die starke Verbreitung von bestimmten Sprachen nach dem Studium dann wohl krasse Einschraenkungen erzwingt was vorlieben fuer Programmiersprachen angeht :)
Naja, als Informatiker kommen wir ja vielleicht eines Tages in die Situation, über die Sprachen (mit-) zu entscheiden, die in einem Projekt verwendet werden. In jedem Fall lohnt es sich, im Studium möglichst viele verschiedene Sprachen zu lernen, um eine umfangreiche Palette von Werkzeugen zur Verfügung zu haben, wenn es dann später im Beruf ans Lösen von Realworld-Problemen geht.

Antworten

Zurück zu „Archiv“