# 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