Sorts Flashcards

1
Q

Internal need for sorting

A

Binary search

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

External need for sorting

A

Names in alphabetical order

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

What are total orders?

A

Assignment of an ordering to every pair of elements

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

What are partial orders?

A

Not an assignment for an ordering for every pair of elements

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

What is a sort algorithm?

A

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

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

How does an insertion sort work?

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

What is the average time for an insertion sort?

A

O(n^2)

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

What is the space for insertion sort?

A

O(1)

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

Describe the workings of a selection sort

A
  • Search for the lowest value
  • Swap it with the first element
  • Continue from the second element
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Average complexity of selection sort

A

O(n^2)

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

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

A

Divide
Recurse
Conquer

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

Describe the divide stage of divide and conquer

A

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

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

Describe the recurse stage of divide and conquer

A

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

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

Describe the conquer stage of divide and conquer

A

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

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

What type of algorithm is a merge sort?

A

Divide and conquer

Structural

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

Describe the divide stage for merge sort

A

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

17
Q

Describe the recurse stage for the merge sort

A

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

18
Q

Describe the conquer stage for the merge sort

A

The sorted sub lists are merged into a single list

19
Q

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

A

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

20
Q

What is the space complexity for merge sort?

21
Q

What is the average time complexity for merge sort?

22
Q

Where is memory reclaimed from as the merging process proceeds?

A

From the middle

23
Q

What will each sequence of length n give rise to?

A

Exactly the same recursive structure

24
Q

Benefits of merge sort

A

VERY predictable

25
Disadvantage of merge sort
Extra memory needed to hold intermediate results, held across the whole run
26
What type of sort is quick sort?
Value based
27
Describe how quick sort works
Splits the list based on heuristic choice of middle value and works to sort the sub lists
28
Which step is the trivial step in merge sort?
Split
29
Which step is the trivial step in quick sort?
Division
30
What is the pivot?
The value used to split the array in quick sort
31
What is the average complexity of quick sort?
O(n*logn)
32
What is the worst complexity of quick sort?
O(n^2)
33
What are the three ways we can choose our pivot?
- Last element - Random element - Median of three
34
Describe the median of three approach for choosing a pivot
Take first, last and middle element in sequence | Choose the median value