Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!ira.uka.de!smurf!flatlin!pilhuhn!hwr From: hwr@pilhuhn.ka.sub.org (Heiko W.Rupp) Newsgroups: comp.sys.amiga.programmer Subject: Re: Combsort algorithm Message-ID: <193e8efd.ARN1453@pilhuhn.ka.sub.org> Date: Mon, 03 Jun 91 21:17:17 GMT References: <191d6f59.ARN12eb@pilhuhn.ka.sub.org> <1991May15.220144.27507@unislc.uucp> Distribution: world Lines: 27 In article , Anders Andersson writes: > In <1991May15.220144.27507@unislc.uucp> ttobler@unislc.uucp (Trent Tobler) writes: > > >From article <191d6f59.ARN12eb@pilhuhn.ka.sub.org>, by hwr@pilhuhn.ka.sub.org (Heiko W.Rupp): > > [..] > >> Which bucket-sort you can even achieve O(n)! > > ^^^ is this suppost to be 'With'? Yup ! > > > I'm not sure what bucket sort is, but radix sort is O(n) and it 'only' requires > twice the memory (i.e. it needs a extra copy of the data). In a general application, > you only sort pointers to data objects, so this isn't too bad. Bucketsort: 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. Gruesse -Heiko -- Heiko W.Rupp, Gerwigstr.5, D-7500 Karlsruhe 1 | hwr@pilhuhn.ka.sub.org Tel: +49 7021 693642 (voice only) | uk85@dkauni2.bitnet They say that killing a shopkeeper brings bad luck.