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