Standard Algorithms Flashcards Preview

AH Computing > Standard Algorithms > Flashcards

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

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


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
ascending order

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


Describe a simple sort

- Compares adjacent items
- If second number is greater, numbers are swapped
- Repeats by comparing second number with each number in list