# Brute Force Sorting and String Matching

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.

## Brute Force Sorting

### Selection sort

Based on sequentially finding the smallest elements

Algorithm SelectionSort(A[0...n-1])

for i ← 0 to n-2 do

mini

for ji+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-2j=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.

### Bubble Sort

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-2j=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.

## Sequential Searching

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?

## Brute-Force String Matching

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