[Tutor] Sorting a list manually

[Dennis Lee Bieber]

On Thu, 12 Aug 2021 15:23:40 +0800, nzbz xx <nzbzxx at gmail.com> declaimed
the following:

>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:

	Ancient Bubble-Sort...

>
>def sorting_function(k):
>    steps_count = 0
>    for j in range(len(k)):
>        for i in range(len(k)-1):

	j runs 4 iterations (presuming a four element input list), i runs 3
iterations, 4 * 3 => 12 total passes.

	To reduce the passes, you have to consider that, once the first pass
has completed, the largest value is at the end of the list. Subsequent
passes do not need to look at that item. So the second pass only looks at
list[0:3], after that pass, the two largest values have been sorted, so you
now only have to look at list[0:2], etc.

	That's the first optimization -- but still runs a full count of passes
regardless of the data.


def bubble_sort(aList):
    steps_count = 0
    for j in reversed(range(len(aList))):
        for i in range(j):
            if aList[i] > aList[i+1]:
                aList[i], aList[i+1] = aList[i+1], aList[i]
            steps_count += 1
            print(aList)
    print(steps_count)
    return aList

bubble_sort([4, 3, 2, 1])

bubble_sort([1, 2, 3, 4])


[3, 4, 2, 1]
[3, 2, 4, 1]
[3, 2, 1, 4]
[2, 3, 1, 4]
[2, 1, 3, 4]
[1, 2, 3, 4]
6
[1, 2, 3, 4]
[1, 2, 3, 4]
[1, 2, 3, 4]
[1, 2, 3, 4]
[1, 2, 3, 4]
[1, 2, 3, 4]
6

	The next optimization is to detect if a swap took place during the
pass; if no swap, list is in order, exit.


def bubble_sort(aList):
    steps_count = 0
    for j in reversed(range(len(aList))):
        swap = False
        for i in range(j):
            if aList[i] > aList[i+1]:
                aList[i], aList[i+1] = aList[i+1], aList[i]
                swap = True
            steps_count += 1
            print(aList)
            if not swap: break
        if not swap: break
    print(steps_count)
    return aList

bubble_sort([4, 3, 2, 1])

bubble_sort([1, 2, 3, 4])


[3, 4, 2, 1]
[3, 2, 4, 1]
[3, 2, 1, 4]
[2, 3, 1, 4]
[2, 1, 3, 4]
[1, 2, 3, 4]
6
[1, 2, 3, 4]
1


	For a possibly cleaner version (I haven't checked if it exits early --
adding instrumentation output I'd leave up to you) look at
https://www.geeksforgeeks.org/bubble-sort/  The text states that it needs
one pass with no swap to know it is done -- but I don't see any such test
in the solutions



-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
	wlfraed at ix.netcom.com    http://wlfraed.microdiversity.freeddns.org/