Introduction
In this lecture, we apply the Brute Force (BF) algorithm design technique to two classical problems:
-
Sorting – arranging elements in a particular order (ascending/descending).
-
String Matching – searching for a substring within a text.
The Brute Force approach offers simple yet foundational methods such as Selection Sort, Bubble Sort, and Brute-Force String Matching, which serve as the basis for understanding more advanced techniques later in the course.
Table of Contents
-
Brute Force Algorithm Design Recap
-
Problem 1: Brute Force Sorting
-
Problem Statement
-
Selection Sort Algorithm
-
Bubble Sort Algorithm
-
Time Complexity Analysis
-
-
Problem 2: Brute Force String Matching
-
Problem Statement
-
Algorithm and Example
-
Time Complexity
-
-
Summary
-
Conclusion
Brute Force Algorithm Design Recap
The Brute Force technique follows a direct, exhaustive approach:
-
Test every possible solution.
-
Choose the correct or best one based on the problem conditions.
Although not efficient for large inputs, it is easy to design, understand, and serves as a baseline for optimization.
Problem 1: Brute Force Sorting
Problem Statement
Given a list of n orderable items (e.g., numbers or strings), rearrange them in increasing order.
Example:
Input: <5, 3, 2, 8, 3>
Output: <2, 3, 3, 5, 8>
Brute force idea → compare all elements, repeatedly find the smallest (or largest), and place it in its correct position.
Selection Sort Algorithm
Explanation:
-
Find the smallest element and place it at the start.
-
Repeat for the remaining unsorted part of the list.
-
Requires n−1 passes.
Example:
Initial: [89, 45, 68, 90, 29, 34, 17]
After sorting: [17, 29, 34, 45, 68, 89, 90]
Bubble Sort Algorithm
Explanation:
-
Compare adjacent elements and swap if out of order.
-
Largest elements “bubble up” to the end after each pass.
Example:
Input: [7, 5, 9, 3, 6, 21, 2]
Sorted (after passes): [2, 3, 5, 6, 7, 9, 21]
Time Complexity Analysis
| Case | Description | Time Complexity |
|---|---|---|
| Best Case | Already sorted list | O(n) |
| Average Case | Random list | O(n²) |
| Worst Case | Reverse sorted list | O(n²) |
Bubble Sort performs n(n−1)/2 comparisons, so it’s inefficient for large datasets but simple to implement.
Problem 2: Brute Force String Matching
Problem Statement
Given:
-
Text (T): A long string of n characters.
-
Pattern (P): A shorter string of m characters (m ≤ n).
Goal: Find if P occurs in T, and return the index of the first match or −1 if not found.
Example:
Algorithm and Example
Explanation:
-
Try aligning pattern P with each substring of T.
-
Compare characters one by one.
-
If mismatch → shift P by one position and repeat.
-
If all characters match → return the starting index.
Example Walkthrough:
Text: nobody_noticed_him
Pattern: not
Comparisons:
Time Complexity
| Case | Description | Complexity |
|---|---|---|
| Worst Case | Pattern nearly matches but fails at last char each time | O(nm) |
| Average Case | Random text | O(n + m) ≈ O(n) |
| Best Case | Match at first position | O(m) |
Summary
| Algorithm | Technique | Complexity | Type |
|---|---|---|---|
| Selection Sort | Brute Force | O(n²) | Sorting |
| Bubble Sort | Brute Force | O(n²) | Sorting |
| String Matching | Brute Force | O(nm) | Searching |
-
Selection Sort: repeatedly selects the smallest element.
-
Bubble Sort: repeatedly swaps adjacent elements.
-
String Matching: sequentially compares all possible alignments.
Conclusion
The Brute Force design approach is simple yet forms the foundation of algorithm design. Though inefficient for large-scale data, it offers clarity and is ideal for teaching the fundamentals of sorting and searching. The algorithms learned here—Selection Sort, Bubble Sort, and Brute Force String Matching—help students transition toward more optimized strategies like Divide and Conquer, Greedy, and Dynamic Programming in upcoming lectures. Here is the lecture Lecture # 14_new
