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

Groups > comp.lang.python > #20399 > unrolled thread

name of a sorting algorithm

Back to article view | Back to comp.lang.python

Contents

  name of a sorting algorithm Jabba Laci <jabba.laci@gmail.com> - 2012-02-14 16:01 +0100
    Re: name of a sorting algorithm Mel Wilson <mwilson@the-wire.com> - 2012-02-14 10:25 -0500
      RE: name of a sorting algorithm "Prasad, Ramit" <ramit.prasad@jpmorgan.com> - 2012-02-14 15:50 +0000
        RE: name of a sorting algorithm Mel Wilson <mwilson@the-wire.com> - 2012-02-14 11:44 -0500
          RE: name of a sorting algorithm "Prasad, Ramit" <ramit.prasad@jpmorgan.com> - 2012-02-14 20:21 +0000
          RE: name of a sorting algorithm "Prasad, Ramit" <ramit.prasad@jpmorgan.com> - 2012-02-14 20:13 +0000
    Re: name of a sorting algorithm Ulrich Eckhardt <ulrich.eckhardt@dominolaser.com> - 2012-02-14 16:33 +0100

#20399 — name of a sorting algorithm

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

[toc] | [next] | [standalone]

#20402

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

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.

[toc] | [prev] | [next] | [standalone]

#20405

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

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.  

[toc] | [prev] | [next] | [standalone]

#20408

Prasad, Ramit wrote:

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

[toc] | [prev] | [next] | [standalone]

#20416

Prasad, Ramit wrote:
> 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.  

[toc] | [prev] | [next] | [standalone]

#20417

Wilson, Mel wrote:
>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.

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.  

[toc] | [prev] | [next] | [standalone]

#20406

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web