quicksort < Pascal < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:08 Mo 14.02.2005 | | Autor: | Eirene |
hallo!!!
also ich muss in der Schule ein Programm programmieren mit quicksort
als kleine Hilfe hat uns der Lehrer folgende Seite empfohlen : http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm
kann mir bitte jemand helfen das zu programmieren und mir das auch ausführlich erklären, da ich das nicht so gut kann??
Außerdem hab ich im Internet noch ein Quelcode gefunden das ziemlich gut ist, meine ich
Function quicksort(s,e)
i=s
j=e
x=feld((i+j)/2)
Repeat
While feld(i)<x
i=i+1
Wend
While feld(j)>x
j=j-1
Wend
If i<=j Then
tmp=feld(i)
feld(i)=feld(j)
feld(j)=tmp
i=i+1
j=j-1
End If
Until i>j
If j>s Then quicksort(s,j)
If i<e Then quicksort(i,e)
End Function
danke
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:08 Mo 14.02.2005 | | Autor: | Lizard |
Hallo,
> als kleine Hilfe hat uns der Lehrer folgende Seite empfohlen :
> http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm
Gefällt mir als Einführung nicht so gut. Schau dir als "größere" Hilfe vielleicht mal ![[]](/images/popup.gif) http://www.wikiservice.at/dse/wiki.cgi?QuickSort an.
|
|
|
| |
|
Hi Eirene!
Wo genau liegt denn das Problem?
Verstehst du den Algorithmus nicht, oder hapert es am Programmieren?
zu Quicksort:
du hast z.B. eine Folge von Zahlen und willst diese sortieren
nimm dir eine Zahl (=Pivotelement) aus der Folge (die Meisten nehmen die Mitte) und verschiebe alle Zahlen, die rechts von dieser Zahl stehen+kleiner sind als diese nach links und alle Zahlen, die links von der Zahl stehen+größer sind nach rechts. Jetzt steht dein Pivotelement an der richtigen stelle und man muss nur noch die Bereiche rechts und links davon sortieren. Bei diesen Bereichen verfährst du genauso.
mmh, ist schlecht zu erklären, hier ein Beispiel
[mm] \vmat{ 63 & 24 & 12 & 53 & 72 & 18 & 44 & 35 } [/mm] wähle 53 als Pivotelement
[mm] \vmat{ 18 & 24 & 12 & 35 & 44 & 53 & 72 & 63}
[/mm]
sortiere jetzt [mm] \vmat{ 18 & 24 & 12 & 35 & 44 } [/mm] und [mm] \vmat{72 & 63 }
[/mm]
wähle 12 bzw. 72 als Pivotelement, dann:
[mm] \vmat{ 12 & 24 & 18 & 35 & 44 } [/mm] und [mm] \vmat{63 & 72 }
[/mm]
sortiere jetzt [mm] \vmat{ 24 & 18 & 35 & 44 } [/mm] mit 18 als Pivotelement:
[mm] \vmat{ 18 & 24 & 35 & 44 }
[/mm]
fertig
zu deinem Quelltext:
deine Zahlenfolge wird hier durch ein Feld beschrieben
Function quicksort(s,e) (sortiere den Bereich s bis e, am Anfang also 0 bis 7 (im Bsp. oben))
i=s
j=e
x=feld((i+j)/2) (x ist dein Pivotelement)
Repeat
While feld(i)<x (du durchläufst deinen Feldbereich vom linken Rand, bis du ein Element gefunden hast, dass größer als dein Pivotelement ist)
i=i+1
Wend
While feld(j)>x (du durchläufst deinen Feldbereich vom rechten Rand, bis du ein Element gefunden hast, dass kleiner als dein Pivotelement ist)
j=j-1
Wend
If i<=j Then (Jetzt hat das Element feld(i), dass links vom Pivotelement ist, aber größer als dieses ist und das Element feld(j), das rechts vom Pivotelement ist und kleiner ist als dieses: hier werden die beiden Elemente vertauscht)
tmp=feld(i)
feld(i)=feld(j)
feld(j)=tmp
i=i+1
j=j-1
End If
Until i>j
(Jetzt liegt dein Pivotelement an der richtigen Stelle)
If j>s Then quicksort(s,j) (Sortiere nun den Bereich s bis j)
If i<e Then quicksort(i,e) (Sortiere nun den Bereich i bis e)
End Function
Hoffe, ich konnte dir helfen.
mfg Verena
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:46 Mo 14.02.2005 | | Autor: | Eirene |
nun ja wenn ich ehrlich sein soll verstehe ich alles nicht, das Prinzip verstehe ich, aber ich weiß überhaupt nicht wie man es programmiert, und wie z.B die Form dann ausssieht
ich weiß auch überhaupt nicht wie ich anfangen soll...
hmm...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:56 Mo 14.02.2005 | | Autor: | baskolii |
mmh, kannst du vielleicht etwas genauer sagen, was dein Problem ist.
In welcher Programmiersprache soll denn das ganze sein.
mfg Verena
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:43 Mo 14.02.2005 | | Autor: | Eirene |
Also es sollte auf jeden fall in delphi sein.
|
|
|
| |
|
Hallo Eirene!
Die Google-Tipps von Karl dürften dir schon weiterhelfen.
Dabei brauchst du aber bereits Kenntnisse in Delphi generell.
Falls du dazu Fragen hast, stell sie ruhig.
Ich persönlich hab es nämlich mal im Praktikum intensiv gelernt.
Viel Erfolg
Gruß Schneckchen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:52 So 20.02.2005 | | Autor: | difftop |
Du hast die Lösung, die Quicksort-Funktion bereits aufgeschrieben.
(allerdings in einer Basic-Notation)
Sie ist nur noch in die Objekt-Pascal-Syntax (liegt Delphi zugrunde)
zu übertragen.
Die While-Schleife in begin .... end, statt Wend zusammenfassen,
die Verzeigung ebenfalls in begin ... end, statt endif zus.fassen.
|
|
|
|
