Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!viusys!uxui!unislc!ttobler
From: ttobler@unislc.uucp (Trent Tobler)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: Combsort algorithm
Message-ID: <1991Jun13.175106.6902@unislc.uucp>
Date: 13 Jun 91 17:51:06 GMT
References: <8235@oasys.dt.navy.mil>
Organization: unisys
Lines: 32

From article <8235@oasys.dt.navy.mil>, by tdsmith@oasys.dt.navy.mil (Timothy Smith):
> In article <193e8efd.ARN1453@pilhuhn.ka.sub.org> hwr@pilhuhn.ka.sub.org (Heiko W.Rupp) writes:
>>Imagine that You have 50 States. Bucket sort means now sorting the letters
>>according to the name of the State in one of 50 Boxes (or Buckets) labeled
>>with the name of the State. Going once through the data costs O(n); adding
>>an element to the head of the list costs O(1) -> You get linear (O(n)) running
>>time.
> 
> What?  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.  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.  To sort,
simply initialize this array to all 0, then for each item to sort, increment
to corresponding element.  For the example you give, A(x) would be
A(0)=0, A(1)=0, ..., A(9)=1, A(10)=1, A(11)=1,  ... A(254)=0, A(255)=0
Then, go though this array, starting from 0 and working to 256, and
store A(x) x's into the original array, ie..
 
no 0's, no 1's, ..., one 9, one 10, one 11, ... no 254's, no 255's.
and you have the original array, sorted.  ( 9 10 11 12 23 41 55 )

This method takes 2 * 256 + 2 * n steps.  In otherwords, it is o(n)


--
  Trent Tobler - ttobler@csulx.weber.edu