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

Groups > comp.lang.python > #20411

Re: name of a sorting algorithm

Show all headers | View raw

On Tue, 14 Feb 2012 16:22:45 +0000, Arnaud Delobelle <arnodel@gmail.com>
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/

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 12:06 -0500

csiph-web