Selection sort

[dn]

On 25/12/2021 03.22, vani arul wrote:
> Hello,
> I am trying write a code.Can some help me find the error in my code.
> Thanks!
> 
> 
> def selectionsort(arr):
>    # le=len(arr)
>     for b in range(0,len(arr)-1):
>         pos=b
>         for a in range(b+1,len(arr)-1):
>             if arr[b]>arr[a+1]:
>                 arr[b],arr[a+1]=arr[a+1],arr[b]
>     return arr
> 
> arr=[3,5,9,8,2,6]
> print(selectionsort(arr))


This looks like a typical 'homework question'. Accordingly, we are happy
to help, but that means helping you to learn Python, NOT to help by
writing a homework-solution!


Evidently you are expected to learn some Python, but additionally an
algorithm (or method) for sorting. Also apparent, is that the current
attempt has been taken from another programming language - rather than
using a more 'pythonic' idiom. All fine, but with a "but...".

One assumes, the Python sort() built-in function may not be used. Even
so, you can ask the computer to test the success (or otherwise) of your
efforts, by adding to the end of the existing code, something like:

print( "Was the algorithm successful?",
    selection_sort( arr ) == sorted( arr )
    )

(I've recently 'enjoyed' an eye operation, so actively seek ways of
having the computer 'see' or check things that are difficult for me -
pending already-excellent recovery progress...)


The question has already been asked: "What are you expecting the code to
do?". This is vital. What is your target? (and when you ask us a
question, how do we know exactly what your target might be?).

Regardless, it is *always* the first question to be asked in attempting
to find a solution to any problem - thus, has much wider application
than computing then! How does one know if the aim is true, without first
defining "the target"?


The key to coding any algorithm is to (temporarily) forget Python, and
to first understand the method - how it works.

What I have often done in the past, is to ask trainees to bring a
pack/deck of Playing Cards - however a few scraps of paper with the
numbers: 3,5,9,8,2, and 6 written on them, will do just as well.

What we want is three sets of the same numbers. One set to move around
(the above), and the other two static - so could write them (in a row)
across a sheet of paper. The first 'static' set, should be the numbers
in the sequence given by the question, ie 'the start position'. Put this
at the 'top' of a desk or flat surface. The second 'static' set, is the
"target", ie the same digits, but in sorted-order. Artie them across a
second piece of paper, and place that at the 'bottom' of the desk. So,
now we can see a starting-position, and a final sequence.

The 'magic' is the bit that happens "in the middle" ("in-between")!

Now, using the space on your desk, between the 'start' and 'end',
arrange the 'numbers' in the given sequence, across a 'row'.

With your brain (and hands) as the 'computer', work the algorithm you've
already started using:

1	commence with the first item in the list:
	ie take the "3" in your left hand
	(or perhaps put a suitable finger on it)
