Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!think.com!mintaka!bloom-beacon!eru!hagbard!sunic!ugle.unit.no!mack.uit.no!stud.cs.uit.no!staale
From: staale@stud.cs.uit.no (Staale Schwenke)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: Combsort algorithm
Message-ID: <1991Jun7.141201.18000@mack.uit.no>
Date: 7 Jun 91 14:12:01 GMT
References: <191d6f59.ARN12eb@pilhuhn.ka.sub.org> <193e8efd.ARN1453@pilhuhn.ka.sub.org> <8235@oasys.dt.navy.mil>
Sender: news@mack.uit.no (USENET News System)
Reply-To: staale@stud.cs.uit.no (Staale Schwenke)
Organization: University of Tromsoe, Norway
Lines: 19

In article <8235@oasys.dt.navy.mil>, tdsmith@oasys.dt.navy.mil (Timothy Smith) writes:
|> 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!
|>                                              ^^^^^ 
|> Tim                                          Hm.. Reads

Assuming , like in the original example, you have a finite number of different keys e.g. 0-100, this could be done by going once through the data. Based on the value each number would be moved into a bucket. (F.ex. an array [0..100] if identical keys were not allowed).
-- 
------------------------------------------------------------------------
Staale Schwenke		E-mail: staale@stud.cs.uit.no
------------------------------------------------------------------------