Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!news.stack.nl!newsfeed.xs4all.nl!newsfeed5.news.xs4all.nl!xs4all!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.001 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'sure.': 0.05; 'decent': 0.07; 'python': 0.08; '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; 'algorithm': 0.13; 'structures': 0.15; '...,': 0.16; '>could': 0.16; ">it's": 0.16; 'bieber': 0.16; 'email addr:ix.netcom.com': 0.16; 'email name:wlfraed': 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; 'sizes,': 0.16; 'swaps': 0.16; 'then:': 0.16; 'url:netcom': 0.16; 'url:wlfraed': 0.16; 'wulfraed': 0.16; 'wrote:': 0.18; 'received:166': 0.18; 'seems': 0.20; 'memory': 0.21; 'url:home': 0.21; 'feb': 0.22; '+0100,': 0.23; 'ancient': 0.23; 'item.': 0.23; 'elements': 0.24; 'guess': 0.26; 'code': 0.26; 'bit': 0.28; "i'm": 0.28; 'second': 0.28; 'class': 0.29; 'url:wiki': 0.29; 'array': 0.30; '(unless': 0.30; 'logic': 0.30; 'outer': 0.30; "didn't": 0.30; 'supposed': 0.32; 'tue,': 0.32; 'list': 0.32; 'sort': 0.33; 'points': 0.34; 'header:X-Complaints-To:1': 0.34; 'lee': 0.34; 'loop': 0.34; 'anything': 0.34; 'someone': 0.34; 'algorithms': 0.34; 'probably': 0.35; 'to:addr:python-list': 0.35; 'starting': 0.36; 'data.': 0.36; 'list,': 0.36; 'received:org': 0.36; 'disk': 0.37; 'drives': 0.37; 'but': 0.37; 'charset:us-ascii': 0.37; 'should': 0.38; 'data': 0.38; 'url:org': 0.39; 'url:en': 0.39; "i'd": 0.39; 'called': 0.40; 'being': 0.40; 'to:addr:python.org': 0.40; 'selection': 0.40; 'back': 0.60; 'simple': 0.61; 'improve': 0.62; 'increase': 0.62; 'subject:name': 0.67; 'dennis': 0.73; 'anywhere.': 0.84; 'faded': 0.84; 'selection,': 0.84; 'swap': 0.84; 'sweep': 0.84 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 10:31:25 -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: 51 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1329233507 news.xs4all.nl 6951 [2001:888:2000:d::a6]:51676 X-Complaints-To: abuse@xs4all.nl Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:20403 On Tue, 14 Feb 2012 16:01:05 +0100, Jabba Laci wrote: >Could someone please tell me what the following sorting algorithm is called? > >Let an array contain the elements a_1, a_2, ..., a_N. Then: > >for i = 1 to N-1: > for j = i+1 to N: > if a_j < a_i then swap(a_j, a_i) > Off hand... The ancient Bubble-Sort... http://en.wikipedia.org/wiki/Bubble_sort As I recall, when I last had to code a simple sort for class (1976-1980) I double-ended the algorithm so that I'd sweep both down and up the list on each main loop. Probably didn't do anything to improve the algorithm (unless I also added logic to track where the last swap took place, and adjusted the outer loop end points to one place outside of those swaps) {Hmm, and I thought I was being clever back then: http://en.wikipedia.org/wiki/Cocktail_sort } >It's so simple that it's not mentioned anywhere. I guess it's called >"selection sort" but I'm not sure. The minimum selection sort is an >improvement of this one. It is NOT a "selection sort", which scans the data for the item that is supposed to be "first" in the list, and swaps just that item. It then scans again starting at the second place... http://en.wikipedia.org/wiki/Selection_sort For the whole category of sorts: http://en.wikipedia.org/wiki/Sorting_algorithm {Or any DECENT textbook on data structures and algorithms should cover at least: bubble, selection, insertion, quicksort, and heapsort -- oh, and merge sort though that seems to have faded a bit [in my world, at least] with the increase in computer memory sizes, b-tree/ISAM disk files, etc. vs the use of multiple tape drives for sequentially accessed data. [apparently merge sort has been revived for use in the Python internal sort algorithm http://en.wikipedia.org/wiki/Timsort ]} -- Wulfraed Dennis Lee Bieber AF6VN wlfraed@ix.netcom.com HTTP://wlfraed.home.netcom.com/