# Sorts a sequence in ascending order using the bubble sort algorithm.
def bubbleSort( theSeq ):
n = len( theSeq )
# Perform n-1 bubble operations on the sequence
for i in range( n - 1 ) :
# Bubble the largest item to the end.
for j in range( n - i - 1 ) :
if theSeq[ j ] > theSeq[ j + 1 ] : # swap the j and j+1 items.
tmp = theSeq[ j ]
theSeq[ j ] = theSeq[ j + 1 ]
theSeq[ j + 1 ] = tmp
return theSeq
# Improved bubblesort that stops when no swap takes place
def bubbleSortOpt( theSeq ):
n = len( theSeq )
# Perform n-1 bubble operations on the sequence
for i in range( n - 1 ) :
swapped = False
# Bubble the largest item to the end.
for j in range( n - i - 1 ) :
if theSeq[ j ] > theSeq[ j + 1 ] : # swap the j and j+1 items.
swapped = True
tmp = theSeq[ j ]
theSeq[ j ] = theSeq[ j + 1 ]
theSeq[ j + 1 ] = tmp
if not swapped:
break # leave the for loop
return theSeq