Standard Algorithms COPY Flashcards
How many comparisons does a bubble sort require?
n^2
In what case would a bubble sort have n^2 swaps?
When the list is in reverse order
How many passes through a list does a bubble sort do?
N
What conditions are placed on data using a binary search?
Data must be sorted
Compare linear search and binary search in terms of complexity and speed for large lists
Linear - Simple, slow for large lists
Binary - Complex, fast for large lists
What is the maximum number of comparisons for a binary search?
x, where 2^x > n
Why is the selection sort with two lists inefficient?
- Has to check every item in the list each time
- Requires second list
How many comparisons does a selection sort with two lists use?
n(n-1)
What makes a selection sort complicated?
Choice of dummy value
How many passes through a list will a selection sort need?
n
What needs to be passed into the binary search function?
Array and thing you are looking to find
Write pseudocode for a binary search
def BinarySearch(array,searchkey): found = false start = 0 end = len(array) while start <= end and found = false: guess = (start+end)//2 if array[guess] = searchkey: found = true else if array[guess] < searchkey: start = guess + 1 else if array[guess] > searchkey: end = guess -1 end if return found
Write pseudocode for a bubble sort
def BubbleSort(array): for passnum in range(len(array),-1,0): for i in range(passnum): if array[i] > array[i+1}: temp =array[i] array[i] = array[i+1] array[i+1] = temp
Write pseudocode for a selection sort
def SelectionSort(alist): dummy = max(alist) for i in range(len(alist)): minimum = alist[0] pos = 0 for x in range(len(alist)): if alist[x] < minimum: minimum = alist[] pos = x end if end for alist[pos] = dummy blist[i] = minimum end for return blist
Write pseudocode for an insertion sort
def InsertionSort(alist): for i in range(len(alist)-1): current = alist[i] position = i while position > 0 and alist[position -1] > current: alist[position] = alist[position-1] position = position -1 end while alist[position] = current end for return alist