Re: Quicker then QuickSort???

From: Mathieu Chavoutier (nospam_at_no.spam)
Date: 05/10/04 

Date: Mon, 10 May 2004 18:08:42 +0200

"madler" <anonymous@discussions.microsoft.com> a écrit dans le message de
news:A205F4F4-C7E5-4927-8B36-FB3A235B29AB@microsoft.com...
> Hi.
>
> I might be a bit niave here but I was looking over a quicksort
implementation (provide by compuware as a sample for DevPartner Profiler
community edition) and I thought that I could do better then that. So I
implemented my own simple sorting algoritim and it seems to run twice as
fast as the quicksort.
>
> So my question is - What is the catch with my algorithim - why do all
libraries include the very complex QuickSort when something as simple as
what I did is not used. I am sure that people have explored the same method
before. Does anyone know what it's shortcomes are?

The fastest sort algorithm is the bubble sort with flag. But, that
performance is only for the case where the list is sort :o)
If you have sorted lists, yes, quick sort is the wrong answer. (that's why
you might have to random your list before sorting with quicksort).

So, why use quicksort ?
It's easy : quicksort is the fastest, but in average. Your sort algorithm is
perhaps faster on some case, but if you try every possible solutions,
quicksort will be faster.

HTH

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: Quicksort
    ... version, unless, of course you can afford order N stack space. ... fully recursive form to the semi recursive form of quicksort by ... If the compiler does tail recursion elimination, ... quicksort, in the average case, is one of the fastest sort algos. ...
    (comp.programming)
  • Re: Quicksort
    ... then we can actually debate about what will actually happen, ... quicksort, in a purely recursive form, likes to overflow if nothing is done; ... quicksort, in the average case, is one of the fastest sort algos. ...
    (comp.programming)
  • Re: Quicksort
    ... >>> quicksort, in the average case, is one of the fastest sort algos. ... of the kind found in qsort. ... > with compiler optimizations, qsort is still about 1.3x faster than> heapsort. ...
    (comp.programming)
  • Re: Quicksort
    ... quicksort, in a purely recursive form, likes to overflow if nothing is ... quicksort, in the average case, is one of the fastest sort algos. ... of about double that of quicksort, and in the case of heapsort, that's ... of the kind found in qsort. ...
    (comp.programming)