The Bubble Sort
Bubble sort is a simple sorting algorithm. This sorting algorithm is comparisonbased algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order. This algorithm is not suitable for large data sets as its average and worst case complexity are of ?(n2) where n is the number of items.
The bubble sort makes multiple passes through a list. It compares adjacent items and exchanges those that are out of order. Each pass through the list places the next largest value in its proper place. In essence, each item “bubbles” up to the location where it belongs.
Figure 1 shows the first pass of a bubble sort. The shaded items are being compared to see if they are out of order. If there are n items in the list, then there are n−1
pairs of items that need to be compared on the first pass. It is important to note that once the largest value in the list is part of a pair, it will continually be moved along until the pass is complete.
At the start of the second pass, the largest value is now in place. There are n−1
items left to sort, meaning that there will be n−2 pairs. Since each pass places the next largest value in place, the total number of passes necessary will be n−1. After completing the n−1
passes, the smallest item must be in the correct position with no further processing required. ActiveCode 1 shows the complete bubbleSort
function. It takes the list as a parameter, and modifies it by exchanging items as necessary.
The exchange operation, sometimes called a “swap,” is slightly different in Python than in most other programming languages. Typically, swapping two elements in a list requires a temporary storage location (an additional memory location). A code fragment such as
temp = alist[i] alist[i] = alist[j] alist[j] = temp
will exchange the ith and jth items in the list. Without the temporary storage, one of the values would be overwritten.
In Python, it is possible to perform simultaneous assignment. The statement a,b=b,a
will result in two assignment statements being done at the same time (see Figure 2). Using simultaneous assignment, the exchange operation can be done in one statement.
Lines 57 in ActiveCode 1 perform the exchange of the i
and (i+1)th
items using the three–step procedure described earlier. Note that we could also have used the simultaneous assignment to swap the items.
The following activecode example shows the complete bubbleSort
function working on the list shown above.
def bubbleSort(alist):
for passnum in range(len(alist)1,0,1):
for i in range(passnum):
if alist[i]>alist[i+1]:
temp = alist[i]
alist[i] = alist[i+1]
alist[i+1] = temp
alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)
0 comments Comments
Leave a comment
 Basic Data Structures

Objectives

What Are Linear Structures?

What is a Stack?

The Stack Abstract Data Type

Implementing a Stack in Python

What Is a Queue?

The Queue Abstract Data Type

Implementing a Queue in Python

What Is a Deque?

The Deque Abstract Data Type

Implementing a Deque in Python

Lists

The Unordered List Abstract Data Type

Implementing an Unordered List: Linked Lists

The Ordered List Abstract Data Type

Implementing an Ordered List

Vocabulary and Definitions

 Sorting and Searching
 Trees and Tree Algorithms
 Graphs and Graph Algorithms