A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.
Output ...
// JAVASCRIPT
function _quicksort(arr)
{
// base-case
if(arr.length < 2)
{
return arr;
}
else
{
let pivot = arr[0];
// I'm creating a sub-array using filter() method that creates a new array filled with elements that pass a test provided by a function.
let less = arr.slice(1).filter( function(el){ return el <= pivot; } );
let greater = arr.slice(1).filter( function(el){ return el > pivot; } );
return _quicksort(less).concat(pivot, _quicksort(greater));
}
}
// PYTHON
def quicksort(array)
{
# base-case, arrays with 0 or 1 elements are already "sorted".
if len(array) < 2:
return array
else
pivot = aray[0]
less = [i for i in array[1:] if i<= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
}
Just like the quicksort algorithm, the sum of elements in an array can be written using the divide-and-conquer technique.
The sum of array numbers is ...
// JAVASCRIPT
// using traditional loop
function sum(arr) {
let total = 0;
for(let i=0 ; i < arr.length; i++) {
total += arr[i];
}
return total;
}
// using recursion (divide-and-conquer)
function sumRecursive(arr) {
if(arr.length == 0) return 0;
return arr[0] + sumRecursive( arr.slice(1) );
// PYTHON
// using traditional loop
def sum(arr):
total = 0
for x in arr:
total += x
return total
// using recursion (divide-and-conquer)
def sum(list):
if list == []:
return 0
return list[0] + sum( list[1:] )
Just like the quicksort and array sum algorithms to find the max number in an array we can use the divide-and-conquer technique.
Number of array items ...
// JAVASCRIPT using recursion (divide-and-conquer)
function count(array) {
if(array == 0) return 0;
return 1 + count( array.slice(1) );
// PYTHON using recursion (divide-and-conquer)
def count(list):
if list == []:
return 0
return 1 + count(list[1]);
Just like the quicksort, array sum algorithms and array count items, to find the max number in an array we can use the divide-and-conquer technique.
The array max number is ...
// JAVASCRIPT using recursion (divide-and-conquer)
function _max(arr) {
if(arr.length == 2) return arr[0] > arr[1] ? arr[0] : arr[1];
var sub_max = _max( arr.slice(1) );
return arr[0] > sub_max ? arr[0] : sub_max;
}