3.1.5.2 Sorting simple lists - the bubble sort algorithm
Sorting a list
How many passes do we need to sort the entire list?
We solve this issue in the following way: we introduce another variable; its task is to observe if any swap has been done during the pass or not; if there is no swap, then the list is already sorted, and nothing more has to be done. We create a variable named
swapped, and we assign a value of False to it, to indicate that there are no swaps. Otherwise, it will be assigned True.myList = [8, 10, 6, 2, 4] # list to sort
for i in range(len(myList) - 1): # we need (5 - 1) comparisons
if myList[i] > myList[i + 1]: # compare adjacent elements
myList[i], myList[i + 1] = myList[i + 1], myList[i] # if we end up here it means that we have to swap the elements
You should be able to read and understand this program without any problems:
myList = [8, 10, 6, 2, 4] # list to sort
swapped = True # it's a little fake - we need it to enter the while loop
while swapped:
swapped = False # no swaps so far
for i in range(len(myList) - 1):
if myList[i] > myList[i + 1]:
swapped = True # swap occured!
myList[i], myList[i + 1] = myList[i + 1], myList[i]
print(myList)
Run the program and test it.
Comments
Post a Comment