Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!weretis.net!feeder4.news.weretis.net!usenet.ukfsn.org!not-for-mail From: Martin Gregorie Newsgroups: comp.lang.java.programmer Subject: Re: Verifying a list is alphabetized Date: Sun, 4 Dec 2011 12:42:38 +0000 (UTC) Organization: UK Free Software Network Lines: 52 Message-ID: References: <722147ec-ab43-4d7c-8b41-32f8705ee7db@i8g2000vbh.googlegroups.com> <4ed9732b$0$294$14726298@news.sunsite.dk> NNTP-Posting-Host: 84.45.235.129 Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Trace: localhost.localdomain 1323002558 21394 84.45.235.129 (4 Dec 2011 12:42:38 GMT) X-Complaints-To: usenet@localhost.localdomain NNTP-Posting-Date: Sun, 4 Dec 2011 12:42:38 +0000 (UTC) User-Agent: Pan/0.135 (Tomorrow I'll Wake Up and Scald Myself with Tea; GIT 30dc37b master) Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:10486 On Sat, 03 Dec 2011 20:05:24 -0800, Roedy Green wrote: > On Sat, 03 Dec 2011 07:44:48 -0500, Eric Sosman > wrote, quoted or indirectly quoted > someone who said : > >> What is the big-Oh complexity of Collections.sort(List) >>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 |