OpenEuphoria

RE: Challenge for Sort programs.

• Posted by Don Phillips <Graebel at hotmail.com> Jun 04, 2002
• 536 views

>Looks nice but it won't sort sequences.
>Hook it up to a test harness & see what it does.
>
>Karl Bochert

I dont have a good way to test it.  I could (I guess) peek into the high 
performance clock on my chip, but I dont really have any need for a quick 
sort of any kind.  Was just throwing it out there to see how it did and 
maybe help someone out.

Heres a slightly modified version that should sort anything.

function QuickSort( sequence Data )
	sequence Left
	sequence Right
	object Pivot
	object NextVal

	-- initialize
	Left = {}
	Right = {}
	Pivot = Data[ 1 ]

	-- partition both halves
	for ListIter = 2 to length(Data) do
		NextVal = Data[ ListIter ]
		if compare(NextVal,Pivot) < 0 then
			Left = append( Left, NextVal )
		else
			Right = append( Right, NextVal )
		end if
	end for

	-- sort partions
	if length(Left) > 1 then Left = QuickSort(Left) end if
	if length(Right) > 1 then Right = QuickSort(Right) end if

	-- join back
	return( Left & {Pivot} & Right )
end function

>I think it's dangerous to choose the 1st element as the pivot
>because of the possibility of pre-sorted data.
>

Its always a possibility that pre sorted data could come in, but dangerous 
no.  Wont hurt the algo any.  Only thing is with QuickSort is that 
pre-sorted data is actually its worse case speed wise.  If you use this and 
the data *might* be pre-sorted, you might look into randomizing it first.  
Little more overhead, but no worse case anymore...

_________________________________________________________________
Chat with friends online, try MSN Messenger: http://messenger.msn.com