Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsreader4.netcologne.de!news.netcologne.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; 'bubble': 0.09; 'loop.': 0.09; 'oh,': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'xor': 0.09; 'adjacent': 0.16; 'bieber': 0.16; 'called,': 0.16; 'email addr:ix.netcom.com': 0.16; 'email name:wlfraed': 0.16; 'ends,': 0.16; 'from:addr:ix.netcom.com': 0.16; 'from:addr:wlfraed': 0.16; 'from:name:dennis lee bieber': 0.16; 'message-id:@4ax.com': 0.16; 'received:wlfraed': 0.16; 'swaps': 0.16; 'url:netcom': 0.16; 'url:wlfraed': 0.16; 'wulfraed': 0.16; 'wrote:': 0.18; 'received:166': 0.18; 'written': 0.19; 'memory': 0.21; 'url:home': 0.21; '(or': 0.22; 'feb': 0.22; 'items.': 0.23; 'index': 0.24; 'guess': 0.26; 'function': 0.27; 'looks': 0.27; 'pass': 0.29; 'avoiding': 0.29; 'temporary': 0.29; 'outer': 0.30; 'tue,': 0.32; 'list': 0.32; 'sort': 0.33; 'header:X-Complaints-To:1': 0.34; 'lee': 0.34; 'loop': 0.34; 'assignment': 0.34; 'to:addr:python- list': 0.35; 'received:org': 0.36; 'but': 0.37; 'charset:us- ascii': 0.37; 'using': 0.37; 'hold': 0.38; 'being': 0.40; 'might': 0.40; 'to:addr:python.org': 0.40; 'selection': 0.40; 'more': 0.61; 'course,': 0.62; 'subject:name': 0.67; 'dennis': 0.73; 'swap': 0.84; 'sort.': 0.91 X-Injected-Via-Gmane: http://gmane.org/ To: python-list@python.org From: Dennis Lee Bieber Subject: Re: name of a sorting algorithm Date: Tue, 14 Feb 2012 12:06:13 -0500 References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Gmane-NNTP-Posting-Host: mobile-166-147-103-229.mycingular.net X-Newsreader: Forte Agent 6.00/32.1186 X-No-Archive: YES 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: 32 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1329239202 news.xs4all.nl 6942 [2001:888:2000:d::a6]:42375 X-Complaints-To: abuse@xs4all.nl Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:20411 On Tue, 14 Feb 2012 16:22:45 +0000, Arnaud Delobelle wrote: ... > >No, it's not Bubble Sort. Bubble sort only swaps adjacent terms. > Oh, right... I guess I focused more on the number of swaps (that is, the swap being /inside/ the inner loop) more than what was being swapped, whereas a selection sort has one swap per outer loop. >I don't know what this sort is called, if it even has a name. It's a >kind of Selection Sort, as each pass it looks for the minimum of the >remaining unsorted items. But 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). > But with all those swaps you still need the register (or other memory location) to hold a temporary copy. Selection only needs an assignment of the minima (maxima) index until the inner loop ends, then a swap using the index. Of course, the swap() function might have been written using in-place XOR sequences: A = A xor B; B = B xor A; A = A xor B thereby avoiding need for a temporary location. -- Wulfraed Dennis Lee Bieber AF6VN wlfraed@ix.netcom.com HTTP://wlfraed.home.netcom.com/