Searching and Sorting Algorithms
The Sequential Search
Since index values in a list are ordered, it is possible to visit them in sequence. This process gives rise to searching
technique, the sequential search.
Starting at the first item
move from item to item, until we either find what we are looking for or run out of items.
If we run out of items, we have discovered that the item we were searching for was not present.
The function needs the list and the item we are looking for and returns a boolean value as to whether it is present.
The boolean variable found is initialized to False and is assigned the value True if we discover the item in the list.
def sequentialSearch(alist, item):
pos = …………………………………..
found = False
while pos < len(alist) and not found:
if alist[pos] == ……………………………………:
found = ………………………………………………
else:
pos = ……………………………………..
return ……………………………………….
testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 3))
print(sequentialSearch(testlist, 13))
The Bubble Sort
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.
Example 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. Once the
largest value in the list is part of a pair, it will continually be moved along until the pass is complete.
First Pass
54 26 93 17 77 31 44 55 20 Excahnge
Excahnge
No Excahnge
Excahnge
Excahnge
Excahnge
Excahnge
Excahnge
93 93 in place after 1st pass
1 Prepared by Sisira Palihakkara
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+1] = ……………………………….
alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)
2 Prepared by Sisira Palihakkara