Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!ecngs!feeder.ecngs.de!xlned.com!feeder7.xlned.com!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.000 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'pointer': 0.05; '"""': 0.07; 'variant': 0.07; 'python': 0.08; '(there': 0.09; 'bubble': 0.09; 'indicates': 0.09; 'pointers': 0.09; 'am,': 0.12; 'algorithm': 0.13; '...,': 0.16; 'adjacent': 0.16; 'bieber': 0.16; 'called,': 0.16; 'disagree.': 0.16; 'element,': 0.16; 'elements,': 0.16; 'sorted,': 0.16; 'swaps': 0.16; 'then:': 0.16; '\xa0for': 0.16; '\xa0in': 0.16; "\xa0it's": 0.16; '\xa0this': 0.16; 'cc:addr :python-list': 0.16; 'wrote:': 0.18; 'repeated': 0.18; 'programming': 0.20; 'cheers,': 0.20; 'cc:no real name:2**0': 0.21; '(but': 0.21; 'header:In-Reply-To:1': 0.22; 'feb': 0.22; '+0100,': 0.23; 'ancient': 0.23; 'items.': 0.23; 'pair': 0.23; 'seemingly': 0.23; '\xa0if': 0.23; 'elements': 0.24; 'index': 0.24; 'cc:2**0': 0.26; 'looks': 0.27; 'variable': 0.28; 'needed,': 0.28; 'order.': 0.28; 'repeatedly': 0.28; 'pass': 0.29; 'message- id:@mail.gmail.com': 0.29; 'class': 0.29; 'cc:addr:python.org': 0.29; 'url:wiki': 0.29; 'array': 0.30; 'quoting': 0.30; '(the': 0.30; 'ago': 0.31; 'actually': 0.31; 'pure': 0.32; 'remaining': 0.32; 'tue,': 0.32; 'list': 0.32; 'sort': 0.33; 'instead': 0.33; 'agree': 0.33; 'points': 0.34; 'lee': 0.34; 'someone': 0.34; 'algorithms': 0.34; 'jump': 0.34; 'probably': 0.35; 'list.': 0.35; 'comparing': 0.37; 'element': 0.37; 'saves': 0.37; 'received:google.com': 0.37; 'using': 0.37; 'another': 0.37; 'either': 0.37; 'received:209.85': 0.38; 'necessary.': 0.38; 'somewhat': 0.38; 'doing': 0.38; 'smaller': 0.39; 'url:org': 0.39; 'url:en': 0.39; 'received:209': 0.39; 'selection': 0.40; "you'll": 0.61; 'simple': 0.61; 'kind': 0.62; 'selected': 0.66; 'subject:name': 0.67; 'dennis': 0.73; 'placing': 0.74; 'algorithm,': 0.84; '\xa0but': 0.84; 'sort.': 0.91 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type:content-transfer-encoding; bh=D/d2GMpqRr31kiRBdlSoJFRYlXz2OEnsCG6lyoPDdbg=; b=v42dRmPxDl0pRv/WJSWgR6jFGtYby6ftLoRgLdJIFpISl8oPTEAZHf8ohO/kVCD2hd yHYckeA32292ziSGYzCxh+OwgNA2VUlZ7ikeRT3Qn+OR6y7ddXbmd7iJrjbzl2BVNUMD rDL6QguWawW9A5gsGrLuXZ//HqFNkpUqBZFKE= MIME-Version: 1.0 In-Reply-To: <73b8d112-9e94-486e-b06c-bdeebc0bf964@q12g2000yqg.googlegroups.com> References: <73b8d112-9e94-486e-b06c-bdeebc0bf964@q12g2000yqg.googlegroups.com> From: Ian Kelly Date: Tue, 14 Feb 2012 10:37:35 -0700 Subject: Re: name of a sorting algorithm To: Den Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Cc: python-list@python.org X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 66 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1329241087 news.xs4all.nl 6905 [2001:888:2000:d::a6]:56929 X-Complaints-To: abuse@xs4all.nl Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:20412 On Tue, Feb 14, 2012 at 9:55 AM, Den wrote: > On Feb 14, 8:22=A0am, Arnaud Delobelle wrote: >> On 14 February 2012 15:31, Dennis Lee Bieber wro= te: >> >> > On Tue, 14 Feb 2012 16:01:05 +0100, Jabba Laci >> > wrote: >> >> >>Could someone please tell me what the following sorting algorithm is c= alled? >> >> >>Let an array contain the elements a_1, a_2, ..., a_N. Then: >> >> >>for i =3D 1 to N-1: >> >> =A0 =A0for j =3D i+1 to N: >> >> =A0 =A0 =A0 =A0if a_j < a_i then swap(a_j, a_i) >> >> > =A0 =A0 =A0 =A0Off hand... The ancient Bubble-Sort... >> >> >http://en.wikipedia.org/wiki/Bubble_sort >> >> Ahem... >> >> No, it's not Bubble Sort. =A0Bubble sort only swaps adjacent terms. >> >> I don't know what this sort is called, if it even has a name. =A0It's a >> kind of Selection Sort, as each pass it looks for the minimum of the >> remaining unsorted items. =A0But it ruffles the unsorted list each pass, >> seemingly to save using an extra register to store the current minumum >> (there was a time when registers were at a premium). >> >> -- >> Arnaud > > I disagree. =A0In a bubble sort, one pointer points to the top element, > while another descents through all the other elements, swapping the > elements at the pointers when necessary. =A0Then the one pointer moved > down to the next element and the process repeats. =A0This looks like the > bubble sort to me. =A0It was one of the first algorithms I had to > program in my first programming class in 1969. Either you're misremembering, or the algorithm you programmed 43 years ago was not actually bubble sort. Quoting from Wikipedia: """ Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. """ In the present algorithm, you'll note that elements in the unsorted part of the list do not "bubble up" as they would in bubble sort. Rather, they jump around somewhat randomly until they are finally selected for the current sort index. I agree with Arnaud -- this is a selection sort variant that saves a local variable (the index of the minimum element) by placing it at the current sort index instead -- at the cost of doing additional swaps. Probably not a good trade-off in Python (but then again, no pure Python sort algorithm is likely to perform better than the built-in). Cheers, Ian