02 Chapter 9 - Searching and Sorting Algorithms

Chapter 9: Searching and Sorting Algorithms

Chapter 9: Searching and Sorting Algorithms

Searching algorithm

• To find a particular / target element (key) in a list

LinearSearch: (i.e. sequential search)

• Searches items in the list one-by one
• Requires 2 parameters: list and key
• Begins at index 0, scans every element in list until key is found or list is exhausted
• If key found: function returns index of matched item in list
• Otherwise: return value -1
• E.g.

def LinearSearch(A, key): # search list A for a match with key # return position of 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 pos # return index of matching item else: # search failed return -1
FUNCTION LinearSearch(list, value): FOR INDEX ← 1 TO LEN(list) // LEN(list) returns length of list IF list[index] == value THEN RETURN index // location ENDIF ENDFOR RETURN -1 ENDFUNCTION

Binary Search

• From middle of ordered / sorted list, look for quick match of key with the midpoint value
• If fail to find a match: look at relative size of key & midpoint value, then move to the lower or upper half of the list
• Shortens search time ⇒ fewer comparisons than linear search
• Indices at ends of the list are low = 0 and high = n-1, where n = no. of elements in list

Compute index of array’s midpoint mid = (low + high) / 2 Compare value at this midpoint with the key If match occurs, return the index mid to locate the key If (A[mid] == key) return mid If key < A[mid], key must lie within the lower range (left half) since list is ordered. New boundaries are low & high = mid - 1 Search Lower Range, index from low to mid - 1 If key > A[mid], key must lie within the upper range (right half) since list is ordered. New boundaries are low = mid + 1 & high Search Upper Range, index from mid + 1 to high Algorithm refines location of a match by halving the length of the interval in which key can exist and then execute the same search algorithm on the smaller sublist Eventually, if key is not in list, low exceeds high and algorithm returns the failure indicator of -1 (match not found) E.g. Key < A[mid] ⇒ high = mid - 1 = 7 ⇒ low exceeds high ⇒ return failure indicator of -1 (match not found)

def BinarySearch(A, key): # search ordered list A for a match with key # return position of key if found, or -1 otherwise found = False # initialisation low = 0 high = len(A) - 1 while (not found) and (low <= high): mid = (low + high) // 2 # mid index of the sublist # e.g. (4+5) // 2 = 4 if key == A[mid]: # have a match found = True elif key < A[mid]: # go to lower sublist high = mid - 1 else # or if key > A[mid]: # go to upper sublist low = mid + 1 if found: # return index of matching item return mid else: # i.e. low > high return -1 # search failed, return -1
def recursiveBinarySearch(A, key): print(A) if len(A) <= 0: return False else: mid = len(A) // 2 print(mid, A[mid]) if key == A[mid]: return True elif key < A[mid]: return recursiveBinarySearch(A[:mid], key) else: return recursiveBinarySearch(A[mid+1:], key)
def recursiveBinarySearch2(A, L, H, key): if L > H: return False else: mid = (L + H) // 2 if key == A[mid]: return True elif key < A[mid]: return recursiveBinarySearch(A, L, mid-1, key) else: return recursiveBinarySearch(A, mid+1, H, key)

Hash Table Search

• Location of each item is determined by a hash function of the item itself
• ⇒ Hash table search is made at the designated location of the item
• ⇒ Less comparisons (not trial-and-error comparisons)
• Uses a hash function that converts a search key to an integer value that is used as an index in a hash table (i.e. hash function maps a big number or string to a small integer that can be used as index in hash table)

Hash function

