[Tutor] Sorting a list manually

[dn]

On 12/08/2021 19.23, nzbz xx wrote:
> I am trying to create a def function where I can sort a list in ascending
> order by starting with the first item in the list and comparing it to the
> number next to it. The evolution of the list  [4, 3, 2, 1] would look as
> such:
> 
> [*4*, 3, 2, 1] [3, *4*, 2, 1] [3, 2, *4*, 1] [3, 2, 1, *4*]
> [*3*, 2, 1, 4] [2, *3*, 1, 4] [2, 1, *3*, 4] [2, 1, 3, *4*]
> [*2*, 1, 3, 4] [1, *2*, 3, 4] [1, 2, *3*, 4] [1, 2, 3, *4*]
> [*1*, 2, 3, 4] [1, *2*, 3, 4] [1, 2, *3*, 4] [1, 2, 3, *4*]
> 
> There's a total of 12 steps in the sorting above. So far, I've managed to
> solve the same list using the code below:
> 
> def sorting_function(k):
>     steps_count = 0
>     for j in range(len(k)):
>         for i in range(len(k)-1):
>             if k[i] > k[i+1]:
>                 k[i], k[i+1] = k[i+1], k[i]
>             steps_count = steps_count + 1
>             print(k)
>     print(steps_count)
> 
> k = [4,3,2,1]
> sorting_function(k)
> 
> And got the following output:
> [3, 4, 2, 1]
> [3, 2, 4, 1]
> [3, 2, 1, 4]
> [2, 3, 1, 4]
> [2, 1, 3, 4]
> [2, 1, 3, 4]
> [1, 2, 3, 4]
> [1, 2, 3, 4]
> [1, 2, 3, 4]
> [1, 2, 3, 4]
> [1, 2, 3, 4]
> [1, 2, 3, 4]
> 12
> 
> However, when I tested the code using a different list e.g. [1, 2, 3, 4],
> the output is:
> [1, 2, 3, 4]
> [1, 2, 3, 4]
> [1, 2, 3, 4]
> [1, 2, 3, 4]
> [1, 2, 3, 4]
> [1, 2, 3, 4]
> [1, 2, 3, 4]
> [1, 2, 3, 4]
> [1, 2, 3, 4]
> [1, 2, 3, 4]
> [1, 2, 3, 4]
> [1, 2, 3, 4]
> 12
> 
> The output should only have a total of 4 steps. What's wrong with my code?

This is a form of the "Bubble Sort". You will find plenty of coverage on
the web, eg https://duckduckgo.com/?q=bubble+sort

Per your marvellously-helpful illustration, looking at the first line
you will notice that the effect is to move the largest value (4) out to
the end of the list. How about if the data was [ 2, 3, 4, 1 ], would the
4 still make it to the end?

So, can it be said that the effect of the first time through the
outer-loop, is that the largest element will always be in its correct
place, wrt the final sorted list?

That realised, let's examine what happens the second time around the
outer-loop. It will (eventually) pick up the 3 (no matter where the 3
started in the original_list) and move it to the second-last position.
At that point, we know the 4 is in-position AND that the 3 has already
been shown to be smaller than the 4 (and thus won't bubble/swap position
with it), so what is the point of that comparison?

Thus, the inner loop can be shortened by one, every time an element is
moved to its final position. Perhaps something like:

for i in range( len( k ) - 1 - j):

This will have the effect of reducing the steps_count - slightly.

With k == 4, the compute-time is negligible. If however the list were
massively-long, then you may like to consider computing len( k ) - 1
only once per outer loop (cf every time). Also compute i + 1 once (cf
three times per inner loop. The code to 'swap' is well written! Do you
know about: steps_count += 1? Another nit-pick is that you'll notice
that in order to discuss the topic sensibly, English words are being
used - the meaning of i, j, and k is less meaningful!


Beyond that short-cut/improvement, there's little that can be done. The
algorithm must consider every element on the line (excepting as-above),
ie just because two 'neighbors' don't swap early along the line, doesn't
mean that the inner-loop can "break", eg

[ 2, 1, 4, 3 ]

The 2 and the 1 must swap, but the 2 and the 4 must not. At this point,
you can't pack-up and go home, because the 4 must be compared against
the 3 because that will realise a swap!

So, the Bubble Sort is a beautiful introductory algorithm and one that
can be 'seen' as it happens (particularly with diagrams such as yours).
However, it is very laborious and thus inefficient. The way to speed-up
sorting is to choose a better algorithm.
(one of which is to use Python's sort() - but should we assume it may
not be used?)


Just tossing-around an idea:

Another way to consider the bubble sort, would be to 'bubble' the
smallest number to the 'left'/top (instead of the largest number to the
right/bottom), then the next smallest, etc.

So, using the min(), index(), and pop() or remove() list methods
(functions), could one:
- take the original_list as input, and create an empty destination_list
- find the min() value and append() it to the destination_list
- index() that value in the original_list and pop() it, or perhaps just
remove() it (?speed comparison)
- rinse and repeat (the latter two steps) until the original_list is
"exhausted".

This may realise a speed advantage over the above, because it is
processing with (efficient) built-in methods, and eschewing complicated
and multiple index-manipulations. Python does the work of gradually
reducing the length of one list and increasing that of the output, with
each pass.

(apologies, no time to code it myself - if you do, will be interested to
hear your conclusions)

Web.Refs:
List functions:
https://docs.python.org/3/library/stdtypes.html?highlight=list%20method#sequence-types-list-tuple-range
Python's timer function: https://docs.python.org/3/library/timeit.html
-- 
Regards,
=dn