Re: Fastcode Sort B&V version 0.8

> > What do you mean?
>
> Concrete here with log distribution, Qucksort will swap element in
> first loop closer to plase where he need to be in finaly sorted
> order. That is main reason. For example (maybe not exact, but just
> to clear):
>
> 1. 100 2 200 3 400 6 800 - pivot is 3
> 2. 2 3 .. 200 100 6 800 - pivot is 100 for right part recursion
> 3. 2 3 .. 6 100 200 800 - end
>
> Recursion calls are on minimum here.
>
> Perhaps, standard random distribution will be much difficult for
> Quicksort. Anyway, can be tested a bit first to be sure.

This has nothing to do with what i was speaking of. It was about the
list length, not the list contents. When testing more list lengths
there will have to be an appropriate list-length distribution.

The list-length distribtion might even be different for the different
list sorting states.

> > > 1. Sorting random data
> > > 2. Sorting (almost) sorted data (adding situation included, as
> > > well) 3. Sorting (almost) reverse sorted data.
> >
> > So in fact these scenarios would match your experiences quite well.
>
> Perhaps to add just a bit less common situation:
>
> 4. Data with many equal elements (range of elements is quite small,
> say 2^8 different elements with size of 1000+).

Yes, a situation with many equal elements might be useful too.

> > In making the benchmark we should just care about realism, not about
> > the algorithms used. Adding pathological cases specific to some
> > algorithms on purpose doesn't make sense for a benchmark.
>
> What is your pioint to test N sorted parts in data anyway?
> By my opinion that is very rare (in practice it is practically
> impossible).
>
> I think I have explain that mentioned created data are pointless.
> Median of three will have not problem with two sorted parts, but in
> generally may be slower than middle element variant.
>
> If you to concat two sorted Tlist, Megesort is much better solution.
> Anyway, why complicate banchmark for that and similar preparation?
>
> Perhaps is better that we concenrate on first three mentioned
> situations, which theory also suggest for testing sort algorithm
> effectiveness.

The benchmark should not take the algorithm used into consideration.
For RTL use there should be one function which performs best on a
series of tests we consider representative for realistic usage.
Pathological cases are not likely a large fraction in this, unless the
alogirthm in question happens to have many realistic pathological cases.

QS pathological cases are a very small fraction of the total list space
BTW. With normal pivot choices (middle element or median-of-three)
these are also very unrealistic cases. Note that first element pivot
implementations do get realistic worst cases (namely the sorted lists).
.

Relevant Pages

  • Re: SBS 2003
    ... "I assume that you want to create a Distribution ... > List in Outlook, so when users can send emails and faxes at the same time ... Create a new Contact public folder under All Public Folders list. ... > distribution lists directly in Fax wizard. ...
    (microsoft.public.windows.server.sbs)
  • Re: P-value from chi-square value: source code
    ... the accuracy being lost by using good algorithms. ... I do not think an algorithm for a chi-squared distribution ... TOMS708 and its code for the cdf of the gamma ... Anyone looking for source code for the gamma distribution should watch ...
    (sci.stat.math)
  • Re: Adding a group to multiple Distribution list
    ... distribution lists. ... Distinguished Name of the group to be added as a member. ... ' Specify Distinguished Name of new member. ...
    (microsoft.public.windows.server.active_directory)
  • Re: Migrate Distribution Lists from 5.5 to 2003
    ... So i'm a little confused do you mean the Distribution Groups do exist in the ... And you can't change them to Distribution lists? ... Microsoft Exchange ... > Exchange 2003 server. ...
    (microsoft.public.exchange.setup)
  • Re: Deczky all-pass filter design Matlab
    ... Like Google is doing? ... Minister of Algorithms ... distribution of cataloged documents may be practical. ...
    (comp.dsp)
Loading