• E.g. Up to 25 integers in the range 0 through 999 are to be stored in a hash table:
• Implement hash table as an integer array table in which each array element is initialised with some dummy value, e.g. -1
• Use each integer i in the set as an index ⇒ i.e. store i in table[i]
• h(i) = i ⇒ hash function h determines location of an item i in the hash table
• To determine if an integer number has been stored, check if table[number] = number
• Only need to examine 1 location ⇒ very time efficient
• But may have unused locations ⇒ may not be space efficient (a lot of available space wasted)
• Properties of good hash functions / algorithms
• Uniformity: distribute keys uniformly across hash table, minimise no. of collisions, ensure search operation is fast and efficient
• Deterministic: the same key should always generate the same hash ⇒ store and retrieve key-value pairs in hash table consistently
• Fast computation: generate hash values quickly ⇒ fast insertion, deletion, & search operations on hash table
• E.g. To improve space utilisation, use an array table with capacity 25
• h(i) = i modulo 25

def h(i): return (i%25) # division by 25 method # e.g. integer 52 is stored in table[2], since h(52) = 52%25 = 2

• Always produces an integer in the range 0 through 24

Collision strategies

• Collisions may occur ⇒ some locations already occupied by other values
• 2 or more keys in the search map to the same location in the hash table
• E.g. all integers of the form 25k+2 hash to location 2
• [1] Linear probing (linear probe open addressing)
• A linear search of the table begins at the location where a collision occurs and continues until an empty slot is found in which the item can be stored
• E.g. 77 collides with 52 at location 2 ⇒ put 77 in position 3 (table[3])
• E.g. to insert 102, follow the probe sequence consisting of locations 2,3,4,5, and find the first available location ⇒ store 102 in table[5]
• If search reaches bottom of table, continue at the first location (e.g. for 123)
• 
• Note: if an insertion causes load factor of the table (its fraction of occupied cells) to grow above the threshold (i.e. >1)¹, the whole table may be replaced by a new table, larger by a constant factor, with a new hash function
• Capacity of hash table = size of array
• Load factor = no. of slots in table or no. of elements or keys stored in hash table divided by capacity
• Lazy deletion of item: mark element as deleted, rather than erasing it entirely
• Deleted locations are treated as empty when inserting, and as occupied during a search
• Hash Table Search with Linear probing
• To determine if a specified value is in the hash table, apply hash function to compute the position at which this value should be found
• Case 1: location is empty ⇒ value is not in table
• Case 2: location contains specified value ⇒ search is successful
• Case 3: location contains a value other than the one for which we are searching ⇒ collisions were resolved ⇒ begin a “circular” linear search at this location and continue until either (i) item is found, or (ii) reached empty location or starting location ⇒ item not in table
• In linear probe scheme, when collisions occur, colliding values are stored in locations that should be reserved for items that hash directly to these locations
• ⇒ Makes subsequent collisions more likely, thus compounding the problem
• [2] Chaining [with Separate Lists]
• Uses a hash table that is an array of linked lists that store the items
• Slot holds a reference to a collection / chain of items
• Allows many items to exist at the same location in the hash table (even if collision, item still placed in proper slot of hash table)
• E.g. using an array table of 26 linked list to store a collection of names
• Initially empty
• Simple hash function h(name) = ord(name[0]) - ord(‘A’)
• I.e. h(name) = 0 if name [0] is ‘A’,
  h(name) = 1 if name[0] is ‘B’,
  h(name) = 25 if name[0] is ‘Z’, etc
• E.g. “Adams” and “Dorry” are stored in nodes pointed to by table[0] and table[3]
• When collision occurs, insert new item into the appropriate linked list
• Hash Table Search with Chaining

Chaining	Linear Probing
Only items that hash to the same table location are searched ⇒ generally faster
Chaining with separate lists: entries in hash table are dynamically allocated List size is limited only by the amount of memory ⇒ Preferred for hashing Disadvantage: space required to allocate the additional node pointer field	Assumes a fixed-length table

• Behaviour of hash function affects frequency of collisions
• Preceding hash function: some letters occur much more frequently than others as first letters of names ⇒ not good choice
• E.g. Linked list of names beginning with ‘T’ tends to be much longer than containing names that begin with ‘Z’ ⇒ clustering effect results in longer search times for T-names than Z-names
• “Average” of first and last letters in the name: distribute names more uniformly throughout hash table ⇒ better hash function
• h(name) = (ord(first letter) + ord(last letter)) / 2
• OR use “average” of all letters
• But cannot be so complex that the time required to evaluate it makes the search time unacceptable

