Brute force is a straightforward approach to solving a problem, usually directly based on the problem statement and definition...(Levitin 2007)
The author attempts to give some motivation to this chapter:
1. Brute force is applicable to a wide variety of problems.
2. For some problems does generate reasonable algorithm.
3. If the problem is only infrequently solved then the expense of developing a better algorithm is not justified.
4. The brute force algorithm may be good for small problem size.
5. Brute force can be used for comparison of more sophisticated algorithms.
Based on sequentially finding the smallest elements
Algorithm SelectionSort(A[0...n-1])
for i ← 0 to n-2 do
min ← i
for j ← i+1 to n-1
do
if A[j] < A[min] then min ← j
swap A[i] and A[min]
1. Problem size is n, array length
2. Basic operation is if test
3. There is no difference between best or worst case
4. The count
C(n) = ∑i=0n-2 ∑ j=i+1n-1 1
5. Solve
C(n) = ∑i=0n-2 [(n-1) - (i+1) + 1] = ∑i=0n-2 [n-1- i]
C(n) = n(n-1)/2 ε Θ(n2)
Note that the number of swap is n-1
Note the sort is in-place and stable.
Based on consecutive swapping adjacent pairs. This causes a slow migration of the smallest elements to the left of the array.
Algorithm BubbleSort(A[0...n-1])
for i ← 0 to n-2 do
for j ← 0 to
n-2-i do
if A[j+1] < A[j] then swap A[j+1] and A[j]
No difference between worst and best case
Number of Comparisons
C(n) = ∑i=0n-2 ∑ j=0n-2-i 1
= ∑i=0n-2[(n-2-i) -0 +1] = ∑i=0n-2[n-1-i] = n(n-1)/2 ε Θ(n2)
Also in-place and stable
The algorithm can be improved. If no swaps are made through one cycle of the outer loop then the array is sorted. Then best case is linear.
Appending the search key to the end of the list guarantees the search will be successful, so we can use the whole loop.
Algorithm SequentialSearch2(A[0...n], K)
// K is the search key and A has n elements
A[n] ← K
while A[i] ≠ K do
i++
if i < n then return i
else return -1
What is the worst and best case cost?
Another improvement is to use a sorted array A[0...n-1], how? What is the worst and best case?
Searching for a pattern, P[0...m-1], in text, T[0...n-1]
Algorithm BruteForceStringMatch(T[0...n-1], P[0...m-1])
for i ← 0 to n-m do
j ← 0
while j < m and P[j] = T[i+j] do
j++
if j = m then return i
return -1
Illustrate the algorithm
Worst case when a shift is not made until the m-th comparison, so Θ(nm)
Typically shift is made early then Average case Θ(n) or for m << n