name of a sorting algorithm

[Jabba Laci]

Hi,

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)

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.

Thanks,

Laszlo

 

[Mel Wilson]

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 in xrange (N-1):
for j in xrange (i, N):
if a[j] < a:
a, a[j] = a[j], a

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's what Wikipedia says a selection sort is: put the least element in [0],
the least of the remaining elements in [1], etc.

Mel.

 

[Ulrich Eckhardt]

Am 14.02.2012 16:01, schrieb Jabba Laci:

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)

It's so simple that it's not mentioned anywhere.

Please do your own homework. This code isn't even Python!

I guess it's called "selection sort" but I'm not sure.

You guessed right.


Uli

 

[Prasad, Ramit]

for i in xrange (N-1):
for j in xrange (i, N):
if a[j] < a:
a, a[j] = a[j], a

It's what Wikipedia says a selection sort is: put the least element in [0], the least of the remaining elements in [1], etc.

If your only requirement to match to selection sort is the end result, then every sort would be selection sort. If you meant "put the least element in [0] in the firstpass" then that would indeed be selection sort, but that is not what the above code does. The above code is bubble sort.

Ramit


Ramit Prasad | JPMorgan Chase Investment Bank | Currencies Technology
712 Main Street | Houston, TX 77002
work phone: 713 - 216 - 5423

--

This email is confidential and subject to important disclaimers and
conditions including on offers for the purchase or sale of
securities, accuracy and completeness of information, viruses,
confidentiality, legal privilege, and legal entity disclaimers,
available at http://www.jpmorgan.com/pages/disclosures/email.

 

[Mel Wilson]

for i in xrange (N-1):
for j in xrange (i, N):
if a[j] < a:
a, a[j] = a[j], a

It's what Wikipedia says a selection sort is: put the least element in
[0], the least of the remaining elements in [1], etc.

If your only requirement to match to selection sort is the end result,
then every sort would be selection sort. If you meant "put the least
element in [0] in the first pass" then that would indeed be selection
sort, but that is not what the above code does. The above code is bubble
sort.

Well, the classic bubble sort swaps adjacent elements until the extreme one
gets all the way to the end. This sort continually swaps with the end
element during one pass until the end element holds the extreme. Then it
shrinks the range and swaps then next less extreme into the new end element.
It does extra swaps because it combines the swap operation with recording
the temporary extreme while it searches the subrange.

Mel.

 

[Prasad, Ramit]

Well, the classic bubble sort swaps adjacent elements until the extreme one
gets all the way to the end. This sort continually swaps with the end
element during one pass until the endelement holds the extreme. Then it
shrinks the range and swaps then next less extreme into the new end element.
It does extra swaps because it combines the swap operation with recording
the temporary extreme while it searches the subrange.

My apologies, you are correct. It is a selection sort, just an
inefficient one.

Ramit


Ramit Prasad | JPMorgan Chase Investment Bank | Currencies Technology
712 Main Street | Houston, TX 77002
work phone: 713 - 216 - 5423

--
This email is confidential and subject to important disclaimers and
conditions including on offers for the purchase or sale of
securities, accuracy and completeness of information, viruses,
confidentiality, legal privilege, and legal entity disclaimers,
available at http://www.jpmorgan.com/pages/disclosures/email.

 

[Prasad, Ramit]

My apologies, you are correct. It is a selection sort, just an inefficient one.

Hmm, I think I should say it is neither since it reminds me of a hybrid of
both (bubble/selection).

The swapping seems very bubble sort, but the looking for the min / max
case seems selection sort-ish. Whatever it is, it is certainly
inefficient.

Ramit


Ramit Prasad | JPMorgan Chase Investment Bank | Currencies Technology
712 Main Street | Houston, TX 77002
work phone: 713 - 216 - 5423

--

This email is confidential and subject to important disclaimers and
conditions including on offers for the purchase or sale of
securities, accuracy and completeness of information, viruses,
confidentiality, legal privilege, and legal entity disclaimers,
available at http://www.jpmorgan.com/pages/disclosures/email.