Standard Algorithms

Question 1

How many comparisons does a bubble sort require?

Answer 1

n^2

Question 2

In what case would a bubble sort have n^2 swaps?

Answer 2

When the list is in reverse order

Question 3

How many passes through a list does a bubble sort do?

Answer 3

N

Question 4

What conditions are placed on data using a binary search?

Answer 4

Data must be sorted

Question 5

Compare linear search and binary search in terms of complexity and speed for large lists

Answer 5

Linear - Simple, slow for large lists

Binary - Complex, fast for large lists

Question 6

What is the maximum number of comparisons for a binary search?

Answer 6

x, where 2^x > n

Question 7

Why is the selection sort with two lists inefficient?

Answer 7

• Has to check every item in the list each time

- Requires second list

Question 8

How many comparisons does a selection sort with two lists use?

Answer 8

n(n-1)

Question 9

What makes a selection sort complicated?

Answer 9

Choice of dummy value

Question 10

How many passes through a list will a selection sort need?

Answer 10

n

Question 11

What needs to be passed into the binary search function?

Answer 11

Array and thing you are looking to find

Question 12

Write pseudocode for a binary search

Answer 12

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

Question 13

Write pseudocode for a bubble sort

Answer 13

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

Question 14

Write pseudocode for a selection sort

Answer 14

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

Question 15

Write pseudocode for an insertion sort

Answer 15

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

Question 16

How many passes will an insertion have?

Answer 16

n-1

Question 17

What computational construct does quick sort use?

Answer 17

Recursion

Question 18

What is the base sort of the quick sort?

Answer 18

That an empty list or one with one element is a sorted list

Question 19

In what scenarios does quick sort before inefficient?

Answer 19

If the list to be sorted does not fit in the available

Question 20

What is the merge sort particularly useful for?

Answer 20

Two sorted lists to be joined together

Question 21

What do sort algorithms performance depends on?

Answer 21

• 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

Question 22

Explain how a bubble sort rearranges a list into

ascending order

Answer 22

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

Question 23

Describe a quick sort and give it’s average time to sort a list

Answer 23

• 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)

Question 24

Describe an insertion sort and give it’s average time to sort a list

Answer 24

• 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

Question 25

Describe a binary search

Answer 25

• 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

Question 26

Describe a selection sort and give the number of comparisons needed

Answer 26

• 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

Question 27

What is the average and worst time for the quick sort?

Answer 27

Average - log(n)

Worst - n^2

Question 28

Describe a simple sort

Answer 28

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