Re: Fastcode poll - Should Sort include worst case situations

Stephen Howe wrote:

> > > Not true. There still exist killer sequences but they are just very
> > > rare.
> >
> > By my experience it is a fact.
>
> 1) Your experience is wrong (and "experience" is not a good arbiter of
> mathematical truth).

Quote: "Problem with all worst cases of Qicksort disapared at least with "midlle element pivot". Meaning, original Hoare's version (based on first or last element pivot) should be forbiden for implementation."

Quite was regarded Hoare's original Quicksort. Fact is that original Hoare's Quicksort worst cases are:

1. Already sorted data
2. Reversely sorted data

Here is not "prove" that any descendant of Quicksort have no "killer sequence" and was not expressed doubt that does'n exist (whatsoever, it easy to create). It was wrote a fact that "middle element" Quicksort version have no problems as original Hoaro's algorithm have (regarding speed and correct of B&V, what was first post in the thread). In these cases, "middle element" version have O(N * Log N). My experience only prove theory. Please read whole thread.

Anyway QuickSort is very simple algorithm and it's complexity is precisely analized (can be found in any "Analysis of Algorithms" based Computer Sience literatury).

Any descendant of Quicksort try to eliminate or moderately decrease some or all of it's weakness (note that "weakness" is not "worst case", to awoid possible misundestanding). That usualy mean dramatically algorithm complexity. Main weakness of Quicksort (as an 'devide and conquer") is that it swaps two elements quite unefficiant depending on choosen pivot and second is recursion and problems with stack.

Etc, further detailed retrospective of many QuickSort implementations as well as other sort algorithm will take too much time and space - wikipedia is starting point and give some interesting links for further analyze who is interested.

Main note here is that there is no sort which suits to all needs, meaning for: data types, ammount of elements and ammount of equal elements as I'm mentioned already. Hybrid sort of several algorithm is only solution to cover all that situations.

And all upper sayed implicitly show main weakness of this competition - based on choosing and implementing hybrid or one of very well known sort algorithms or invent new one (which is very dificult, or better say practically impossible task). All in all, that is the job of Computer Science Department and scientist.

I would like to see TList sort competition (replacemen of TList), not separatelty sort competition - there is much more space to improve sorting behavior inside TList class itself and not much new for sorting routines.

Sasa
--
www.szutils.net
.

Relevant Pages

  • Re: Fastcode poll - Should Sort include worst case situations
    ... median algorithm, not O), there exists sequences that will beat ... quicksort and make it O. ... by many compiler vendors is "Engineering a Sort ... If it detects that a portion of an array is responding badly, ...
    (borland.public.delphi.language.basm)
  • Re: Help me with references
    ... I can't think of any situation in which bubble sort is ... > best choice for a sorting algorithm in a real machine. ... Quicksort is optimized for large Ns. ... I picked Bubblesort because your original post implied something along ...
    (comp.lang.java.help)
  • Re: sorting algorithms
    ... >> Quicksort seems to have close this chapter and now nothing ... >> sorting algorithm was a competition like finding the longuest ... No sort does both on all input set ... You haven't defined what you mean by "efficient use of memory". ...
    (comp.programming)
  • Re: sorting
    ... The algorithm you choose depends a lot on the number of ... sort will be quick enough. ... Quicksort or another method. ... use Bubble sort algorithm which is ...
    (microsoft.public.excel.programming)
  • Re: "Sorting" assignment
    ... algorithm such as tbe bubble sort should be given a free pass because ... I would tailor which algorithm to start with by how the student thinks ... If you only learn the beautiful side of programming, ...
    (comp.programming)