Groups > comp.lang.java.programmer > #31673

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

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!1.eu.feeder.erje.net!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail
From	Eric Sosman <esosman@comcast-dot-net.invalid>
Newsgroups	comp.lang.java.programmer
Subject	Re: best and worst sorting algorithm for 1 to 10,000 and then 10,000 + elements
Date	Mon, 11 May 2015 17:27:28 -0400
Organization	A noiseless patient Spider
Lines	28
Message-ID	<mir6q5$f83$1@dont-email.me> (permalink)
References	<c26476e6-86b7-494b-a2e8-4d9eb7f7bbd7@googlegroups.com> <t162latr1e10ir0vhkr46krlr2mrlnatgr@4ax.com>
Mime-Version	1.0
Content-Type	text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding	7bit
Injection-Date	Mon, 11 May 2015 21:26:30 +0000 (UTC)
Injection-Info	mx02.eternal-september.org; posting-host="858a9d65d95f4ea4d355bd116aa2cdbf"; logging-data="15619"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19B6K0MqHGKZ+7yqo+0yaSb"
User-Agent	Mozilla/5.0 (Windows NT 6.1; WOW64; rv:31.0) Gecko/20100101 Thunderbird/31.6.0
In-Reply-To	<t162latr1e10ir0vhkr46krlr2mrlnatgr@4ax.com>
Cancel-Lock	sha1:aGdRrRknXXmzVsAPjAFuLRxKiDg=
Xref	csiph.com comp.lang.java.programmer:31673

Show key headers only | View raw

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

Thread

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

csiph-web