3.2 BUBBLE SORT 63
correct position to insert this new element. You should notice that for
unique keys the standard binary search would always return a failure. So for
this problem, assume a revised binary search that returns the location at
which this key belongs.
a. What is the worst-case analysis of this new insertion sort?
b. What is the average-case analysis of this new insertion sort?
3.2 Bubble Sort
The second sort we will consider is bubble sort. The general idea is to allow
smaller values to move toward the top of the list while larger values move to
the bottom. There are a number of varieties of bubble sort. This section will
deal with one of these, and the others will be left as exercises.
The bubble sort algorithm makes a number of passes through the list of ele-
ments. On each pass it compares adjacent element values. If they are out of
order, they are swapped. We start each of the passes at the beginning of the list
and compare the elements in locations 1 and 2, then the elements in locations
2 and 3, then 3 and 4, and so on, swapping those that are out of order. On the
first pass, once the algorithm reaches the largest element, it will be swapped
with all of the remaining elements, moving it to the end of the list after the
first pass. The second pass, therefore, no longer needs to look at the last ele-
ment in the list. The second pass will move the second largest element down
the list until it is in the second to last location. The process continues with each
additional pass moving one more of the larger values down in the list. During
all of this, the smaller values are also moving toward the front of the list. If on
any pass there are no swaps, all of the elements are now in order and the algo-
rithm can stop. It should be noted that each pass has the potential of moving a
number of the elements closer to their final position, even though only the
largest element on that pass is guaranteed to wind up in its final location.
The following algorithm carries out this bubble sort version:
BubbleSort( list, N )
list the elements to be put into order
N the number of elements in the list
numberOfPairs = N
swappedElements = true
