Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sample.eng.ohio-state.edu!purdue!haven.umd.edu!mimsy!oasys!tdsmith
From: tdsmith@oasys.dt.navy.mil (Timothy Smith)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: Combsort algorithm
Message-ID: <8454@oasys.dt.navy.mil>
Date: 14 Jun 91 15:31:57 GMT
References: <8235@oasys.dt.navy.mil> <1991Jun13.175106.6902@unislc.uucp>
Reply-To: tdsmith@oasys.dt.navy.mil (Timothy Smith)
Organization: David Taylor Research Center, Bethesda, MD
Lines: 65

In article <1991Jun13.175106.6902@unislc.uucp> ttobler@unislc.uucp (Trent Tobler) writes:
>From article <8235@oasys.dt.navy.mil>, by tdsmith@oasys.dt.navy.mil (Timothy Sm
>ith):
>>
>>        Start with an unsorted list of n objects (or pointers to objects,
>> same thing...)  Is there a sort algorithm which is o(n)?  If so, use
>> it to sort (23 41 55 12 11 9 10) with only 7 moves. I'm skeptical!
>>
>Except than o(n) does not mean n moves.  o(n) means it takes exactly
>k*n with k constant.

    Oops!  Guess I was typing a bit too quickly.

In your example, suppose the numbers are in the range
>of 0-255.  One o(n) sort that I can think of goes like this.
>
>   We have an array of 256 elements labeled A(x) which can hold a range of
>0 up to the maximum size of an array we wish to sort...
      {...stuff...}
>Then, go though this array, starting from 0 and working to 256, and
>store A(x) x's into the original array, ie..
	 {...more stuff...}
>This method takes 2 * 256 + 2 * n steps.  In otherwords, it is o(n)
>
>--
>  Trent Tobler - ttobler@csulx.weber.edu

    Let m be the number of buckets. I get O(2*m+2*n) => O(m+n) => O(max(m,n))
=> max(O(n),O(m))
    The problem as I see it is that the bucket range has to be defined
ahead of time.  For reccuring problems this is fine, since m can be
fixed.  But for arbitrary problems it is not so clear.
    For example, sorting  (3 1 2) can be done with 3 buckets, but
(10,000 1 2) requires 10,000 buckets. Are both problems O(3)? In theory,
yes. In practice, no. A key variable has been neglected.
    For real numbers m is infinite. I conclude combsort is not a general 
purpose sorting algorithm, just a special case integer sort over a finite 
set of input possibilities. In THEORY combsort is O(n), but theory sometimes 
has little relation to practicality. If m is O(n) then the sort is O(n),
otherwise the analysis is misleading.  If m >> n then combsort is O(1)!
AND, if m >> n^2 then selection sort wil beat it, even though selection
sort is O(n^2)!
    I bring this up because this isn't comp.theory, so O(n) could be 
taken out of context.
      - Complexity is not a quantitative measure of utility between 
	algorithms, it is a qualitatively estimate of the time
	for different sized runs with the same algorithm.
      - Two algorithms with the same complexity may have run times that
	differ by orders of magnitude.  
      - Complexity claims are sensitive to how the problem is
	posed. Sometimes the worst case complexity is quoted, sometimes
	the average, and sometimes the most likely.  This becomes a
	problem when the worst case for one is compared with the average
	for another.
      - There are no general purpose sorts which do better than O(n*logn).
      - There are some special purpose integer sorts that are O(n).
      - If the input domain is restricted to n << m combsort becomes
	O(1), i.e. runs in constant time. It also becomes a very inefficient
	algorithm. (for the above example, bubblesort uses aprox 4
	moves to sort (10,000 2 1), combsort uses aprox 20,000 moves.
	On (10,000 5,000 4 3 2 1), a problem which is twice as big,
	bublesort uses aprox 25 moves, combsort 20,000.)


Tim Smith