HCI 8. Searching and Sorting Algorithms (2022)

Hwa Chong Institution H2 Computing 1 8 Searching and Sorting Algorithms Learning Outcome In the last chapter, we learnt t o search and sort a list using the methods provided in Python. Here, we will look closer into the various algorithms, explaini ng how the search and sort are done behind the scene and how efficient the algorithms are. 8.1 Searching Algorithms A searching algorithm intends to find a particular element in a list. This targeted element may not exist in the list, may appear once or multiple times. We call this targeted element the key. 8.1.1 Linear Search As the name implies, linear search basically searches the items in the list one-by-one. The function LinearSearch requires two parameters: the list and the key. The algorithms begins at index 0, scans every element in the list until the key is found or the list is exhausted. If the key is found, the function returns the index of the matched item in the list; otherwise, the value −1 is returned. Here are two examples for illustration. A: 8 3 6 2 6 1. key = 6 Search the list from the beginning, returning the index of the first occurrence of element 6. key = 6 A[0] A[1] A[2] A[3] A[4] return value = 2 8 3 6 2 6 Fundamental Algorithms  Implement sort algorithms: insertion sort, bubble sort, quicksort, merge sort  Use examples to explain sort algorithms  Implement search algorithms: linear search, binary search, hash table search  Use examples to explain search algorithms  Compare and describe the efficiencies of the sort and search al gorithms using Big-O notation for time complexity (worst case). Exclude: space complexity Implementing Algorithms  Implement sort programs: insertion sort, bubble sort, quicksort, merge sort   Implement search programs: linear search, binary search, hash table search

Hwa Chong Institution H2 Computing 2 def LinearSearch (A, key): #Search the list A for a match with key #Return the position of the key if found, or -1 otherwise. pos = 0 # start position to search found = False while ( not found and pos < len(A) ): if A[pos] == key: found = True else: pos = pos + 1 if found: # return index of matching item return pos else: # search failed, return -1 return -1 2. key = 9 , start = 0, n = 5. Start at the first element and search the list for the number 9. Since it is not found, return the value −1. key = 9 n = 5 A[0] A[1] A[2] A[3] A[4] return value = −1 Linear Search Implementation 8.1.2 Binary Search The linear se