#---------------------------------------------------
# Function name:  bubbleSort
#   Input:      an array, list
#   Output:     the sorted array, list
#   Note:       For simplicity, this version of bubble sort performs exactly (n-1) passes.
#                   It does not end early if data is already ordered.

def bubbleSort (list):
	n = len(list)		# number of elements in list
	passNum = 1		# start with the 1st pass

	cmps = 0		# number of comparisons performed
	swaps = 0		# number of swaps performed

	while (passNum < n):
		print "passNum = ", passNum
		print "    ", list
		index = 0

		while (index < (n-passNum)):
			print "  index =", index

			if (list[index] > list[index+1]):
				temp = list[index+1]
				list[index+1] = list[index]
				list[index] = temp
				swaps = swaps + 1
				print "    ", students

			cmps = cmps + 1
			index = index + 1

		print "    ", students
		passNum = passNum + 1

	print
	print "In sorting the data, the Bubble Sort performed", cmps, "comparisons and", swaps, "swaps."
	print

	return list


#---------------------------------------------------
# Main program:

students = ["Steve", "Garrett", "Danyu", "Krystal", "Chau", "Winnie", "Peter"]

print
print "Initial order in list is:"
print "   ", students			# display initial order in list
print

students = bubbleSort(students)		# sort 'students' list

print "Final order in list is:"
print "   ", students			# display final order in list
print