- D&C algorithms are recursive algorithms. To solve a problem using D&C, there are two steps:
- Figure out the base case. This should be the simplest possible case.
- Divide & decrease your problem until it becomes the base case.
- Given an array [2,4,6], add up and return the total
- Base case: if array has 0 element, sum is 0
- Reduce problem size: move closer to an empty array with every recursive call
function sum(array) {
if(!array.length) { // base case
return 0;
}
return array[0] + sum(array.slice(1)); // reduce problem size
}
- Tip: when you’re writing a recursive function involving an array, the base case is often an empty array or an array with one element. If you’re stuck, try that first.
- Base case: If array is empty, count is 0
- Reduce problem size: first item + count of the rest
function count(array){
if(!array.length) { // base case
return 0;
}
return 1 + count(array.slice(1)); // reduce problem size
}
- Base case: if array has one element, that is the max
- Reduce problem size: compare first item to the max from the rest of the array
function findMax(array){
if(array.length === 1) { // base case
return array[0];
}
const subMax = findMax(array.slice(1)); // reduce problem size
return array[0] > subMax ? array[0] : subMax;
}
- Quick sort is a sorting algorithm that is much faster than selection sort and is frequently used in real life. It uses D&C.
- Base case: array with one element doesn’t need to be sorted
- Reduce problem size:
- Pick a pivot
- Partition array into two subarrays: elements less than the pivot and elements greater than the pivot
- Call quick sort recursively on the two subarrays
- quicksort(small subarray) + pivot + quicksort(big subarray)
- Using divide & conquer to sort
[33, 15, 10]
- Pick an element from the array. This element is called
pivot
. - Now use the first item as
pivot
33
. - Find the elements smaller than the pivot and the elements larger than the pivot ⇒ This is called
partitioning
, now we have:- The sub-array of all numbers less than the pivot
[15,10]
- The pivot
- The sub-array of all numbers larger than the pivot
[]
- The sub-array of all numbers less than the pivot
- Sort the sub-arrays
- The results will be
sorted sub array
+pivot
+sorted sub array
quicksort([15,10]) + [33] + quicksort([])
- Inductive proofs are one way to prove that your algorithm works.
- Each inductive proof has two steps: the base case and the inductive case.
- For example, suppose we want to prove that I can climb to the top of a ladder.
- Inductive case: if my legs are on a rung, I can put my legs on the next rung.
- Base case: my legs are on the first rung.
- Therefore, I can climb the entire ladder, going up one rung at a time.
-
Quick sort is unique, because its speed depends on the pivot you choose.
-
Merge sort is O(n log n)
- Merge sort is a recursive algorithm that continuously splits the array in half until it cannot be further divided
step 1: start step 2: declare array and left, right, mid variable step 3: perform merge function. mergesort(array, left, right) mergesort(array, left, right) if left > right return mid = (left + right)/2 mergesort(array, left, mid) mergesort(array, mid+1, right) merge(array, left, mid, right) step 4: Stop
-
In the worst case, quick sort can takes O(n^2) times
-
But in the average, quick sort takes O(n log n) times
- If you are trying to print [2,4,6,8,10]
- function
print_items
: 2 4 6 8 10 - function
print_items2
: 2 4 6 8 10
- function
- When the time complexity are the same (both are O(n)), the constant makes a difference.
- Quicksort & merge sort both have O(n log n) time, but quicksort is faster because it has a smaller constant than merge sort.
-
The performance of quicksort heavily depends on the pivot you choose.
-
If there’s an array already sorted, quicksort will re-sort it again.
-
If you choose pivot from the first item:
- This is the worst case
- The height of the call stack will be O(n)
- Each level runs O(n)
- The total time will be O(n^2)
-
If you choose the pivot from middle of the array:
- This is the best case
- The height of the call stack will be O(log n)
- Each level runs O(n)
- The total time will be O(n log n)
- Divide & conquer works by breaking a problem down into smaller & smaller pieces.
- If you using D&C on a list, the base case is probably an empty array or an array with one element.
- Quicksort, choosing a random element as the pivot. The average run time is O(n log n)
- The constant in Big O can matters sometimes. That’s why quicksort is faster than merge sort
- The constant almost never matters for simple search (O(n)) vs binary search(O(log n)), because O(log n) is so much faster than O(n) when your list gets bigger.
- the code for quick sort
- https://leetcode.com/problems/sort-an-array/