Sorting algorithms (ordering of items in a list, e.g. to allow quick access to a work)

• Ascending order:
• Descending order:
• E.g. exchange position of 2 items (at positions i and j) in a list of integers

def swap(A, i, j): # use all 3 lines in pseudocode; python can use 1 line temp = A[i] A[i] = A[j] A[j] = temp # one-line alternative: A[i], A[j] = A[j], A[i]

Bubble Sort

• Requires up to (i.e. max) (n-1) passes, for an array A with n elements
• For each pass, compare adjacent elements and exchange their values when the 1st element is greater than the 2nd element
• At end of each pass, the largest element has “bubbled up” to the end of the current sublist
• E.g. After pass 0 (1st pass) completed, the tail of the list (A[n-1]) is sorted and the front of the list remains unordered
• lastExchangeIndex: Maintain a record of the last index that is involved in an exchange
• Set to 0 at the start of each pass
• Pass 0 compares adjacent elements (A[0], A[1]), (A[1], A[2]), … . , (A[n−2], A[n−1])
• For each pair (A[j], A[j+1]), exchange values if A[j] > A[j+1] and update lastExchangeIndex to j
• At end of each pass, the largest element is in A[n-1] and the value lastExchangeIndex indicates that all elements in the tail of the list from A[lastExchangeIndex + 1] to A[n-1] are in sorted order
• For subsequent passes, compare adjacent elements in the sublist from A[0] to A[lastExchangeIndex]. Process terminates when lastExchangeIndex = 0.
• E.g. 5-element array A = 50, 20, 40, 75, 35

Pass 0 (1st pass): lastExchangeIndex != 0, so process continues Note: largest number moves to the back of list
Pass 1 (2nd pass): Scan sublist of elements A[0] to A[lastExchangeIndex] = A[3] new value of lastExchangeIndex = 2, so process continues
Pass 2 (3rd pass): Scan sublist A[0] to A[lastExchangeIndex] = A[2]
Pass 3 (4th pass): Scan sublist A[0] to A[lastExchangeIndex] = A[1] Single comparison of 20 and 35 leads to no exchanges lastExchangeIndex = 0 ⇒ process terminates

def bubbleSort(A): i = len(A) - 1 # index of last element in sublist while i > 0: # continue until no exchanges are made lastExchangeIndex = 0 # scan sublist A[0] to A[i] for j in range(i): # i.e. 0, 1, 2, …(i-1) # exchange a pair and update lastExchangeIndex if A[j] > A[j+1]: swap (A, j, j+1) lastExchangeIndex = j # set i to index of the last exchange # continue sorting the sublist A[0] to A[i] i = lastExchangeIndex

# without using lastExchangeIndex def bubblesort(A): for j in range(len(A)): for i in range(len(A)-1): if A[i] > A[i+1]: A[i], A[i+1] = A[i+1], A[i] return (A)

Insertion Sort

• Similar to paper-shuffling process that orders a list of names
• Put each name on a card, rearrange card alphabetically by sliding a card forward in the stack until it finds the correct location
• ⇒ cards at front of stack are sorted, those at rear of stack are waiting to be processed
• E.g.
• E.g. list A of size n (n integer elements)
• Pass i (1 <= i <= n-1): Sublist already in ascending order
• Path assigns A[i] to the list
• Let A[i] be the target and move down the list, compare the target with items A[i-1], A[i-2], etc
• Stop the scan at first element A[j] that is <= target or at the beginning of the list (j = 0)
• Moving down the list, slide each element to the right (A[j] = A[j-1])
• When correct location for A[i] found, insert it at location j

def insertionSort(A, n): for i in range(1, n): # i identifies sublist A[0] to A[i] # index j scans down list from A[i-1] # look for correct position to locate target target = A[i] j = i # locate insertion point by scanning downwards # as long as target < A[j-1] and have not encountered beginning of list while (j > 0) and (target < A[j-1]): # shift elements up to make room for insertion A[j] = A[j-1] j = j - 1 # location found, insert target A[j] = target

