Hier etwas zu Sortieralgorithmen
lima-city → Forum → Programmiersprachen → Sonstige Programmiersprachen
aufwand
diskussionsgrundlage
element
elemente
erste
fest
folgen
grtes element
gren
kleiner rechts
letztes element
mitte
recht
rckfragen
struktur
teilung
umordnung
verfeinerung
verteilung
-
Sortieren durch Zerlegen
Gegeben sei eine Folge mit n-Elementen. Ein belieb. aber festes Element als Vergleichselement.
Ordne alle Elemente kleiner gleich dem Vergleichselement in eine linke, die anderen in eine rechte Teilfolge
Verfahre mit Teilfolgen genauso, bis jede Teilfolge einelementig ist.
Sortieren durch Zerlegen:
Bsp.: (10/19/88/27/12/1/8/2) Vergleichselement rechts von geom. Mitte
(10/12/1/8/2) (19/88/27)
(1) (10/12/8/2) (19/88/27) (19/27/88)  (19/27) (88)
(27/19)
(8/2) (10/12) (19) (27)
(2) (8) (10/12)
Änderungsmöglichkeiten: Wenn 2 Teilfolgen nach
Teilung identisch, wähle neues VE
Füge das Vergleichselement als letztes Element in die entsprechende Teilfolge.
Ist das VE gleichzeitig letztes und größtes Element, füge es als erstes Element in die neue Teilfolge.
Bezüglich des Vergleichselementes ist auf Gleichverteilung zu achten.
(1/1/2/5/1/4/1/3)  (1/1) (1/2/5/4/3/1)
 (1) (1) (1/2/3/1/4) (5)
(1/2/1/3) (4)
(1) (2/3/1)
(2/1/3)
(1) (2/3)
(3/2)
(2) (3)
Quicksort
Verfeinerungen vor jeder Teilg. zum Sortieren
Vor jedem Teilungsschritt findet eine Umordnung der Elemente statt. Dabei werden gleichzeitig die Zahlen links und rechts vom VE paarweise auf Zahlen untersucht, die größer (links) bzw. kleiner (rechts) bezüglich des VEs sind.
Sortieraufwand: A(n)Quicksort  n*log10 n
 n*lg n
 n* ln n
ln10
n* ln n n* ln n
ln 2 ln 10 Momentan ist QS der schnellste SA
Aufwand abh. Von Verteilung der Elemente
(Struktur d. Folge)
-
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
