Ch 3.1 brute force, exhaustive search, & selection sort Flashcards
a straightforward approach to solving a problem, usually
directly based on the problem statement and definitions of the concepts
involved
brute force
consider the exponentiation problem: compute an for a
nonzero number a and a nonnegative integer n. Although this problem might
seem trivial, it provides a useful vehicle for illustrating several algorithm design
strategies, including the brute force. (Also note that computing an mod m for some
large integers is a principal component of a leading encryption algorithm.) By the
definition of exponentiation,
a^n = a* …* a (n times)
This suggests simply computing an by multiplying 1 by a n times
the consecutive integer checking algorithm for computing gcd(m, n) and the definition-based algorithm for matrix multiplication are examples of what algorithm?
brute force
it seems to be the only general approach for which it
is more difficult to point out problems it cannot tackle. Second, for some important problems—e.g., sorting, searching, matrix multiplication, string matching—
the brute-force approach yields reasonable algorithms of at least some practical value with no limitation on instance size. Third, the expense of designing a
more efficient algorithm may be unjustifiable if only a few instances of a problem need to be solved and a brute-force algorithm can solve those instances with
acceptable speed. Fourth, even if too inefficient in general, a brute-force algorithm can still be useful for solving small-size instances of a problem. Finally,
a brute-force algorithm can serve an important theoretical or educational purpose as a yardstick with which to judge more efficient alternatives for solving a
problem.
brute force
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. Then we scan the list, starting with the second element,
to find the smallest among the last n − 1 elements and exchange it with the second
element, putting the second smallest element in its final position
on the ith pass through the list, which we number from 0 to n − 2, the algorithm searches
for the smallest item among the last n − i elements and swaps it with Ai
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 next pass bubbles up the second largest element, and so on, until
after n − 1 passes the list is sorted.
brute force algorithms
Brute force algorithms are straightforward methods of solving a problem that try every possibility rather than advanced techniques to improve efficiency.
Directly do the problem without considering time and space performance
Advantages
Simple and general (?)
Iterating through all possible solutions. Show that no other solutions exist
Usually efficient for small input size
Disadvantages
Often takes to much time
Brute force algorithms
Sorting
Bubble sort
Selection sort
Searching
Sequential search
Exhaustive search
String matching
Geometric problems
Closest pair, Convex Hull
insertion sort
insertion_sort(A)
for j = 2 to length[A]
{
key = A[j]
// insert A[j] into the sorted sequence A[1..j-1]
i = j – 1
while i>0 and A[i] > key
{
A[i+1] = A[i]
i = i – 1
}// end while
A[i+1] = key
}//end for
bubble sort
Swap pairwise elements which are out of order, from beginning to end
In each round, at least one element is in rightful position
bubble sort algorithm
Data Structure: Array
Input: A[0..n-1]
for i=0 to n-1 do
for j=i to n-1 do
if A[j] > A[j+1]
swap A[j] and A[j+1]
end;
end;
bubble sort c++
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
{
if (A[i] > A[j])
{
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
20 45 90 8
8 45 90 20
8 20 90 45
8 20 45 90
optimized bubble sort c++
flag = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n-1; j++)
{
if (A[j] > A[j+1])
{
temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
flag = 1; // if swapping occurs
}
}
if (flag == 0)
break; // the input list already sorted, no need for the inner loop
}
Sequential Search Algorithm
Data Structure: Array
Input A[0..n−1]
Target key: K
i ← 0
while A[i] K do
i = i + 1
end;
if (i<n)
“Found” at i
else
“not found“;
brute force string matching
Given a string of n characters called the text and a string of m characters (m n) called the pattern, find a substring of the text that matches the pattern.
