1. RE: Challenge for Sort programs.
rforno at tutopia.com wrote:
> Hi all:
> I was attempting to improve the performance of the Shell sort that comes
> with Euphoria. One of the ways is substituting the divisor 3 by some
> other,
> especially for non-integers in the range 2.5 - 3.5. 2.6, 2.7 and 3.4
> have
> proven to be good.. Some other tactics have been tried, with no great
> success.
> As you know, Shell sort is based on Insertion sort, one of the simple
> ones,
> with times O(n ^ 2), instead of O(n log(n)) as the efficient ones.
> Then I started seeking to improve the simple sorts or develop new simple
> sorting methods, with the aim to apply then to Shell sort replacing
> Insertion sort in it. My attempts failed with modified versions of
> Insertion
> sort, but I succeed in programming double_sel_sort (a modification of
> normal
> Selection sort working from both ends) and new_sort, a novel approach
> (also
> a modification of Selection sort) which takes advantage of the
> previous-to-best key to reduce the search range. These sorts are
> marginally
> faster than Insertion sort if the number of items is not too low.
> But they should not be used to replace Insertion sort inside Shell sort,
> because they are slower than it when the sequence is nearly sorted.
> Shell
> sort takes advantage of this fact especially in its last pass, identical
> to
> Insertion sort, precisely because the sequence is then nearly sorted.
> So, I tried Bubble sort, that is the fastest one for nearly sorted
> sequences, and the generated a new_shell_sort based on Bubble sort. It
> is
> not faster, but rather slower than the original Shell sort.
> Well, after this rant, you will find the code for all these sorts, plus
> two
> slightly improved versions of Bubble sort, and Selection sort, one of
> the
> basic ones (Rob: why is it not included in Allsorts.ex?).
> The challenge to find faster sorts remain open. I hope to have
> contributed
> some ideas on this subject.
<SNIP>
Actually I have a question. Are you simply trying to improve the speed
of the sort? Or trying to improve the performance of the shell sort
only?
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 = {}
Right = {}
Pivot = Data[ 1 ]
-- partition both halves
for ListIter = 2 to length(Data) do
NextVal = Data[ ListIter ]
if NextVal < Pivot then
Left &= NextVal
else
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 have not tested this for speed but it should be very compariable to
just about anything else out there...
2. RE: Challenge for Sort programs.
-------Phoenix-Boundary-07081998-
You wrote on 6/3/02 3:47:47 PM:
>
>Hi all:
>I was attempting to improve the performance of the Shell sort that comes
>with Euphoria.
<snip>
>Well, after this rant, you will find the code for all these sorts, plus two
>slightly improved versions of Bubble sort, and Selection sort, one of the
>basic ones (Rob: why is it not included in Allsorts.ex=3F).
>The challenge to find faster sorts remain open. I hope to have contributed
>some ideas on this subject.
This got me thinking about sorts and how the fastest of all sorts is the
partition sort, also known as quicksort. I wrote one for Euphoria, and
although
it does out-perform the others, its advantage is not as great as I might
have expected. I just wrote it with no concern for Euphoria optimizations,
so
there might be room for considerable improvement. I have also not tested it
on
a variety of data (of course). I am attaching the code
for the quicksort, a test harness and the code from your message.
Karl Bochert
-------Phoenix-Boundary-07081998-
Content-type: application/octet-stream; Name=rforno.e
3. RE: Challenge for Sort programs.
-------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---
4. RE: Challenge for Sort programs.
-------Phoenix-Boundary-07081998-
Hi Parnell, D (Derek), you wrote on 6/3/02 11:15:31 PM:
>Karl,
>
>I might be wrong but your program seems to fail to sort the data. Can you
>confirm that it works okay=3F
>
Its not enough that I come up with a faster sort, but it should
work too=3F Attached is a version that appears to work. Its a little
slower, but still faster than sort() for large data. I still think
it runs slower than it should. The data that I sort contains lots
of duplicates, and it is possible that my code handles them poorly.
I have added a non-recursive version that is slower than the
recursive version. It should be tested on longer data, sorted data,
reverse sorted data etc.
Karl Bochert
-------Phoenix-Boundary-07081998-
Content-type: application/octet-stream; Name=qsort.e
5. RE: Challenge for Sort programs.
>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
