AS Computer Science
Algorithms and programs (4)
Key terms Insertion sort Binary Search
Term Definition Example: insertion sort 15, 10, 20, 1, 5 • Compare search item x with the middle
element of the sorted array.
loop for i = 1 (second element of the array) to 4
Sorting An algorithm for arranging the data
(last element of the array) • If x matches with middle element, return mid
algorithm in ascending or descending order to
index.
make searching easier. i = 1. 10 is smaller than 15, move 15 and insert
10 before 15 = 10, 15, 20, 1, 1 • Else If x is greater than the mid element,
Searching An algorithm used to look for a then x lies in right half subarray after the mid
i = 2. 20 will remain at its position as all
algorithm specific data element in a dataset. element. So, recur for right half.
elements are smaller = 10, 15, 20, 1, 5
• Else (x is smaller) recur for the left half.
i = 3. 1 will move to the beginning and all
Example Bubble sort. other elements from 10 to 20 will move Binary search is an efficient algorithm
one position ahead of their current for finding an item from a sorted list of
First Pass: position = 1, 10, 15, 20, 5 items.
(7 1 5 3 9) –> (1 7 5 3 9). Swap since 7 > 1 i = 4. 5 will move and be inserted after 1, and Find 52
(1 7 5 3 9) –> (1 5 7 3 9), Swap since 7 > 5 elements from 10 to 20 will move one
position ahead of their current position. 7 10 12 23 41 52 60 77 88 89
(1 5 7 3 9) –> (1 5 3 7 9), Swap since 7 > 3 = 1, 5, 10, 15, 20 0 1 2 3 4 5 6 7 8 9
(1 5 3 7 9) –> (1 5 3 7 9), No swap since 9 > 7 52 > 41 (discard lower half)
Second Pass: 7 10 12 23 41 52 60 77 88 89
Linear Search
L=0 1 2 3 M=4 5 6 7 8 H=9
(1 5 3 7 9) –> (1 5 3 7 9)
52 < 77 (discard upper half)
(1 5 3 7 9) –> (1 3 5 7 9), Swap since 5 > 3 Each item in the data set is compared with the
search condition in sequence until the item is 7 10 12 23 41 52 60 77 88 89
(1 3 5 7 9) –> (1 3 5 7 9) found, or the end of the data set is reached. 0 1 2 3 4 L=5 6 M=7 8 H=9
Third Pass:
(1 3 5 7 9) –> (1 3 5 7 9) 52 (found at location 5)
(1 3 5 7 9) –> (1 3 5 7 9) Find 20
The array is sorted, but (1 3 5 7 9) –> (1 3 5 7 9) 7 10 12 23 41 52 60 77 88 89
algorithm needs one (1 3 5 7 9) –> (1 3 5 7 9) 0 1 2 3 4 L&M=5 H=6 7 8 9
whole pass without (1 3 5 7 9) –> (1 3 5 7 9)
any swap to know it is 10 80 30 50 70 20 90 40
sorted. 1 2 3 4 5 6 7 8 Algorithm
Example optimised Implementation Declare binarySearch(dataList, searchItem):
Algorithm if len(dataList) = 0
1 Declare BubbleSort(bubbleList): return False
2 exchanges = True else
1 Declare linearSearch(dataList, searchItem) midpoint = low + (high - low)/2
3 passnum = len(bubbleList)-1 2 end if
4 while passnum > 0 and exchanges = True 3 position = 0 if dataList[midpoint]= searchItem
5 exchanges = False 4 found = false return True
6 for i = 1 to n 5 else:
7 if bubbleList[i]>bubbleList[i+1]: 6 while position < len(dataList) and found = false if item < dataList[midpoint]:
7 if dataList[position] = searchItem then return binarySearch(dataList[low:midpoint],searchIt
8 exchanges = True
8 found = true else:
9 temp = bubbleList[i] return binarySearch(dataList[midpoint+1:high],searchIte
9 else
10 bubbleList[i] = bubbleList[i+1] end if
10 position = position + 1
11 bubbleList[i+1] = temp end if
11 end if
12 end if 12 end while
13 next i
14 passnum = passnum-1
15 end while
16 end Subroutine
17
18 bubbleList=[20,30,40,90,50,60,70,80,100,110]
19
20 BubbleSort(bubbleList)
21 print(bubbleList)
