Quick Sort + Divide and conquer

Question 1

How does Quick Sort work?

Answer 1

Selects an element, usually the central element and divides the input around it.

Elements smaller than the the pivot are put on the left of the pivot and larger on the right.

process repeated recursively

Question 2

What is the pivot

Answer 2

The element selected in quicksort

Question 3

Downsides of quicksort

Answer 3

Not very fast

same time complexity as bubble sort with 0(n^2)

Question 4

What is divide and conquer?

Answer 4

Problem solving technique to break a problem down into smaller more managable sub problems and then reassemble the full solution.

Question 5

Divide (Divide and conquer)

Answer 5

Halving the size of the problem with every iteration

Question 6

Conquer

Answer 6

Where each sub problem is solved ofter recursively.

Question 7

Merge

Answer 7

All teh solutions to the subproblems are recombined during this stage.

Question 8

Where is it used?

Answer 8

In binary search
quick sort
merge sort

Question 9

Divide and conquer advantages

Answer 9

Simplifies very complex problems

the time take to solve the problem does not increase at the rate of the difficulty of the problem

0(logn)