Nonrekursiver Quicksort

[p. specht]

Zeit für ein wenig Nostalgie

WindowTitle "NONREKURSIVES QUICKSORT"
' Getestet, aber ohne Gewähr - P. Specht für Paules PC Forum
Declare NumMax&,A&[],Stack1&[],Stack2&[],StackPtr&,HeadPtr&,TailPtr&
declare Pivot&,a&,b&,t&,q&,r&,p&,s&
declare i&,ms1&,sec!

Jump0:
Cls

Print "Wieviele Random Numbers?:"; : Input NumMax&
Randomize:i&=0:While i&<NumMax&:A&[i&]=Rnd(100000)
    Locate 2,2:print i&,A&[i&]  ''''
Inc i&:EndWhile

ms1& = &GetTickCount  ''''

StackPtr&=0
HeadPtr&=0
TailPtr&=NumMax&-1

Print "Starte Nonrekursives Quicksort...";  ''''

Jump2:

While HeadPtr& < TailPtr&
	Pivot& = A&[(HeadPtr& + TailPtr&)/2]
	a& = HeadPtr&
	b& = TailPtr&
	
Jump1:
  
	While A&[a&] < Pivot& : inc a& : EndWhile
	While A&[b&] > Pivot& : dec b& : EndWhile

  If a& < b& 
		t&=A&[a&]
		A&[a&]=A&[b&]
		A&[b&]=t&
		inc a&
		dec b&
    Goto "Jump1"
	EndIf
	
	If a&=b&
		q& = b& - 1
		r& = a& + 1
	Else
		q& = b&
		r& = a&		
	EndIf
	
	inc StackPtr&
	p& = HeadPtr&
	s& = TailPtr&
	
	If (q&-p&) < (s&-r&)
		Stack1&[StackPtr&] = r&
		Stack2&[StackPtr&] = s&
		HeadPtr& = p&
		TailPtr& = q&		
	Else
		Stack1&[StackPtr&] = p&
		Stack2&[StackPtr&] = q&
		HeadPtr& = r&
		TailPtr& = s&
	EndIf
	
EndWhile

If StackPtr& > 0
	HeadPtr& = Stack1&[StackPtr&]
	TailPtr& = Stack2&[StackPtr&]
	dec StackPtr&
	Goto "Jump2"
EndIf


' Sortierung fertig
sec!=(&GetTickCount - ms1&)/1000

print:Print "Kontrollausgabe (jedes " + str$(int(NumMax&/30+1))+". Element):"  ''''
WhileLoop 0,NumMax&-1,int(1+NumMax&/30):Print A&[&Loop];:EndWhile : print      ''''

print : print "Dauer des reinen Sortiervorgangs der "+str$(NumMax&)+" Zufallsvariablen: "+str$(sec!)+" Sek."
print : print "Weiterer Test mit beliebiger Taste..."
WaitInput
Goto "Jump0"

Für das Sortieren von 500.000 8-Byte-Zufallsintegers in XProfan11.2a brauchte mein 2.5 GHz Rechner (Profan rechnet dabei nur auf einem Kern) mit diesem Algorithmus 186,61 bzw. 185,41 Sekunden. Nostalgie halt... Für solche Arraygrößen bitte die Zeile mit Locate 2,2 auskommentieren, sonst kann man sich während der Zufallsgenerierung einen Kaffee machen gehen.

Gruss

P.S.: ... und Alles Gute den Vätern!