An Interest In:
Web News this Week
- October 13, 2021
- October 12, 2021
- October 11, 2021
- October 10, 2021
- October 9, 2021
- October 8, 2021
- October 7, 2021
Some of Our Sources
- Technology Review
- TutsPlus - Code
- Joshua Blankenship
- Vandelay Design
- Naldz Graphics
- FanExtra - PSD
- Crazy Leaf Design
- Fudge Graphics
- Spyre Studios
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:
- figure out the base case(the simplest possible case).
- 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.
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 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.
- pick an element from the array, this element is called the pivot.
- find the elements smaller than the pivot then the elements greater than the pivot.
this process is called partitioning
- if sub-arrays are sorted we just need to combine them together.
- if sub-arrays are not sorted then repeat the first 2 steps until having a sorted array.
Original Link: https://dev.to/amiraabdelhalim/divide-and-conquer-p0d