2	then compare that with the "5" (right hand/finger)
3	given that three is less than five, what should happen?
4	next compare the "3" with the "9"
	(left finger doesn't move, right hand/finger does!)
5	what should happen at this time?
6	keep going, until...
	you compare the "3" with the "2"
	what happens now?

That's the basic algorithm done!

Continuing the above, after a while there are no more items left to
compare with the one under your left hand/finger. What is the state of
the list?

Not much has changed, but what can we say about the situation
(placement) of the item which is in the first-position/at the left side
of the scraps of paper/playing cards? How does it relate to the
first-position in the target-row?

For the next stage, start with the second item in the list (move your
left hand/pointing-finger!):
1	run through, similar to the above
2	until you (your right hand) reach the end
	(yes, it is starting to become a bit boring, but...)

When you have once-again 'run out' of items to compare, what can now be
said about the state of the list? About the values in the first two
positions (and their equivalents in the 'target')?

So, change of thinking: could it be considered that we have two
'sub-lists' (amongst our paper-scraps/playing-cards)? One with two items
in it, the other containing 'all the others'. What can we say about the
'left-sub-list' (and specifically its sequencing)?


So, at this time, please decide if you need to continue with the above
cycles in order to fully-understand how the method arrives at the
desired conclusion - or keep going to prove 'everything' to your
satisfaction, by running right-through. Has the algorithm managed to
arrange the slips of paper/playing cards into the correct sequence, as
portrayed by the bottom-row of numbers?


Once you have confidence in the algorithm, it can be implemented in
code. (but not before! Don't be in too much of a hurry!) So, let's think
about how to represent the algorithm *and* the data, as program-code.

When sorting, items each can be described in two ways. The first item
(in the sample data provided) has the *value* "3". That same item, is in
the first *position* of the list.

Alternately, we can say/think, that the first item in the sample-data
occupies the first position in the list, and has the value "3".

NB I've written the value "3" as inside quotation-marks for
emphasis/identification - it may or may not be a Python-string because
(the sample list) will sort correctly either way, but it appears to be
of integer type, so the quotation-marks are just a way of writing and
emphasis, OK?)


Consider this concept of the two ways to look at each item in the list,
from the perspective of the algorithm/method:-

The *value* of each item will never change (during the sort). We are not
going to increase each value by 10%, for example - we're not giving
employees a salary-raise, are we?

However, the *position* of items may change - because the objective of
sorting is to arrange the items into some definition of sequence (and we
kind-of assume that 'change' is required, because the (sample) list does
not start-out as being in-order).


Accordingly, one of the challenges is to keep separate in our minds, an
item's value, and its position in the list - even though the two
describe the same item!

NB the English word "position", is usually called an "index" or even an
"offset" in Computer Science - ie the item's relative-position in
relation to the beginning of the list. In Python, lists, or rather their
indexes/indices, are zero-based - which means that the first item is
"addressed" as having an index of "0" - ie in Python:

	list_name[ 0 ]


Thinking back to our 'playing with paper/cards' above, what is the
purpose of the outer loop? Considering "targets" again: by the end of
each cycle through the loop, what will have been achieved?

Similarly, that of the inner loop? During a single cycle of the
outer-loop, what is the objective of the complete run through the
inner-loop?


When you answer these two questions, how are you expressing the problem
in terms of each item's "position" - and its "value"?


It turns-out, we only need to look any item's value or items' values
within the if-condition (and no-where else in the code). Whereas, we use
indexing to control both of the for-loops (and later, if an exchange of
position is necessary).


So, now (finally!) we can build a 'skeleton' of code, taking it (an
algorithmic) step-by-step to add, or 'flesh-out', more detail gradually:

1
code an outer-loop to traverse the list. With nothing else 'inside' it,
print the index once for each execution of the loop, ie execution should
show you "0, 1, 2, etc" (except each on its own line, not
comma-separated - unless you know how to do that in Python). Ensure the
indexing starts and stops correctly - not too early, nor too late, in
terms of the length of the list - watch-out for that "zero-based"
consideration mentioned earlier, and ensure that last item is not
'visited'! (why not?)

2
add code for the inner-loop. Remembering the observation (above) that
this should only traverse the right-hand sub-list (but should this one
go all the way to 'the end'?). Insert another print statement and
observe the behavior of this (second) index. Ensure that it starts, and
stops, correctly (wrt to the length of the *sub*-list)?

3
Now the program(me) features two indexes/indices. Thinking back to the
algorithm, to what does the first (outer-loop) index 'point'? Similarly,
to what does the second (inner-loop) index point? With those two
thoughts in-mind, does this make it easier to decide which two values to
compare when it comes to writing the if-condition?

NB you could pause 'development' at this point, and use this step in the
process to check that the if-condition is correct (employ one or two
judiciously-placed debug-print statements).

Thereafter, do the (aforementioned) two indexes/indices also make it
easy to decide on the positions of the two items that (may) need to be
'swapped'?

At this point, code the entire if-suite, and (if you haven't already) it
may be helpful to add another debug-print (or two), to confirm which
indexes and values the code is comparing, and which values and indexes
are being inter-changed (but only should such action be necessary).


Hopefully, you have now figured-out both the algorithm, and the code to
implement same. Does it work? Is the list properly sorted by the end?

If not, come back to us with a more detailed question (plus code and
sample output).

If you're successful, also revert (with pride), and we'll try showing
you another way to implement the same algorithm - but in a manner
many?most other programming languages cannot. In other words, a
'pythonic' solution...


Apologies - I've taken several sessions to write this msg, with breaks
to rest my eyes in-between. Now I've clicked the wrong button on the
Spelling-Checker, but can't figure-out what I did/didn't correct, or
correct correctly. Confused? So am I. Please be understanding for this
and any other typos or proof-reading failings...
-- 
Regards,
=dn