Sorting data (i.e. placing data into some particular order, such as ascending or descending) is one of the most important computing applications. Python lists provide a sort meth- od. In this exercise, readers implement their own sorting function, using the bubble-sort method. In the bubble sort (or sinking sort), the smaller values gradually “bubble” their way upward to the top of the

Question

list like air bubbles rising in water, while the larger values sink to the bottom of the list. The process that compares each adjacent pair of elements in a list in turn and swaps the elements if the second element is less than the first element is called a pass. The technique makes several passes through the list. On each pass, successive pairs of elements are compared. If a pair is in increasing order, bubble sort leaves the values as they are. If a pair is in decreasing order, their values are swapped in the list. After the first pass, the largest value is guaranteed to sink to the highest index of a list. After the sec- ond pass, the second largest value is guaranteed to sink to the second highest index of a list, and so on. Write a program that uses function bubbleSort to sort the items in a list.

What will be an ideal response?

Answer 1

```
# Bubble sort.

import random

# implements bubble sort on a list
def bubbleSort( bList ):

# make len( bList ) passes
for item in range( len( bList ) - 1 ):

# make one pass through len( bList ) - 1 elements
for index in range( len( bList ) - 1 ):

# if this element is greater than next element,
# swap elements.
if bList[ index ] > bList[ index + 1 ]:
bList[ index ], bList[ index + 1 ] = \
bList[ index + 1 ], bList[ index ]

# main program
bubbleSortList = []

# insert 10 random numbers in the list
for i in range( 1, 11 ):
bubbleSortList.append( random.randrange( 1, 100 ) )

# print unsorted list
print "List before bubble sort:",

for item in bubbleSortList:
print "%2d" % item,

print

# pass list to function bubbleSort (function modifies list)
bubbleSort( bubbleSortList )

# print sorted list
print "List after bubble sort: ",

for item in bubbleSortList:
print "%2d" % item,

print
```
List before bubble sort: 46 29 6 6 95 92 43 73 69 2
List after bubble sort: 2 6 6 29 43 46 69 73 92 95