Brute Force and Exhaustive Search - Coggle Diagram
Brute Force and Exhaustive Search
Brute force is a straightforward approach to solving a problem, usually directly based on the problem statement and definitions of the concepts
We start selection sort by scanning the entire given list to find its smallest element and exchange it with the first element, putting the smallest element in its final position in the sorted list
Another brute-force application to the sorting problem is to compare adjacent elements of the list and exchange them if they are out of order. By doing it repeatedly, we end up “bubbling up” the largest element to the last position on the list.
The decrease-and-conquer technique is based on exploiting the relationship between a solution to a given instance of a problem and a solution to its smaller instance. There are three major variations of decrease-and-conquer:
decrease by a constant
In the decrease-by-a-constant variation, the size of an instance is reduced by the same constant on each iteration of the algorithm Typically, this constant is equal to one
decrease by a constant factor
The decrease-by-a-constant-factor technique suggests reducing a problem instance by the same constant factor on each iteration of the algorithm. In most applications, this constant factor is equal to two.
variable size decrease
the variable-size-decrease variety of decrease-and-conquer, the
size-reduction pattern varies from one iteration of an algorithm to another.
Insertion Sort or straight insertion sort
Divide-and-conquer algorithms work according to the
following general plan:
A problem is divided into several subproblems of the same type, ideally of about equal size.
The subproblems are solved (typically recursively, though sometimes a different algorithm is employed, especially when subproblems become small enough).
If necessary, the solutions to the subproblems are combined to get a solution to the original problem.
The merging of two sorted arrays can be done as follows. Two pointers (array indices) are initialized to point to the first elements of the arrays being merged.