Quicksort

Question 1

What is divide and conquer?

Answer 1

It’s a recursion algorithm

To solve a problem using D&C, there are two steps:
1. Figure out the base case. This should be the simplest possible case.
2. Divide or decrease your problem until it becomes the base case.

Question 2

What is quicksort?

Answer 2

It’s a sorting algorithm, faster than selection sort and used more in real life, that use divide and conquer technique

Question 3

What is the pivot?

Answer 3

It’s the element that we use to sort in quick sort algorithm

Question 4

What is partitioning?

Answer 4

When we use the pivot, the array divided into:

A sub-array of all the numbers less than the pivot
The pivot
A sub-array of all the numbers greater than the pivot

Question 5

How does quick sort algorithm work?

Answer 5

1. Pick a pivot.
2. Partition the array into two sub-arrays: elements less than the pivot and elements greater than the pivot.
3. Call quicksort recursively on the two sub-arrays.

Question 6

What is the if O for quick sort?

Answer 6

In the best case and average case=> o(n log n)
In the worst case => o(n^2)