[go: up one dir, main page]
Scribd
Upload
17 views4 pages

Brute Force Applications Sorting Strung Match

The document discusses brute force algorithms for sorting and string matching, highlighting their applicability to various problems and their simplicity. It details selection sort and bubble sort algorithms, including their operations and complexities, as well as a sequential search method. Additionally, it presents a brute-force string matching algorithm to find a pattern within a text.

Uploaded by

Chitra
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
17 views4 pages

Brute Force Applications Sorting Strung Match

The document discusses brute force algorithms for sorting and string matching, highlighting their applicability to various problems and their simplicity. It details selection sort and bubble sort algorithms, including their operations and complexities, as well as a sequential search method. Additionally, it presents a brute-force string matching algorithm to find a pattern within a text.

Uploaded by

Chitra
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

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

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.

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-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.

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

You might also like