Sorts

Question 1

Internal need for sorting

Answer 1

Binary search

Question 2

External need for sorting

Answer 2

Names in alphabetical order

Question 3

What are total orders?

Answer 3

Assignment of an ordering to every pair of elements

Question 4

What are partial orders?

Answer 4

Not an assignment for an ordering for every pair of elements

Question 5

What is a sort algorithm?

Answer 5

The placement of a structure into the order induced by the sort order

Question 6

How does an insertion sort work?

Answer 6

• walk along a list
• if value is larger than one of its left, do nothing
• if it is smaller, shuffle the elements to its left and insert it into the correct place

Question 7

What is the average time for an insertion sort?

Answer 7

O(n^2)

Question 8

What is the space for insertion sort?

Answer 8

O(1)

Question 9

Describe the workings of a selection sort

Answer 9

• Search for the lowest value
• Swap it with the first element
• Continue from the second element

Question 10

Average complexity of selection sort

Answer 10

O(n^2)

Question 11

What are the three stages in a divide and conquer algorithm?

Answer 11

Divide
Recurse
Conquer

Question 12

Describe the divide stage of divide and conquer

Answer 12

Take a problem S and split it into two smaller sub problems S1 and S2

Question 13

Describe the recurse stage of divide and conquer

Answer 13

Recursively solve S1 and S2, either directly (by the base case) or by further division

Question 14

Describe the conquer stage of divide and conquer

Answer 14

Combine the solutions to S1 and S2 into a solution to S

Question 15

What type of algorithm is a merge sort?

Answer 15

Divide and conquer

Structural

Question 16

Describe the divide stage for merge sort

Answer 16

Sorting n elements can be simplified into two problems sorting n/2 elements each

Question 17

Describe the recurse stage for the merge sort

Answer 17

Base case - a problem of 1 element in solved other we can recursively divide

Question 18

Describe the conquer stage for the merge sort

Answer 18

The sorted sub lists are merged into a single list

Question 19

Where does the logarithmic complexity aspect come from in merge sort?

Answer 19

By definition, you can divide a list of length n in two logn times

Question 20

What is the space complexity for merge sort?

Answer 20

O(n*logn)

Question 21

What is the average time complexity for merge sort?

Answer 21

O(n*logn)

Question 22

Where is memory reclaimed from as the merging process proceeds?

Answer 22

From the middle

Question 23

What will each sequence of length n give rise to?

Answer 23

Exactly the same recursive structure

Question 24

Benefits of merge sort

Answer 24

VERY predictable

Question 25

Disadvantage of merge sort

Answer 25

Extra memory needed to hold intermediate results, held across the whole run

Question 26

What type of sort is quick sort?

Answer 26

Value based

Question 27

Describe how quick sort works

Answer 27

Splits the list based on heuristic choice of middle value and works to sort the sub lists

Question 28

Which step is the trivial step in merge sort?

Answer 28

Split

Question 29

Which step is the trivial step in quick sort?

Answer 29

Division

Question 30

What is the pivot?

Answer 30

The value used to split the array in quick sort

Question 31

What is the average complexity of quick sort?

Answer 31

O(n*logn)

Question 32

What is the worst complexity of quick sort?

Answer 32

O(n^2)

Question 33

What are the three ways we can choose our pivot?

Answer 33

• Last element
• Random element
• Median of three

Question 34

Describe the median of three approach for choosing a pivot

Answer 34

Take first, last and middle element in sequence

Choose the median value