Flashcards in Standard Algorithms Deck (28):

1

## How many comparisons does a bubble sort require?

### n^2

2

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

### When the list is in reverse order

3

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

### N

4

## What conditions are placed on data using a binary search?

### Data must be sorted

5

## 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

6

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

### x, where 2^x > n

7

## Why is the selection sort with two lists inefficient?

###
- Has to check every item in the list each time

- Requires second list

8

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

### n(n-1)

9

## What makes a selection sort complicated?

### Choice of dummy value

10

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

### n

11

## What needs to be passed into the binary search function?

### Array and thing you are looking to find

12

## 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

13

## 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

14

## 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

15

## 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

16

## How many passes will an insertion have?

###
n-1

17

## What computational construct does quick sort use?

### Recursion

18

## What is the base sort of the quick sort?

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

19

## In what scenarios does quick sort before inefficient?

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

20

## What is the merge sort particularly useful for?

### Two sorted lists to be joined together

21

## 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

22

##
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

23

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

24

## 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

25

## 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

26

## 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

27

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

###
Average - log(n)

Worst - n^2

28