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

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

Re: Verifying a list is alphabetized

Show all headers | View raw

On Sat, 03 Dec 2011 20:05:24 -0800, Roedy Green wrote:

> On Sat, 03 Dec 2011 07:44:48 -0500, Eric Sosman
> <esosman@ieee-dot-org.invalid> wrote, quoted or indirectly quoted
> someone who said :
> 
>>     What is the big-Oh complexity of Collections.sort(List<String>)
>>on an already-sorted list?
> 
> IIRC QuickSort goes a bit bananas if the file is already sorted.  ISTR
> some sort doing some random swaps at the start to make sure that does
> not happen.  It does do a check first if things are in order.
>
I'm a little wary of quicksort's claim of superior speed in every 
situation.

Some time back (and writing PL/9 on a 6809 - PL/9 is a close relative of 
PL/M) I decided to educate myself by implementing a number of sorts to 
compare code complexity and speed. These were the Bubble, Selection, 
Shell, and Quicksort algorithms. As I was writing in PL/9, I simply threw 
all the records into a chunk of memory and stored pointers to them in an 
array. Swapping records was very fast because the records themselves 
never moved: I just swapped pointers in the array and, when the sort 
finished, wrote out the records by iterating along the pointer array. 

With a single text key the various sorts performed as expected: slowest 
to fastest was the order that I listed earlier.

However, then I got cute and replaced the simple comparison function, 
which I used in all the algorithms, with a more complex one, capable of 
multi-key sorting as well as natural, lexicographic, caseless, and 
numeric ordering for each key. Much to my surprise, I discovered that 
using this comparator, the quicksort was slower than the shell sort, 
giving a performance ordering (slow to fast) of Bubble, Selection, 
Quicksort and Shell.  

Evidently there's an unstated assumption in Quicksort that record swaps 
will always be slower and/or less costly than comparisons, so it was 
optimised to minimise swaps and not to worry about the cost of 
comparisons. This feature was emphasised in my test series by the 
extremely low cost of record swaps. 

It strikes me that Java implementation may also show this behavior, 
especially if the objects to be sorted were stored in an Object array
rather than a more complex structure such as a Collection, and the 
comparator required by this object type is non-trivial.


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

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Verifying a list is alphabetized laredotornado <laredotornado@zipmail.com> - 2011-11-30 07:52 -0800
  Re: Verifying a list is alphabetized Knute Johnson <nospam@knutejohnson.com> - 2011-11-30 08:05 -0800
    Re: Verifying a list is alphabetized Lew <lewbloch@gmail.com> - 2011-11-30 11:18 -0800
    Re: Verifying a list is alphabetized Arne Vajhøj <arne@vajhoej.dk> - 2011-12-02 19:54 -0500
      Re: Verifying a list is alphabetized Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-03 07:44 -0500
        Re: Verifying a list is alphabetized Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-03 09:02 -0500
        Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-03 20:05 -0800
          Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-03 22:13 -0800
            Re: Verifying a list is alphabetized Tom Anderson <twic@urchin.earth.li> - 2011-12-04 21:47 +0000
          Re: Verifying a list is alphabetized Martin Gregorie <martin@address-in-sig.invalid> - 2011-12-04 12:42 +0000
            Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-12-04 12:18 -0800
              Re: Verifying a list is alphabetized Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2011-12-04 13:17 -0800
                Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-12-04 15:32 -0800
                Re: Verifying a list is alphabetized markspace <-@.> - 2011-12-04 15:59 -0800
                Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-12-04 16:14 -0800
                Re: Verifying a list is alphabetized markspace <-@.> - 2011-12-04 17:12 -0800
                Re: Verifying a list is alphabetized Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-04 21:17 -0500
            Re: Verifying a list is alphabetized Tom Anderson <twic@urchin.earth.li> - 2011-12-04 22:11 +0000
              Re: Verifying a list is alphabetized Martin Gregorie <martin@address-in-sig.invalid> - 2011-12-04 23:41 +0000
              Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-12 01:39 -0800
          Re: Verifying a list is alphabetized Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-04 08:47 -0500
          Re: Verifying a list is alphabetized Gene Wirchenko <genew@ocis.net> - 2011-12-04 21:34 -0800
  Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-11-30 12:52 -0800
    Re: Verifying a list is alphabetized laredotornado <laredotornado@zipmail.com> - 2011-12-01 06:43 -0800
  Re: Verifying a list is alphabetized Joshua Maurice <joshuamaurice@gmail.com> - 2011-11-30 13:16 -0800
  Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-02 01:43 -0800
    Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-12-02 05:58 -0800
      Re: Verifying a list is alphabetized Arne Vajhøj <arne@vajhoej.dk> - 2011-12-02 19:55 -0500
      Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-03 02:54 -0800
        Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-12-03 06:17 -0800
    Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-03 03:10 -0800
  Re: Verifying a list is alphabetized Arne Vajhøj <arne@vajhoej.dk> - 2011-12-02 19:52 -0500

csiph-web