Unit 2
Fundamental Algorithm Strategies
1. Brute-force Technique :
• Brute force is a straightforward method used in algorithmic problem-solving that checks
every possible solution until the correct one is found.
• The brute force algorithm tries out all the possibilities till a satisfactory solution is not
found.
• Many problems solved in day to day life using the brute force strategy.
Example :- Exploring all the paths to a nearby market to find the minimum shortest path.
Advantages of Brute Force Technique :
• The brute-force approach is a guaranteed way to find the correct solution by listing all the
possible candidate solutions for the problem.
• It is known for its simplicity and can serve as a comparison benchmark.
• This type of algorithm is applicable to a wide range of domains.
• The brute force method is ideal for solving small and simpler problems.
Disadvantages of Brute Force Technique :
• It is an inefficient algorithm as it requires solving each and every step.
Common Application and Examples :
• Searching (Linear Search) :- Each element in a list is checked one by one until the target is
found.
• Sorting :
a. Selection sort : Repeatedly finds the smallest element in the unsorted portion of an array
and swaps it with first element of the portion.
b. Bubble sort : Repeatedly compare adjacent elements and swaps them if they are in the
wrong order.
Q1. Brute force Technique in Linear Search
Problem
Given an array of elements, find the position of a given key format.
Linear Search is a simple searching algorithm where each element of the array is checked one
by one from the beginning until the required element (key) is found or the list ends.
Example
Suppose:
Array A = [10, 25, 30, 45, 50]
Key = 30
Step-by-step:
Compare 10 with 30 → Not equal
Compare 25 with 30 → Not equal
Compare 30 with 30 → Match found
Result: Position = 2 (index starts from 0)
Algorithm: Linear Search
Linear_Search(A, n, key)
1. for i = 0 to n-1
2. if A[i] == key
3. return i
4. return -1
C Program for Linear Search
#include <stdio.h>
int linearSearch(int A[], int n, int key) {
for(int i = 0; i < n; i++) {
if(A[i] == key) {
return i; // element found
}
}
return -1; // element not found
}
int main() {
int A[] = {10, 25, 30, 45, 50};
int n = 5;
int key;
printf("Enter the element to search: ");
scanf("%d", &key);
int result = linearSearch(A, n, key);
if(result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found\n");
}
return 0;
}
Time and Space Complexity of Linear Search
Time Complexity
Best Case: O(1)
The element is found at the first position.
Only one comparison is needed.
Average Case: O(n)
The element is found somewhere in the middle.
About n/2 comparisons are required.
Worst Case: O(n)
The element is at the last position or not present in the array.
All n elements are checked.
Space Complexity: O(1)
Q.2: Selection Sort (Brute Force Technique)
Definition:
Selection Sort is a simple sorting algorithm that repeatedly finds the smallest element from
the unsorted part of the array and places it at the beginning.
How it Works (Steps in Sentences)
In the first step, the smallest element from the entire array is found and swapped with
the first element.
In the second step, the smallest element from the remaining unsorted part is found and
swapped with the second element.
This process continues, reducing the unsorted portion each time.
Example
Array: A = [64, 25, 12, 22, 11]
Pass 1:
Find smallest → 11
Swap with first element
Result → [11, 25, 12, 22, 64]
Pass 2:
Find smallest from remaining → 12
Swap with second element
Result → [11, 12, 25, 22, 64]
Pass 3:
Find smallest → 22
Swap
Result → [11, 12, 22, 25, 64]
Pass 4:
Find smallest → 25
Swap
Result → [11, 12, 22, 25, 64]
Final Sorted Array: [11, 12, 22, 25, 64]
Algorithm: Selection Sort
Selection_Sort(A, n)
1. for i = 0 to n-2
2. min = i
3. for j = i+1 to n-1
4. if A[j] < A[min]
5. min = j
6. swap A[i] and A[min]
C Program for Selection Sort
#include <stdio.h>
void selectionSort(int A[], int n) {
int i, j, min, temp;
for(i = 0; i < n-1; i++) {
min = i;
for(j = i+1; j < n; j++) {
if(A[j] < A[min]) {
min = j;
}
}
// Swap
temp = A[i];
A[i] = A[min];
A[min] = temp;
}
}
int main() {
int A[] = {64, 25, 12, 22, 11};
int n = 5;
selectionSort(A, n);
printf("Sorted array:\n");
for(int i = 0; i < n; i++) {
printf("%d ", A[i]);
}
return 0;
}
Time Complexity
Best Case: O(n²)
Worst Case: O(n²)
Space Complexity: O(1) (Constant Space)