Scribd
Upload
13 views23 pages

Chapter 2

Chapter 2 introduces the divide and conquer algorithm, a problem-solving technique that involves breaking down a problem into smaller subproblems, solving them individually, and then combining their solutions. It covers specific algorithms like Binary Search, Merge Sort, and Quick Sort, detailing their processes and complexities. Additionally, it discusses the advantages and disadvantages of Merge Sort and provides an assignment related to implementing these algorithms.

Uploaded by

gbonsa2
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
13 views23 pages

Chapter 2

Chapter 2 introduces the divide and conquer algorithm, a problem-solving technique that involves breaking down a problem into smaller subproblems, solving them individually, and then combining their solutions. It covers specific algorithms like Binary Search, Merge Sort, and Quick Sort, detailing their processes and complexities. Additionally, it discusses the advantages and disadvantages of Merge Sort and provides an assignment related to implementing these algorithms.

Uploaded by

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

CHAPTER 2

DIVIDE AND CONQUER


Contents

 Introduction to divide and conquer


 Binary Search
 Quick Sort
 Selection sort
What does it mean divide and conquer?

 Divide and Conquer Algorithm is a problem-solving technique used to


solve problems by dividing the main problem into subproblems, solving
them individually and then merging them to find solution to the original
problem.
 Divide and Conquer algorithm is a problem-solving strategy that involves:
 Divide : Break the given problem into smaller non-overlapping problems.
 Conquer : Solve Smaller Problems
 Combine : Use the Solutions of Smaller Problems to find the overall result.
Example
1. Divide:

❑ Break down the original problem into smaller subproblems.

❑ Each subproblem should represent a part of the overall problem.

❑ The goal is to divide the problem until no further division is


possible.
2. Conquer:
❑ Solve each of the smaller subproblems individually.

❑ If a subproblem is small enough (often referred to as the “base


case”), we solve it directly without further recursion.

❑ The goal is to find solutions for these subproblems independently.


3. Merge:

❑ Combine the sub-problems to get the final solution of the whole


problem.

❑ Once the smaller subproblems are solved, we recursively combine


their solutions to get the solution of larger problem.

❑ The goal is to formulate a solution for the original problem by


merging the results from the subproblems.
Examples of Divide and Conquer are Merge Sort, Quick Sort, Binary
Search and Closest Pair of Points.
Binary Search

 The binary search algorithm uses the divide-and-conquer strategy to search through an
array.
 This searching algorithms works only on an ordered list.

➢ The basic idea is:


 Locate midpoint of array to search
 Determine if target is in lower half or upper half of an array.
✓ If the target is in lower half, make this half the array to search
✓ If the target in the upper half, make this half the array to search
 Loop back to step 1 until the size of the array to search is one, and this
element does not match, in which case return –1.
 The computational time for this algorithm is proportional to log2 n.
 Therefore, the time complexity is O(log n)
Searching a Dictionary:

 A detailed specification of this process:


1. The goal is to search for a word w in region of the book
2. The initial region is the entire book
3. At each step pick a word x in the middle of the current region
4. There are now two smaller regions: the part before x and the part
after x
5. if w comes before x, repeat the search on the region before x,
otherwise search the region following x (go back to step 3)
Note: at first a “region” is of a group of pages, but eventually a region
is a set of words on a single page
Example
Merge sort

 Merge sort is a sorting algorithm that follows the divide-and-


conquer approach.
 It works by recursively dividing the input array into smaller
subarrays and sorting those subarrays then merging them back
together to obtain the sorted array.
 In simple terms, we can say that the process of merge sort is to
divide the array into two halves, sort each half, and then merge the
sorted halves back together. This process is repeated until the entire
array is sorted.
Merge sort…

 Merge sort uses divide and conquer strategy and its time complexity
is O(nlogn).
Algorithm:
1. Divide the array in to two halves.
2. Recursively sort the first n/2 items.
3. Recursively sort the last n/2 items.
4. Merge sorted items (using an auxiliary array).
Example: Sort the following list using merge sort algorithm.
Example: Sort the following list using merge sort algorithm.
Complexity Analysis of Merge Sort:

• Time Complexity:
• Best Case: O(n log n), When the array is already sorted or nearly sorted.
• Average Case: O(n log n), When the array is randomly ordered.
• Worst Case: O(n log n), When the array is sorted in reverse order.
Advantages of Merge Sort:

• Stability : Merge sort is a stable sorting algorithm, which means it maintains the
relative order of equal elements in the input array.

• Guaranteed worst-case performance: Merge sort has a worst-case time


complexity of O(N logN) , which means it performs well even on large datasets.

• Simple to implement: The divide-and-conquer approach is straightforward.

• Naturally Parallel : We independently merge subarrays that makes it suitable for


parallel processing.
Disadvantages of Merge Sort:

• Space complexity: Merge sort requires additional memory to store


the merged sub-arrays during the sorting process.

• Not in-place: Merge sort is not an in-place sorting algorithm, which


means it requires additional memory to store the sorted data. This
can be a disadvantage in applications where memory usage is a
concern.

• Slower than Quicksort in general. QuickSort is more cache


friendly because it works in-place.
Quick Sort

 Quick sort is the fastest known algorithm. It uses divide and conquer
strategy and in the worst case its complexity is O (n2). But its expected
complexity is O(nlogn).
Algorithm:
1. Choose a pivot value (mostly the first element is taken as the pivot value)
2. Position the pivot element and partition the list so that:
✓ the left part has items less than or equal to the pivot value
✓ the right part has items greater than or equal to the pivot value
4. Recursively sort the left part
5. Recursively sort the right part
.
Selection Sort

 Basic Idea:
 Loop through the array from i=0 to n-1.
 Select the smallest element in the array from i to n
 Swap this value with value at position i.
 Given array abc = 34 8 64 51 32 21
.

 Analysis
 How many comparisons?
 (n-1)+(n-2)+...+1= O(n2 )
 How many swaps?
 n=O(n)
 How much space?
 In-place algorithm
Individual Assignment (10%)

 1. Write implementations(pseudocode or flowchart) of algorithms


solved using divide and conquer approach.
 The algorithms may be: Binary search, merge sort, quick sort or any
of your interest under divide and conquer approach.
 Deadline: March, 27, 2025
 Submission format: hand written.
.

You might also like