DIVIDE AND CONQUER ALGORITHMS

Understand the concept of divide and conquer and when it might be useful in solving a problem. 

Desmond Tutu—a human rights activist in the 1990’s—once said “there is only one way to eat an elephant: a bite at a time”. Typically, large and daunting tasks can be broken up into smaller sections which can be solved in less time than solving one large task. Divide and conquer algorithms take this idea of breaking up a large task that would be difficult to solve and breaks them up into simple sub-problems that can be solved directly and then combined. Quick sort is a common algorithm that uses the divide and conquer ideology to sort a large array of values in a fast manner.

Recursion- The act of defining a function that calls itself from within. Recursion is defined in two steps: the base case and the recursive step.

• Base case- An end case where recursion is not needed to produce an answer.

• Recursive case- A set of rules that reduces all other cases to the base case.

Divide and Conquer- The act of recursively breaking down problems into two or more sub-problems into similar, but simpler sub-problems that can be solved directly and then combine their solutions to solve the larger problem. Divide and conquer algorithms are defined in two steps:

• Divide- Splitting a large problem into similar, simpler problems. This is done recursively until the problems are simple enough to be solved outright.

• Conquer- Combining the sub-problems solutions to find the solution to the original problem.

Partition- The act of breaking up values into sections.

Pivot- Point at which the values are divided into two sub-arrays.

Briefly review recursion and ensure the concept of quicksort is understood.

Write a function in QuickSortStudentSolution.py’s partition that:

1. Originally puts the pivot at the highest partitioned array value.

2. Creates index i that is one lower than the lowest partitioned array value.

3. Iterates value j from the lowest partitioned array value to the highest.

   • If the partitioned array value at j is less than the pivot, then put i at i+1 and swap array values at i and j.

4. Swap partitioned array value at i+1 and the highest partitioned array value.

Write a function in QuickSortStudentSolution.py’s quicksort that:

1. Checks that the leftmost value is less than the rightmost value.

2. Finds the partition index pi using the array’s leftmost l and rightmost r values.

3. Recursively quicksorts the array of values from the leftmost value to pi-1

4. Recursively quicksorts the array values from pi+1 to the rightmost value.

What is the base case in quick sorting?

What does the pivot do in quick sorting?

• • • Does it move? Why?

Why partition in quick sorting?

Which section of the code is the divide?

Which section of the code is the conquer?

Consider the array of 10 values in the original order of [1,5,8,2,4,3,7,0,2,9].

• • • Create a tree showing how quicksort would go through this array.

    • How many divisions would be created?

    • How many conquers would happen?

• What is divide and conquer?

• What is quick sorting?

•  What is a pivot?

Merge Sort