[DSAL] Sortieren der Punkte beim Graham-Scan-Algorithmus

[Progra] Programmierung
[DSAL] Datenstrukturen und Algorithmen
[SWT] Softwaretechnik
[DB] Datenbanken und Informationssysteme

Sortieren der Punkte beim Graham-Scan-Algorithmus

Beitragvon paco89 » 27.08.12 16:40

hallo,

ich habe eine frage zum Graham-Scan algor. und zwar muss man ja bevor man mit dem Alg. beginnt, die Punkte ersteinmal sortieren. also die reihenfolge der punkte bestimmen, um mit dem Graham-Scan Algorithmus zu starten.
das ist klar. wie man die determinanten bestimmt, ist auch klar. ich versuche das grad anhand der musterlösung zu den Hausaufgaben von diesem Jahr zu verstehen und da steht dass Mergesort angewandt wurde. ich weiß zwar, wie Mergesort geht, aber bezogen auf diese aufgabe kann ich mir das nicht so genau erklären.


kann mir jmd. vtl. weiterhelfen.....?


edit: der graham-scan alg. is an sich klar....nur das sortieren vor dem start bereitet mir probleme....
paco89
 
Beiträge: 115
Registriert: 05.12.10 05:04

Re: Sortieren der Punkte beim Graham-Scan-Algorithmus

Beitragvon cracki » 29.08.12 18:28

also du willst nach irgendeinem winkel sortieren... in python: sorted(points, key=(lambda (x,y): math.atan2(y,x))) wenn points eine liste von (x,y) tupeln ist, und der winkel im ursprung zur x-achse gemeint ist. relativ zu einem anderen punkt P sei eine uebung fuer den leser.

wie du die liste der punkte parallel zur liste der winkel sortierst, in einer sprache die nicht so komfortabel wie python ist, ueberlegs dir mal ;) in C gibt es sort(), welches eine vergleichsfunktion nimmt. da passiert die magie.
"I suppose if what you said had any merit it would occasion hostility." -- Kenny Tilton
Frische Vorlesungen! -- video.rwth-aachen.de
Benutzeravatar
cracki
 
Beiträge: 537
Registriert: 22.02.08 14:51
Wohnort: Aachen
Studiengang: Informatik (M.Sc.)
Studiert seit: ?
Anwendungsfach: Medizin


Zurück zu Praktische Informatik