Bubble Sort Algorithm

The philosophy of Bubble Sort is to look at adjacent elements in the array and put them in order. We will look at the first two elements, swap them if necessary; then look at the second and third elements, swapping if necessary; then look at the third and the fourth and so on. After one pass through the array, the largest item will be at the end of the array (prove this to yourself). Similarly, if we make another complete pass through the array, the second largest item will be in position. If we make n such passes, all of the array will be sorted.

As with many of our algorithms, Bubble Sort creates a sorted portion of the array (at the end) and an unsorted portion. We can improve its run-time slightly (not asymptotically), by making each pass only go through the unsorted portion of the array.

for i = n down to 1
    for j = 1 to i-1
	if A[j] < A[j+1]
	    swap(A,i,j)

The inner for loop (using j as the loop variable) is walking through the array looking at sequential entries and swapping them if they are out of order. First it will check the first and the second entries; then the second and the third; and so on. The main effect of that loop is that the largest element will end up in the last space that loop examines.

The outer loop makes the inner loop happen n times. The first time, the largest number will be correctly positioned; the second time the next largest number will be correctly positioned and so on until the smallest number is correctly positioned.

The i and j variables are colored to match their colors in the animation. You will see the values these variables take on near the top of the animation applet.