This content originally appeared on DEV Community and was authored by Amira Abdelhalim
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.
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.
- 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
[33, 10](33)[50, 34]
- 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.
This content originally appeared on DEV Community and was authored by Amira Abdelhalim
Amira Abdelhalim | Sciencx (2021-10-13T12:23:58+00:00) Divide and Conquer. Retrieved from https://www.scien.cx/2021/10/13/divide-and-conquer/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.