QuickSort - Versionsgeschichte

84.190.85.60 am 23. September 2008 um 01:16 Uhr

2008-09-23T01:16:48Z

← Nächstältere Version		Version vom 23. September 2008, 01:16 Uhr
Zeile 3:		Zeile 3:

	===Laufzeit===		===Laufzeit===
	best-case : log n~~<br/>~~		best-case : log n
	average-case : log n~~<br/>~~		average-case : log n
	worst-case : n² bzw. log n (Random-QuickSort) ~~<br/>~~		worst-case : n² bzw. log n (Random-QuickSort)
	stabil : nein		stabil : nein

84.190.105.86 am 21. September 2008 um 18:32 Uhr

2008-09-21T18:32:44Z

← Nächstältere Version		Version vom 21. September 2008, 18:32 Uhr
Zeile 27:		Zeile 27:
	<b>return</b> i+1		<b>return</b> i+1

	[[Kategorie:~~Aussagenlogik~~]]		[[Kategorie:Algorithmentheorie]]

84.190.105.86 am 21. September 2008 um 17:42 Uhr

2008-09-21T17:42:53Z

← Nächstältere Version		Version vom 21. September 2008, 17:42 Uhr
Zeile 11:		Zeile 11:

	====QuickSort(H,l,r)====		====QuickSort(H,l,r)====
	if l < r then m:= Partition( H,l,r )		<b>if</b> l < r <b>then</b> m:= <b>Partition(</b> H,l,r <b>)</b>
	QuickSort( H , l , m-1 )		<b>QuickSort(</b> H , l , m-1 <b>)</b>
	QuickSort( H , m-1 , r )		<b>QuickSort(</b> H , m-1 , r <b>)</b>


	====Partition( H,l,r )====		====Partition( H,l,r )====
	i = l - 1		i = l - 1
	for j := 1 to r-1 do		<b>for</b> j := 1 <b>to</b> r-1 <b>do</b>
	if H[j] <= H[r] then		<b>if</b> H[j] <= H[r] <b>then</b>
	i = i + 1		i = i + 1
	if i < j then		<b>if</b> i < j <b>then</b>
	change( H[i] , H[j] )		<b>change(</b> H[i] , H[j] <b>)</b>
	if i+1 < r then		<b>if</b> i+1 < r <b>then</b>
	change( H[i+1] , H[r] )		<b>change(</b> H[i+1] , H[r] <b>)</b>
	return i+1		<b>return</b> i+1

	[[Kategorie:Aussagenlogik]]		[[Kategorie:Aussagenlogik]]

84.190.105.86 am 21. September 2008 um 17:34 Uhr

2008-09-21T17:34:49Z

← Nächstältere Version		Version vom 21. September 2008, 17:34 Uhr
Zeile 1:		Zeile 1:
			QuickSort geht nach dem Prinzip "teile und hersche" (engl. "Divide and Conquer") vor. In jedem Schritt wird ein Pivotelement gewählt und die kleineren Elemente auf die eine Seite bzw alle größeren Elemente auf die andere Seite verschoben. Das Pivotelement befindet sich nun schon einmal an der richtigen Stelle. Jetzt wird dieses Vorgehen rekursiv oder iterativ für beide Seiten solange wiederholt, bis es nur noch ein-elementige Listen sind und nun werden alle Elemente die sich nun schon an den richtigen Stellen befinden zu einer sortierten Liste wieder zusammengefügt.
			QuickSort ist nicht stabil, was bedeutet, daß die relative Reihenfolge der zu sortierenden Elemente nicht eingehalten wird.

	===Laufzeit===		===Laufzeit===
	best-case : log n<br/>		best-case : log n<br/>
	average-case : log n<br/>		average-case : log n<br/>
	worst-case : n² <br/>		worst-case : n² bzw. log n (Random-QuickSort) <br/>
	stabil : nein		stabil : nein

84.190.105.86 am 21. September 2008 um 16:51 Uhr

2008-09-21T16:51:03Z

← Nächstältere Version		Version vom 21. September 2008, 16:51 Uhr
Zeile 1:		Zeile 1:
			===Laufzeit===
			best-case : log n<br/>
			average-case : log n<br/>
			worst-case : n² <br/>
			stabil : nein

	===Psydocode:===		===Psydocode:===

84.190.105.86: Die Seite wurde neu angelegt: ===Psydocode:=== ====QuickSort(H,l,r)==== if l < r then m:= Partition( H,l,r ) QuickSort( H , l , m-1 ) QuickSort( H , m-1 , r ) ====Partition( H,l,r )==== ...

2008-09-21T16:45:10Z

Die Seite wurde neu angelegt: ===Psydocode:=== ====QuickSort(H,l,r)==== if l < r then m:= Partition( H,l,r ) QuickSort( H , l , m-1 ) QuickSort( H , m-1 , r ) ====Partition( H,l,r )==== ...

Neue Seite

===Psydocode:===

====QuickSort(H,l,r)====
if l < r then m:= Partition( H,l,r )
QuickSort( H , l , m-1 )
QuickSort( H , m-1 , r )

====Partition( H,l,r )====
i = l - 1
for j := 1 to r-1 do
if H[j] <= H[r] then
i = i + 1
if i < j then
change( H[i] , H[j] )
if i+1 < r then
change( H[i+1] , H[r] )
return i+1

[[Kategorie:Aussagenlogik]]