Your Web News in One Place

Search Archive

## Help Webnuz October 13, 2021 12:23 pm GMT

# Divide and Conquer

## Divide and Conquer

it is a well-known recursive technique for solving problems. D&C gives a new way to think about solving problem.
To solve a problem using D&C technique, there are two steps:

1. figure out the base case(the simplest possible case).
2. divide the problem until it becomes the base case.

`D&C isn't a simple algorithm that is applied to a problem. it is a way of thinking about the problem.`

Example

If we want to know the sum of numbers in an array... let's think of the simplest base case we can have.
The simplest case is to have an array of 0 or 1 item. so in each step we need to take our array closer to an empty array. ## Quicksort

Quicksort is one of the algorithms that is built on divide and conquer technique. It is a sorting algorithm faster than selection sort and it is frequently used in real life.
let's say we want to sort an array using quicksort what are the steps we shall do to have a sorted array.

1. pick an element from the array, this element is called the pivot.
2. find the elements smaller than the pivot then the elements greater than the pivot. `this process is called partitioning`

`[33, 10]` `(33)` `[50, 34]`

1. if sub-arrays are sorted we just need to combine them together.
2. if sub-arrays are not sorted then repeat the first 2 steps until having a sorted array. An online community for sharing and discovering great ideas, having debates, and making friends