Re: Quicker then QuickSort???

From: Kristofer Gafvert (kgafvert_at_NEWSilopia.com)
Date: 05/10/04 

Date: Mon, 10 May 2004 20:11:34 +0200

Hello,

Have you tried your algorithm with all kind of different data input? Without
pseudo code, i cannot tell you the O(n) for this algorithm (because i am
lazy today), but that is not the main point of my message. The point with my
message is that all algorithms have advantages, and disadvantages, and you
should consider how the data used to sort look like, if you have any upper
bound limit, and then select the best algorithm for that. With "correct"
formed input data, you can get the fastest algorithm to run slower than the
one that should run slowest.

Bruno R. Preiss has a really good website about algorithms and data
structures here:

http://www.brpreiss.com/books/opus6/

(click web book)

He has a complete chapter about Sorting Algorithms that you might find
useful. 

-- 
Regards,
Kristofer Gafvert - IIS MVP
http://www.ilopia.com - When you need help!
"madler" <anonymous@discussions.microsoft.com> wrote in message
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?
>
> Here is the method:
>
> int lval,lpos;
> int hval,hpos;
> lpos = 0;
> hpos = 0;
> lval = 1000000;
> hval = 0;
> for (int i = 0 ;i<(numElems /2);i++)
> {
>
> flag = false;
> int j;
> lval = hval;
> hval = 0;
> for (j = i;j<((numElems -i)-1);j++)
> {
> int c = Elements[j];
> if (c < lval)
> {
> lpos = j;
> lval = c;
>
> }
> if (c > hval)
> {
> hpos = j;
> hval = c;
>
> }
> }
>
> SwapEm(i,lpos);
> SwapEm(j,hpos);
>
> }
>
>
> Thanks

Relevant Pages

  • Re: C++ more efficient than C?
    ... If you want to do language comparisons, ... complicated algorithm, though). ... int compare ... not been in C's standard library. ...
    (comp.lang.c)
  • Re: Mersenne Twister -- A Revised C++ Implementation
    ... "That algorithm is a slight elaboration on the basic linear congruential ... takes an int, and an int on the target you seem to be developing on -- ... unless you qualify it by stressing that you ... compilation to pick the appropriate type in a more general manner. ...
    (comp.lang.cpp)
  • Re: Non-restoring binary square root and convergence
    ... I took the algorithm from "Algorithms for Extracting Square Roots and Cube ... % sqrt 9 16 ... int main ...
    (comp.programming)
  • Re: Non-restoring binary square root and convergence
    ... I took the algorithm from "Algorithms for Extracting Square Roots and Cube ... % sqrt 9 16 ... int main ...
    (sci.math)
  • Re: dijkstra algorithm issue
    ... I am just trying to implement Dijkstra's algorithm but i am not sure ... int n_vertices; ... draw a graph on paper,consider its adjacency matrix ... then compute by hand the shortest path you want on paper, ...
    (comp.programming)