Standard Algorithms COPY Flashcards

1
Q

How many comparisons does a bubble sort require?

A

n^2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

When the list is in reverse order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

N

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What conditions are placed on data using a binary search?

A

Data must be sorted

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

Linear - Simple, slow for large lists

Binary - Complex, fast for large lists

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

x, where 2^x > n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Why is the selection sort with two lists inefficient?

A
  • Has to check every item in the list each time

- Requires second list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

n(n-1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What makes a selection sort complicated?

A

Choice of dummy value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What needs to be passed into the binary search function?

A

Array and thing you are looking to find

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Write pseudocode for a binary search

A
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Write pseudocode for a bubble sort

A
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Write pseudocode for a selection sort

A
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Write pseudocode for an insertion sort

A
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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How many passes will an insertion have?

A

n-1

17
Q

What computational construct does quick sort use?

A

Recursion

18
Q

What is the base sort of the quick sort?

A

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

19
Q

In what scenarios does quick sort before inefficient?

A

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

20
Q

What is the merge sort particularly useful for?

A

Two sorted lists to be joined together

21
Q

What do sort algorithms performance depends on?

A
  • 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
22
Q

Explain how a bubble sort rearranges a list into

ascending order

A

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

23
Q

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

A
  • 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)
24
Q

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

A
  • 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
25
Q

Describe a binary search

A
  • 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
26
Q

Describe a selection sort and give the number of comparisons needed

A
  • 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
27
Q

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

A

Average - log(n)

Worst - n^2

28
Q

Describe a simple sort

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