Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #31647 > unrolled thread

best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements

Back to article view | Back to comp.lang.java.programmer

Contents

  best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements Ajay Paul <ajaykpaul@gmail.com> - 2015-05-04 10:39 -0700
    Re: best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements Marcel Mueller <news.5.maazl@spamgourmet.org> - 2015-05-04 19:54 +0200
      Re: best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-05-09 07:58 -0400
    Re: best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-05-04 14:16 -0400
      Re: best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-05-04 14:27 -0400
    Re: best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements Martin Gregorie <martin@address-in-sig.invalid> - 2015-05-08 20:42 +0000
    Re: best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements v_borchert@despammed.com (Volker Borchert) - 2015-05-11 02:32 +0000
    Re: best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements Gene Wirchenko <genew@telus.net> - 2015-05-11 14:00 -0700
      Re: best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-05-11 17:27 -0400
      Re: best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements Arne Vajhøj <arne@vajhoej.dk> - 2015-06-03 21:53 -0400

#31647 — best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements

what are the best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements.

I understand that bubble short is worst.

[toc] | [next] | [standalone]

#31648

On 04.05.15 19.39, Ajay Paul wrote:
> what are the best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements.

If you have no further information about the data to sort and you have 
random access merge sort and its derivatives are probably best for 
general purpose. Everything else depends.


Marcel

[toc] | [prev] | [next] | [standalone]

#31658

On 5/8/2015 5:42 PM, Stefan Ram wrote:
> Marcel Mueller <news.5.maazl@spamgourmet.org> writes:
>> If you have no further information about the data to sort and you have
>> random access merge sort and its derivatives are probably best for
>> general purpose. Everything else depends.
>
>    If one has a huge array, it is well possible that the largest
>    possible gain comes from sorting an array of primitves (int)
>    versus an array of references (Integer).

     Note the many overloads of Arrays#sort() already provide for this:
There are versions not only for Objects, but for arrays of almost all
primitive types.  (Sorting an array of the remaining type is left as
an exercise for the reader; try for a linear-time implementation...)

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

[toc] | [prev] | [next] | [standalone]

#31649

On 5/4/2015 1:39 PM, Ajay Paul wrote:
> what are the best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements.

     See Marcel Muller's response.  As a practical matter, use
java.util.Collections#sort or java.util.Arrays#sort and apply
your ingenuity to the other problems your program needs to solve.
Later on, if you measure the performance, find it inadequate,
discover that sorting is a significant time-waster, *and* think
you can do better -- if all those, then and only then implement
your own sort.

> I understand that bubble short is worst.

     Not even close.  One well-known far worse sort is

	https://en.wikipedia.org/wiki/Bogosort

... and of course any implementation of any algorithm can always
be disimproved.  (One effective way is to post the bad code to
Usenet and solicit improvements ;)

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

[toc] | [prev] | [next] | [standalone]

#31650

On 5/4/2015 2:16 PM, Eric Sosman wrote:
> On 5/4/2015 1:39 PM, Ajay Paul wrote:
>> what are the best and worst sorting algorithm for 1 to 10,000 and then
>> 10,000 + elements.
>
>      See Marcel Muller's response. [...]

     Sorry: Marcel Mueller's response.  Ich schäme mich.

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

[toc] | [prev] | [next] | [standalone]

#31654

On Mon, 04 May 2015 10:39:26 -0700, Ajay Paul wrote:

> what are the best and worst sorting algorithm for 1 to 10,000 and then
> 10,000 + elements.
> 
> I understand that bubble short is worst.

The relative cost of the key comparison and element swap steps is 
important. Some will tell you that quicksort is significantly faster than 
shell-sort without qualifying that statement but that it only true if key 
comparison has a lower cost than swapping elements: if key comparison is 
expensive, i.e. there are multiple keys in each item and each key 
comparison is expensive (such as caseless comparisons) then quicksort 
becomes the slower algorithm because it minimises element swaps on the 
assumption that key comparison is always cheaper than swapping items.

Bottom line: as others have said, use the standard Collection sorts 
unless properly instrumented tests show their (lack of) performance is 
causing problems.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [next] | [standalone]

#31670

Ajay Paul wrote:
> what are the best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements.
> 
> I understand that bubble short is worst.

Sounds like homework...

-- 

"I'm a doctor, not a mechanic." Dr Leonard McCoy <mccoy@ncc1701.starfleet.fed>
"I'm a mechanic, not a doctor." Volker Borchert  <v_borchert@despammed.com>

[toc] | [prev] | [next] | [standalone]

#31672

On Mon, 4 May 2015 10:39:26 -0700 (PDT), Ajay Paul
<ajaykpaul@gmail.com> wrote:

>what are the best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements.
>
>I understand that bubble short is worst.

     You need to hit the books.

     For example, bubble sort can do very well with nearly-sorted
data, and quick sort does not.

Sincerely,

Gene Wirchenko

[toc] | [prev] | [next] | [standalone]

#31673

On 5/11/2015 5:00 PM, Gene Wirchenko wrote:
> On Mon, 4 May 2015 10:39:26 -0700 (PDT), Ajay Paul
> <ajaykpaul@gmail.com> wrote:
>
>> what are the best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements.
>>
>> I understand that bubble short is worst.
>
>       You need to hit the books.
>
>       For example, bubble sort can do very well with nearly-sorted
> data, and quick sort does not.

     Voyaging off to far Anectodistan: The worst sort I ever personally
encountered in an actual, for-sale, commercial program written by
professional programmers ran in O(N*N*logN) time.  The sort itself made
only O(N*logN) comparisons, but the comparator in this instance did a
linear search through an auxiliary list of size ~=N, taking O(N) time
for each comparison.

     The irony was that the purpose of the O(N*N*logN) sort was to speed
up a subsequent operation that would otherwise have taken O(N*N) time.

     Any more True Crime stories out there?

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

[toc] | [prev] | [next] | [standalone]

#31766

[sorry if duplicate post]

On 5/11/2015 5:00 PM, Gene Wirchenko wrote:
 > On Mon, 4 May 2015 10:39:26 -0700 (PDT), Ajay Paul
 > <ajaykpaul@gmail.com> wrote:
 >
 >> what are the best and worst sorting algorithm for 1 to 10,000 and 
then 10,000 + elements.
 >>
 >> I understand that bubble short is worst.
 >
 >       You need to hit the books.
 >
 >       For example, bubble sort can do very well with nearly-sorted
 > data, and quick sort does not.

That depends on how the pivot element is picked.

Pivot=first or pivot=last works very bad with already or near sorted.

But pivot=middle works great with already or near sorted.

Obviously there are just as many bad orders for pivot=middle but they
are a lot less likely than already or near sorted.

Arne

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web