DATA STRUCTURES-UNIT V
UNIT V
DIVIDE AND CONQUER ALGORITHMS: General Method – Binary Search-
Quick Sort- Merge Sort.
BACKTRACKING: General method, 8 Queens, Graph
coloring, Hamiltonian cycle.
DIVIDE AND CONQUER ALGORITHMS: General Method
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 is mainly useful when we divide a problem
into independent subproblems. If we have overlapping subproblems, then we
use Dynamic Programming.
Divide and Conquer Algorithm can be divided into three
steps: Divide, Conquer and Merge.
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.
In Merge Sort, the conquer step is to sort the two halves
individually.
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.
Characteristics of Divide and
Conquer Algorithm
The characteristics of Divide and Conquer Algorithm are:
●
Dividing the Problem: The first step is to break the
problem into smaller, more manageable subproblems. This division can be done
recursively until the subproblems become simple
●
Independence of Subproblems: Each subproblem should be
independent of the others, meaning that solving one subproblem does not depend
on the solution of another.
●
Conquering Each Subproblem: Once divided, the subproblems are
solved individually. This may involve applying the same divide and conquer
approach recursively until the subproblems become simple
●
Combining Solutions: After solving the subproblems,
their solutions are combined to obtain the solution to the original problem.
This combination step should be relatively efficient and straightforward.
Examples of Divide and Conquer
Algorithm
1. Merge Sort
2. Quicksort
5.2)BINARY SEARCH ALGORITHM
Binary Search Algorithm is
a searching algorithm used in a sorted array
by repeatedly dividing the search interval in half.
The idea of binary search is to use
the information that the array is sorted and reduce the time complexity to
O(log N).
●
Binary search is a search algorithm
used to find the position of a target value within a sorted array.
●
It works by repeatedly dividing the search interval in half
until the target value is found or the interval is empty.
●
The search interval is halved by comparing the target element
with the middle value of the search space.
To
apply Binary Search algorithm:
● The
data structure must be sorted.
●
Access to any element of the data structure should take constant
time.
Binary Search Algorithm
Below is the
step-by-step algorithm for Binary Search:
●
Divide the search space into two halves by finding the middle index “mid”.
●
Compare the middle element of the search space with the key.
●
If the key is found
at middle element, the process is terminated.
●
If the key is not
found at middle element, choose which half will be used as the next search
space.
○ If the key is smaller than the middle element,
then the left side is used for next
search.
○ If the key is larger than the middle element,
then the right side is used for next
search.
●
This process is continued until the key is found or the total search space is exhausted.
Binary Search Algorithm work:
Example:
arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, and the target = 23.
The Binary Search Algorithm can be
implemented in the following two ways
●
●
Applications Binary Search Algorithm:
●
Binary search can be used as a building block for more complex
algorithms used in machine learning, such as algorithms for training neural
networks or finding the optimal hyperparameters for a model.
●
It can be used for searching in computer graphics such as
algorithms for ray tracing or texture mapping.
●
It can be used for searching a database.
Advantages of Binary Search
●
Binary search is faster than linear search, especially for large
arrays.
●
More efficient than other searching algorithms with a similar
time complexity, such as interpolation search or exponential search.
●
Binary search is well-suited for searching large datasets that
are stored in external memory, such as on a hard drive or in the cloud.
Disadvantages of Binary Search
●
The array should be sorted.
●
Binary search requires that the data structure being searched be
stored in contiguous memory locations.
●
Binary search requires that the elements of the array be
comparable, meaning that they must be able to be ordered.
QuickSort is a sorting algorithm based on the Divide and Conquer that picks an element as a
pivot and partitions the given array around the picked pivot by placing the
pivot in its correct position in the sorted array.
QuickSort works on the
principle of divide and conquer, breaking down the problem into smaller
sub-problems.
There are mainly three
steps in the algorithm:
1.
Choose a Pivot: Select an element from the array as the
pivot. The choice of pivot can vary (e.g., first element, last element, random
element, or median).
2.
Partition the Array: Rearrange the array around the pivot.
After partitioning, all elements smaller than the pivot will be on its left,
and all elements greater than the pivot will be on its right. The pivot is then
in its correct position, and we obtain the index of the pivot.
3.
Recursively Call: Recursively apply the same process to
the two partitioned sub-arrays (left and right of the pivot).
4.
Base Case: The recursion stops when there is only one
element left in the sub-array, as a single element is already sorted.
Choice of Pivot
There are many
different choices for picking pivots.
● Always pick the first
(or last) element as a pivot. The problem with this approach is it ends up
in the worst case when array is already sorted.
● Pick a random element
as a pivot. This is a preferred approach because it does not have a
pattern for which the worst case happens.
●
Pick the median element is pivot. This is an ideal approach in
terms of time complexity as we can find median in
linear time and the partition function will always divide the input array
into two halves. But it takes more time on average as median finding has high
constants.
Partition Algorithm
The key process in quickSort is a partition(). There are three common algorithms to partition. All
these algorithms have O(n) time complexity.
1. Naive Partition:
create copy of the array. First put all smaller elements and then all
greater. Finally we copy the temporary array back to original array. This
requires O(n) extra space.
2. Lomuto Partition:This is a simple algorithm, we keep track of
index of smaller elements and keep swapping.
3. Hoare’s Partition: This is the fastest of all. traverse array
from both sides and keep swapping greater element on left with smaller on right
while the array is not partitioned.
EXAMPLE:
The logic is simple, we start from the
leftmost element and keep track of the index of smaller (or equal) elements as i . While traversing, if we find a
smaller element, we swap the current element with arr[i]. Otherwise, we ignore the current element.
Advantages
of Quick Sort
●
It
is a divide-and-conquer algorithm that makes it easier to solve problems.
●
It
is efficient on large data sets.
●
It
has a low overhead, as it only requires a small amount of memory to function.
●
It
is Cache Friendly as we work on the same array to sort and do not copy data to
any auxiliary array.
●
Fastest
general purpose algorithm for large data when stability is not required.
●
It
is tail recursive and hence all the tail call optimization can be done.
Disadvantages
of Quick Sort
●
It
has a worst-case time complexity of O(n2), which occurs when the pivot is
chosen poorly.
●
It
is not a good choice for small data sets.
●
It
is not a stable sort, meaning that if two elements have the same key, their
relative order will not be preserved in the sorted output in case of quick
sort, because here we are swapping elements according to the pivot’s position
(without considering their original positions).
5.4)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 is a popular sorting algorithm
known for its efficiency and stability. It follows the divide-and-conquer
approach to sort a given array of elements.
Here’s a step-by-step explanation of how merge sort works:
1. Divide: Divide the list or array recursively
into two halves until it can no more be divided.
2. Conquer: Each subarray is sorted individually
using the merge sort algorithm.
3. Merge: The sorted subarrays are merged back
together in sorted order. The process continues until all elements from both
subarrays have been merged.
Example:
sort the array or list [38, 27, 43, 10] using Merge Sort
Divide:
●
[38, 27, 43, 10] is divided into [38, 27 ] and [43, 10] .
●
[38, 27] is divided into [38] and [27] .
●
[43, 10] is divided into [43] and [10] .
Conquer:
●
[38] is already sorted.
●
[27] is already sorted.
●
[43] is already sorted.
●
[10] is already sorted.
Merge:
●
Merge [43] and [10] to get [10,43] .
●
Merge [27, 38] and
[10,43] to get the final sorted list
[10, 27, 38, 43]
Therefore, the sorted list
is [10, 27, 38, 43] .
Advantages of Merge Sort:
- Efficient: It has a time complexity of O(n
log n), making it faster than simple algorithms like bubble sort or
insertion sort, especially for large datasets.
- Stable: It maintains the
order of equal elements, which can be useful in certain situations (e.g.,
sorting records by multiple criteria).
- Consistent: It always
performs well, regardless of whether the data is sorted or unsorted
initially.
- Works well with
large data: It is good for sorting large datasets that don’t fit in memory
(e.g., external sorting).
Disadvantages of Merge Sort:
- Requires Extra Space: It needs extra memory for merging, which can be costly in terms
of space.
- Not In-Place: Since it uses
additional memory, it’s not an in-place algorithm like quicksort or bubble
sort.
- Slower for Small
Data: It can be slower than simpler algorithms like insertion sort for
smaller datasets due to overhead.
- Complex to
Implement: It’s more complicated to code compared to simpler sorting
algorithms.
Comments
Post a Comment