Flashcards in Standard Algorithms Deck (28):
How many comparisons does a bubble sort require?
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?
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?
What makes a selection sort complicated?
Choice of dummy value
How many passes through a list will a selection sort need?
What needs to be passed into the binary search function?
Array and thing you are looking to find
Write pseudocode for a binary search
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
Write pseudocode for a bubble sort
for passnum in range(len(array),-1,0):
for i in range(passnum):
if array[i] > array[i+1}:
array[i] = array[i+1]
array[i+1] = temp
Write pseudocode for a selection sort
dummy = max(alist)
for i in range(len(alist)):
minimum = alist
pos = 0
for x in range(len(alist)):
if alist[x] < minimum:
minimum = alist
pos = x
alist[pos] = dummy
blist[i] = minimum
Write pseudocode for an insertion sort
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
alist[position] = current
How many passes will an insertion have?
What computational construct does quick sort use?
What is the base sort of the quick sort?
That an empty list or one with one element is a sorted list
In what scenarios does quick sort before inefficient?
If the list to be sorted does not fit in the available
What is the merge sort particularly useful for?
Two sorted lists to be joined together
What do sort algorithms performance depends on?
- Size of the list being sorted
- If the list is partially sorted or not
- If list is in reverse order
- If the list contains lot of duplicate numbers
Explain how a bubble sort rearranges a list into
Compares adjacent items
If first is greater than second, items are swapped
Repeat this process from beginning of list to unsorted part
Stops when no more swaps have taken place
Describe a quick sort and give it's average time to sort a list
- Uses recursion
- Works on the base fact that a list with no elements or one element is a sorted list
- Divide and Conquer method
- Breaks the list into smaller sub-lists by comparing the list values to a pivot value and splitting accordingly
- Average time: log(n)
Describe an insertion sort and give it's average time to sort a list
- Comparative sort
- Compares adjacent values and swap if out of order
- Orders the first two items and then inserting 3rd item into correct place and continue with 4th and so on
- Continual reapplication of comparisons
- Average time: n(n-1)/2
Describe a binary search
- Compares the target value to the middle of the list
- If not at middle value, define a new list containing target
- Continue this until target is middle value of a smaller list
Describe a selection sort and give the number of comparisons needed
- A dummy value is selected
- Linear search through the list, looking for minimum value
- Minimum value placed in second list, dummy value put in place in first list
- Repeated until all values in first list are dummy's
- N(N-1) Comparisons
What is the average and worst time for the quick sort?
Average - log(n)
Worst - n^2