OpenEuphoria

RE: Challenge for Sort programs.

• Posted by kbochert at ix.netcom.com Jun 04, 2002
• 417 views

-------Phoenix-Boundary-07081998-

Hi Don Phillips, you wrote on 6/3/02 5:48:03 PM:

>Actually I have a question.  Are you simply trying to improve the speed 
>of the sort=3F  Or trying to improve the performance of the shell sort 
>only=3F
>
>Seems to me the best way to improve its speed is to use a different algo 
>altogether.  Like a quicksort:
>
>function QuickSort( sequence Data )
>	sequence Left
>	sequence Right
>	integer Pivot
>	integer NextVal
>
>	-- initialize
>	Left =3D {}
>	Right =3D {}
>	Pivot =3D Data[ 1 ]
>
>	-- partition both halves
>	for ListIter =3D 2 to length(Data) do
>		NextVal =3D Data[ ListIter ]
>		if NextVal < Pivot then
>			Left &=3D NextVal
>		else
>			Right &=3D NextVal
>		end if
>	end for
>
>	-- sort partions
>	if length(Left) > 1 then Left =3D QuickSort(Left) end if
>	if length(Right) > 1 then Right =3D QuickSort(Right) end if
>
>	-- join back
>	return( Left & Pivot & Right )
>end function
>
>
>I have not tested this for speed but it should be very compariable to 
>just about anything else out there...
>
Looks nice but it won't sort sequences.
I think it's dangerous to choose the 1st element as the pivot
because of the possibility of pre-sorted data.

Hook it up to a test harness & see what it does.

Karl Bochert

-------Phoenix-Boundary-07081998---