Quick sort (in-place algorithm shown here)

• Fastest sorting algorithm
• Similar to sorting a large stack of papers by name: split papers into 2 piles with some pivot character (e.g. K) separating the list
• All names <= K go in 1 pile, the rest go into 2nd pile
• Take each pile, split into 2 parts (e.g. partition points ‘F’ and ‘R’)
• Continue to subdivide piles into smaller stacks
• 
• Uses partition approach: determine pivot value to split list into 2 parts, then search elements into parts within the list
• Summary (adapted from ChatGPT)
• Goal: rearrange to [ <= pivot | pivot | >= pivot ]
• Set pivot to middle element, move pivot to front
• A[mid], A[low] = A[low], A[mid]
• left = low + 1 ⇒ scans from left, stops when found WRONG big value (> pivot)
• right = high ⇒ scans from right, stops when found WRONG small value (< pivot)
• Wrong values of right & left should be on the left & right respectively ⇒ swap right and left
• If left > right: no more misplaced elements, everything is partitioned
• Swap pivot with right, because pivot should be back to the “middle” of <= pivot and >= pivot
• A[right], A[low] (pivot) = A[low], A[right]
• Return right
• Scanning phase
• Scan entire range of elements in list A[0] to A[9]
• Range extends from low = 0 to high = 9, mid (middle index) = 4
• 1st pivot value: A[mid] = 550
• Algorithm separates elements of A into sublists $S_{low}$ and $S_{high}$
• $S_{low}$: lower sublist (elements <= pivot)
• $S_{high}$: higher sublist (elements > pivot)
• Pivot ultimately ends up in $S_{low}$ ⇒ thus temporarily move it to the low end of the range, and exchange its value with A[0] (A[low])
• So can scan sublist A[1] to A[9] using 2 indices left and right
• left: initially set at index 1 (low + 1) ⇒ locates elements for sublist $S_{low}$
• right: initially set at index 9 (high) ⇒ locates elements for sublist $S_{high}$
• Goal of pass: identify elements in each of the sublists
• 
• Index left moves up the list, index right moves down the list
• Move left forward to look for element A[left] that > pivot
• Scan stops
• Prepare to relocate element to upper sublist
• Before relocation, move index right downward in list, identify element <= pivot
• ⇒ identified 2 elements in wrong sublists (misplaced partners), exchange them
• swap(A, left, right)
• Process continues until left and right pass each other with right = 5, left = 6
• ⇒ where right first entered into the lower lists (containing elements <= pivot)
• Hit separation point between the 2 lists ⇒ final location for pivot identified
• E.g. swap 600 and 450, 800 and 350, 650 and 400
• Then exchange pivot A[0] with A[right]
• swap(A, 0, right)
• ⇒ creates sublist A[0] - A[4] whose elements are less than those in sublist A[6] - A[9]
• Pivot (550) at A[5] creates 2 sublists that are approximately ½ the size of the original list
• These 2 sublists are processed using the same algorithm (recursive phase)
• 
• Recursive phase
• Process the 2 sublists $S_{low}$ (A[0] - A[4]) and $S_{high}$ (A[6] - A[9]) using the same methods
• Sublist $S_{low}$ (low = 0; high = 4; mid = 2; pivot = A[mid] = 300)
• Exchange pivot and A[low]
• Assign initial value to left and right
• left = 1 = low + 1
• right = 4 = high
• left stops at index 2 (A[2] > pivot)
• right stops at index 1 (A[1] < pivot)
• 
• Since right < left, process halts, and right is the separate point between 2 smaller sublists A[0] and A[2] - A[4]
• Exchange A[right] = 150 and A[low] = 300
• Note: location of pivot leaves us with a one-element sublist and a three-element sublist
• Recursive process terminates on an empty or single-element sublist
• 
• Sublist $S_{high}$ (low = 6; high = 0; mid = 7; pivot = A{mid] = 800
• Exchange pivot and A[low]
• Assign initial value to left and right
• left = 7 = low + 1
• right = 9 = high
• left stops when it passes the end of the list
• right remains at its initial position
• 
• Since right < left, process halts and right locates the insertion point for pivot
• Exchange A[right] = 700 and A[low] = 800
• Note: location of pivot leaves us with a three-element sublist and an empty sublist
• Recursive process terminates on an empty or single-element sublist
• 
• Completing the sort
• Sublist 400, 450, 350 (A[2] - A[4]), pivot = 450
• Scanning process arranges element in order 350, 400, 450
• 1 more recursive call needed with the 2-element sublist 350, 400
• Sublist 700, 650, 600 (A[6] - A[8]), pivot = 650
• After scanning, elements arranged in order 600, 650, 700
• Values 600 and 700 constitute 2-element sublists
• Example of inner workings [chatgpt]

[550, 600, 300, 800, 400, 450, 650, 350, 700, 150] pivot 400, so [400, 600, 300, 800, 550, 450, 650, 350, 700, 150] [400, 150, 300, 800, 550, 450, 650, 350, 700, 600] [400, 150, 300, 350, 550, 450, 650, 800, 700, 600] [350, 150, 300] [400] [550, 450, 650, 800, 700, 600] left sublist [350, 150, 300], mid is 150 [150, 350, 300] [150] [350, 300] —> sublist [350, 300], mid is 350 [350, 300] [300] [350] right sublist [550, 450, 650, 800, 700, 600], mid is 650 [650, 450, 550, 800, 700, 600] [650, 450, 550, 600, 700, 800] [600, 450, 550] [650] [700, 800] —> left sublist [600, 450, 550], mid is 450 [450, 600, 550] [450] [600, 550] —> sublist [600, 550], mid is 600 [600, 550] [550] [600] —> right sublist [700, 800], mid is 700 [700] [800] ==> overall [150] [300] [350] [400] [450] [550] [600] [650] [700] [800]

• Quick Sort implementation
• Recursive algorithm partitions a list A[low] to A[high] about a pivot, where
  pivot = A[mid] # mid = (low + high) / 2
• After exchanging pivot value with A[low], set indices
  left = low + 1 # beginning of list and
  right = high # end of list
• Left moves up the list (traverses) as long as it does not exceed right, and points at elements <= pivot

while (left <= right) and (A[left] <= pivot): left = left + 1 # go to next element

• After left is positioned, right moves down the list as long as it refers to elements > pivot

# scan down upper sublist; stop when right identifies an element <= pivot while (A[right] > pivot) right = right - 1

• If left < right, the indices identify 2 elements that are in the wrong sublists, and exchanges their values

# exchange a large element in the lower sublist with a smaller element from the higher sublist swap(A, left, right)

• Swapping of elements terminates when right < left
• Right identifies top of left sublist that contains elements <= pivot
• Right index is the pivot location in the list
• Retrieve pivot value from A[low]: swap(A, low, right)

def split(A, low, high): # split list into 2 sublist, rearrange list so pivot is properly positioned at A[pos] # get mid index and assign its value to pivot middle = (low + high) // 2 pivot = A[middle] # exchange pivot with 1st item swap(A, middle, low) left = low + 1 # index for left search right = high # index for right search while left <= right: # search from left for element > pivot while left <= right and A[left] <= pivot: left = left + 1 # search from right for element <= pivot while A[right] > pivot: right = right - 1 # interchange elements if left & right have not passed each other if left < right: swap(A, left, right) # end of searches; place pivot in correct position pos = right A[low] = A[right] A[pos] = pivot2345 return pos # pos is final position of pivot

def partition(A, low, high): mid = (low + high) // 2 pivot = A[mid] A[mid], A[low] = A[low], A[mid] pivot = A[low] left = low + 1 right = high while left <= right: (# note: swap signs if want descending order) while (left <= right) and A[left] <= pivot: left += 1 # move right while A[right] >= pivot: right -= 1 # move left # IN LOOP if left < right: A[left], A[right] = A[right], A[left] else: # USE A[low] not pivot else only changes variable not value !! A[right], A[low] = A[low], A[right] # out of loop – left > high return right

• Uses recursion to process the sublists
• After locating pivot to split list, we recursively call Quicksort with parameters low to right-1 (for lower sublist) and right+1 to high (for upper sublist)
• Stop when a sublist has <2 elements (since a 1-element or empty list is ordered)

def quicksort(A, low, high): # sort array elements A[low], …., A[high] if low < high: # list has >1 element # split into 2 sublists # pos is final position of pivot pos = split(A, low, high) # partition quicksort(A, low, pos-1) # quick sort left sublist quicksort(A, pos+1, high) # quick sort right sublist # else list has 0 or 1 element ⇒ no sorting required return A

• Youtube: (not in-place)

def quick_sort(sequence): if len(sequence) <= 1: return sequence pivot = sequence.pop() higher_than_pivot = [] lower_than_pivot = [] for item in sequence: if item < pivot: lower_than_pivot.append(item) else: higher_than_pivot.append(item) return quick_sort(lower_than_pivot) + [pivot] + quick_sort(higher_than_pivot) print(quick_sort([2,4,6,2,72,71]))

Merge sort

• Recursive
• Divides list into 2 halves, apply merge sort on each half recursively
• Stop splitting when each sublist contains only 1 element
• After the 2 halves are sorted, merge them
• Stop merging when 1 sorted list results
• 
• Must know how to present visualisation in this diagram
• If 3 numbers e.g. 57 48 70, split as [57] [48, 70] not [57, 48] [70] cos of mid

def mergeSort(arr, low, high): if low < high: mid = (low + high) // 2 # get mid index # sort 1st and 2nd halves mergeSort(arr, low, mid) # recursive call mergeSort(arr, mid+1, high) merge(arr, low, mid, high) # merge def merge(arr, low, mid, high): num = high - low + 1 # no. of elements temp = [0] * num # create temp array to store merged result # initialise left = low # initial index of 1st subarray right = mid + 1 # initial index of 2nd subarray index = 0 # initial index of merged array # merge both halves while left <= mid and right <= high: # check condition if arr[left] <= arr[right]: # left element is smaller temp[index] = arr[left] # insert left to temp left += 1 else: # right element is smaller temp[index] = arr[right] # insert right to temp right += 1 index += 1 # increment index by 1 # copy remaining elements of 1st subarray to temp while left <= mid: temp[index] = arr[left] left += 1 index += 1 # copy remaining elements of 2nd subarray to temp while right <= high: temp[index] = arr[right] right += 1 index += 1 # copy temp back into original array for i in range(0, num): arr[low+i] = temp[i]

Merge Sort In Python Explained (With Example And Code) def mergesort(arr): if len(arr) <= 1: return(arr) # recursion mid = len(arr) // 2 left_arr = arr[:mid] right_arr = arr[mid:] mergesort(left_arr) mergesort(right_arr) # merge i = 0 # left array index j = 0 # right array index k = 0 # merged array index while i < len(left_arr) and j < len(right_arr): if left_arr[i] < right_arr[j]: arr[k] = left_arr[i] i += 1 else: arr[k] = right_arr[j] j += 1 k += 1 while i < len(left_arr): arr[k] = left_arr[i] i += 1 k += 1 while j < len(right_arr): arr[k] = right_arr[j] j += 1 k += 1 return arr

• E.g. merging 2 sorted sublists [2,4,5,9] and [1,6,7,8]
  
  

Big-O Notation (i.e. worst case scenario)

• Measure of how long an algorithm takes to process an additional unit of input
• Time complexity: how much runtime each algorithm takes
• Increases with size of list to be searched, and on conditions (e.g. sorted or not)
• (NOT TESTED) Space complexity: how large memory space each algorithm takes
• Study how time cost changes w.r.t. its input size n in the worst case performance
• Can depend on amount of data & initial ordering of data

Constant complexity: O(1)	Linear complexity: O(n)	Quadratic complexity: O($n^2$)
Complexity remains constant regardless of input size	Time cost grows linearly and proportionally with input size	Running time increases with the square of the input size (e.g. nested loops)
def get_last(List): return List[-1]	def get_sum(List): total = 0 for item in List: total += item return total	def multiplication_table(n): for i in range(1, n+1): for j in range(1, n+1): print(i*j, end = ‘’) print()
E.g. Linear Search (if first element), Hash Table Search (if no collision)	E.g. Linear Search, Hash Table Search	E.g. Bubble Sort, Quick Sort, Insertion Sort

• (in slides not in notes:)

Logarithmic complexity: O(log(n))	Exponential complexity: O($2^n$)	Linearithmic / Quasilinear complexity: O(nlog(n))
Algorithm reduces size of input data by half with each step ⇒ no. of operations needed grows much slower than input size	Time taken doubles with each additional input ⇒ as input size inc., no. of operations grows very quickly	Execution time grows proportionally to input size multiplied by the logarithm of the input size ⇒ Combination of: O(n) [process all/most elements at each level of division & combi] and O(log n) [repeatedly having/doubling data space]
E.g. Binary Search	E.g. recursive calculation of Fibonacci sequence	E.g. Merge Sort, better case of Quick Sort

• Linear search: requires O(n) comparisons of items in the list
• Binary search: halves the ordered list in each iteration ⇒ requires O(log2n)⁶ comparisons
• Hash table (in ideal circumstances without collision): finds item in 1 step, i.e. O(1)
  (when collision occurs): requires O(n)
• ⇒ may require more space
• Bubble sort and insertion sort: nested loops ⇒ quadratic complexity with O($n^2$)
• Significant problem with large datasets of hundreds or thousands of elements
• Bubble sort
• Performs better for sorted list ⇒ can detect when list is sorted and does not continue making unnecessary passes through the list
• Generally very (least) inefficient: requires large no. of interchanges
• Insertion sort
• Generally inefficient, but better than bubble sort due to low overhead⁷
• Merge sort: divides the array in 2 halves and takes linear time to merge 2 halves ⇒ time complexity always O(n log n)
• Quick sort: time complexity varies between O(n log n) in the best case to O($n^2$) in worst case (i.e. when array is sorted and pivot selected is largest/smallest element ⇒ unlikely)
• Merge sort and quick sort: generally very efficient especially for large lists
• O(n log n) efficiency

Searching Algorithm	Time complexity (worst case)		Sorting Algorithm	Time complexity (worst case)
Linear Search	O(n)		Bubble Sort	O($n^2$)
Binary Search	O(log n)	89	Insertion Sort	O($n^2$)
Hash Table Search	O(n)		Quick Sort	O($n^2$)
Best case: O(1)			Merge Sort	O(n log n)

Comments from the Word document

Footnotes

1. Comment by ANDREA TAN KAI XUAN HCI: ? ↩

2. Comment by ANDREA TAN KAI XUAN HCI: is this the same as swap(A, low, right)? ↩

3. Comment by ANDREA TAN KAI XUAN HCI: eh nah then wheres pos ↩

4. Comment by ANDREA TAN KAI XUAN HCI: pos = right
   A[low], A[pos] = A[pos], A[low] ↩

5. Comment by ANDREA TAN KAI XUAN HCI: probably same as:
   A[low], A[right] = A[right], A[low]
   return right ↩

6. Comment by ANDREA TAN KAI XUAN HCI: O(log n)? ↩

7. Comment by ANDREA TAN KAI XUAN HCI: ? ↩

8. Comment by ANDREA TAN KAI XUAN HCI: not O(log2n)? or is it cos worst case ↩

9. Comment by ANDREA TAN KAI XUAN HCI: i think that’s for comparisons might be diff? ↩