Re: comparison of sorting algorithms

From: CBFalconer (cbfalconer_at_yahoo.com)
Date: 06/14/04 

Date: Mon, 14 Jun 2004 05:11:56 GMT

Dan Tex1 wrote:
>
... snip ...
>
> I tested a hybrid, non-recursive quicksort that uses insertion
> sort as partitions of data to be sorted become smaller. I tried
> it with different types of data in all sorts of different
> starting orders. I tried small data sets and large ones ( many
> megabytes of data, files 30, 40 MB and larger ). I found that
> it worked great for pretty much eveything.

There is always an input that will make it run in O(N*N). See:

  SOFTWARE—PRACTICE AND EXPERIENCE, VOL. 29(0), 1–4 (0 1999)
  A Killer Adversary for Quicksort
  M. D. MCILROY 

-- 
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!

Relevant Pages

  • Re: fastest sorting routine for 2-D array of long values
    ... Disconnected ADO recordset? ... That has a sort method... ... Maybe it has to be a non-recursive quicksort, but it is not easy at all to find these. ... RBS ...
    (microsoft.public.excel.programming)
  • Re: Novell Desktop Linux 10: getting closer to a toss up between Linux & Windows?
    ... On the other hand Linux has a well known (and sort of (almost) standardized ... But /video has become a sort of standard I think. ... I use 'locate' and 'grep' many times a day. ... As you have discovered finding something across many disk and partitions with so many giga bytes ...
    (comp.sys.ibm.pc.hardware.chips)
  • RE: Checking if entry is already in List
    ... Below is an InsertItem subroutine, a fast Heap sort, and a binary search to ... Dim ExactMatch As Boolean ... Dim nent As Long ... ' find the insertion position but skip insertion if no dups allowed and ...
    (microsoft.public.vb.general.discussion)
  • Re: moving data from one place to another in a text file
    ... random key produced sort time five times faster than n * log ... >in some partitions. ... unique words per partition were: ... >the thread to do its own parsing. ...
    (comp.lang.cobol)
  • sorting (was Re: VERY URGENT C PROGRAM)
    ... The first point is true of bubble sort and ... less true of insertion sort (because we have to make room for the ... insertion in the array). ... deck of cards handy, pick out two cards and hold them in one hand. ...
    (comp.lang.c)