Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #20403

Re: name of a sorting algorithm

Show all headers | View raw

On Tue, 14 Feb 2012 16:01:05 +0100, Jabba Laci <jabba.laci@gmail.com>
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/

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Re: name of a sorting algorithm Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2012-02-14 10:31 -0500

csiph-web