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}_{=0}^{n}^{-2} ∑ _{j}_{=i+1}^{n}^{-1}
1

5. Solve

*C*(*n*) = ∑_{i}_{=0}^{n}^{-2} [(*n*-1) - (*i*+1) + 1] = ∑_{i}_{=0}^{n}^{-2}
[*n*-1- *i*]

*C*(*n*) = *n*(*n*-1)/2 ε Θ(*n*^{2})

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}_{=0}^{n}^{-2} ∑ _{j}_{=0}^{n}^{-2-i} 1

= ∑_{i}_{=0}^{n}^{-2}[(*n*-2-*i*)
-0 +1] = ∑_{i}_{=0}^{n}^{-2}[*n*-1-*i*]
= *n*(*n*-1)/2 ε Θ(*n*^{2})

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*