Re: sort algorithm

Limbo said:

i have an array of size 100000000 (100M) that was randomaly
initialized with numbers (0-100)
now, i wrote a function that sort this array in 1500 ms.
its sorts an array of 10M in 140 ms, an array of 1M in 16 ms.
my question is, is this function performance ok?

My results are:

100,000,000 entries: 650ms
10,000,000 entries: 63ms
1,000,000 entries: 5ms

(AMD Athlon 1.4GHz). Compare and contrast, depending on your processor. If
you're doing this on a 286 with seventeen bytes of RAM, your results rock
and you should publish or patent. If you're doing it on a Cray, though, go
back to school. :-)

what is the Big O of this function.

Mine is O(n). Yours looks O(n)-ish, too.

is there a better function to do the same?

I used bucket-sort. For this application, I heartily recommend it.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
.

Relevant Pages

  • Re: Sorting objects in ooRex? is this possible with data structures?
    ... Currently the only sort available in ooRexx is SysStemSort and it ... In ooRexx 3.2 there are several new sort methods coming. ... the quickSort the sequence of array entries with the same key value may change (the result is still ... The sort methods are defined for the Array class. ...
    (comp.lang.rexx)
  • Re: Sort pseudo-lists
    ... pete boardman wrote: ... > sort the array of arrays by their second, third, and fourth entries ...
    (comp.lang.ruby)
  • Re: sort algorithm
    ... i wrote a function that sort this array in 1500 ms. ... is this function performance ok? ... The best sorting algorithm for that specific case is counting sort, ...
    (comp.programming)
  • Sort Array
    ... I have an array of three columns and a variable number of entries. ... Is there some way in VBA to sort this array according to the length of the ...
    (microsoft.public.word.vba.beginners)
  • Sort Array
    ... I have an array of three columns and a variable number of entries. ... Is there some way in VBA to sort this array according to the length of the ...
    (microsoft.public.word.vba.beginners)