Quicksort

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)
           }
       
   

1. Array Sum

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:] )
                           
   

2. Array Count Items

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]);
                             
   

3. Array Max Number

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;
           }