Scribd
Upload
6 views

Algorithm Analysis and Design

Uploaded by

PRINCE KOFI GYIMAH
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
6 views

Algorithm Analysis and Design

Uploaded by

PRINCE KOFI GYIMAH
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 34

LECTURE 2: DIVIDE &

CONQUER ALGORITHM
SUB-TOPIC BINARY SEARCH, MERGE SORT, QUICK SORT, STRASSEN'S
MATRIX, FINDING MAXIMUM AND MINIMUM
THE DEFECT COIN PROBLEM
DIVIDE AND CONQUER

• General Definition:
• A divide and conquer algorithm is a strategy for solving large problems by,
• 1. Breaking the problem into smaller sub-problems
• 2. Solving the sub-problems and
• 3. combining them to get the desired output
• To use the divide and conquer algorithm, recursion is used.
DAC ALGORITHM
BINARY SEARCH ALGORITHM

• Let a1 be list of elements that are in non-decreasing order


• It is a problem of determining whether a given element x is present in the list
and it is a quick and method
EXAMPLE OF BINARY SEARCH
EXAMPLE 2

5 7 9 13 32 33 44 54 56 88
MERGE SORT
MERGE SORT PROCEDURE

• Usually done recursively


• Divide and conquer
EXAMPLE
• The array is broken down into individual items
• Quick note, when this is implemented in code, the above steps will be done
in different order because of recursion
• To sort, we will examine the individual items, compare their value and merge
them into temporary arrays
CONTINUATION
FINAL OUTCOME
QUICK SORT

• Quick sort is recursive algorithm


• When you think of quick sort, the word pivot comes to bear
• Pivot is simply one of the items in the array that means the following three
conditions after we sorted it.
PIVOT CONDITIONS

• Correct position in final sorted array


• Items to the left are smaller
• Items to the right are larger
EXAMPLE
CONTINUATION
MORE ON QUICK SORT
• Since the left side of the array is sorted
• We can divide the array into sub arrays
• Recursion will handle the rest
HOW TO CHOOSE PIVOT ELEMENT

• Median of three- In this method we consider the first, middle and last
element of the array. (2+8+4)/3 = 4.6

You might also like