Searching and Sorting Algorithms
Assignment
Submitted By:
Ashiqan Roll No: 46 Semester: 3rd
Submitted To:
Ma’am Bisma
Date:
January 11, 2026
Table of Contents
1. Introduction
2. Linear Search
Algorithm Explanation
Pseudocode
C++ Implementation
Complexity Analysis
3. Binary Search
Algorithm Explanation
Pseudocode
C++ Implementation
Complexity Analysis
4. Bubble Sort
Algorithm Explanation
Pseudocode
C++ Implementation
Complexity Analysis
5. Conclusion
6. References
Introduction
This assignment provides a detailed exploration of fundamental searching and sorting
algorithms: Linear Search, Binary Search, and Bubble Sort. These algorithms are
crucial for understanding basic data manipulation techniques in computer science. For
each algorithm, we will cover its operational principles, present pseudocode for
clarity, provide C++ implementations, and analyze its time and space complexity. The
goal is to offer a comprehensive understanding of how these algorithms function and
their efficiency characteristics.
Linear Search
Algorithm Explanation
Linear search, also known as sequential search, is a straightforward method for finding
a target value within a list or array. It works by sequentially checking each element of
the list until a match is found or the entire list has been searched. If the target element
is found, its position (index) is returned; otherwise, a special value (e.g., -1) is returned
to indicate that the element is not present in the list.
Pseudocode
Function LinearSearch(array, target):
For each element at index i in array:
If element at index i is equal to target:
Return i
Return -1
C++ Implementation
#include <iostream>
#include <vector>
int linearSearch(const std::vector<int>& arr, int target) {
for (int i = 0; i < [Link](); ++i) {
if (arr[i] == target) {
return i; // Element found at index i
}
}
return -1; // Element not found
}
int main() {
std::vector<int> myVector = {10, 20, 30, 40, 50};
int targetValue = 30;
int result = linearSearch(myVector, targetValue);
if (result != -1) {
std::cout << "Element " << targetValue << " found at index " <<
result << std::endl;
} else {
std::cout << "Element " << targetValue << " not found in the array."
<< std::endl;
}
targetValue = 99;
result = linearSearch(myVector, targetValue);
if (result != -1) {
std::cout << "Element " << targetValue << " found at index " <<
result << std::endl;
} else {
std::cout << "Element " << targetValue << " not found in the array."
<< std::endl;
}
return 0;
}
Complexity Analysis
Time Complexity:
Best Case: O(1) - The target element is the first element in the list.
Average Case: O(n) - The target element is found in the middle of the list.
Worst Case: O(n) - The target element is the last element or not present in
the list. The algorithm has to check all ‘n’ elements.
Space Complexity: O(1) - Linear search requires a constant amount of extra
space, regardless of the input size.
Binary Search
Algorithm Explanation
Binary search is an efficient algorithm for finding an item from a sorted list of items. It
works by repeatedly dividing the search interval in half. If the value of the search key is
less than the item in the middle of the interval, the algorithm narrows the interval to
the lower half. Otherwise, it narrows it to the upper half. This process continues until
the value is found or the interval is empty.
Pseudocode
Function BinarySearch(array, target):
Set low = 0, high = length(array) - 1
While low <= high:
Set mid = (low + high) / 2
If array[mid] == target:
Return mid
Else If array[mid] < target:
Set low = mid + 1
Else:
Set high = mid - 1
Return -1
C++ Implementation
#include <iostream>
#include <vector>
#include <algorithm> // For std::sort
int binarySearch(const std::vector<int>& arr, int target) {
int low = 0;
int high = [Link]() - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // To prevent potential overflow
if (arr[mid] == target) {
return mid; // Element found
} else if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // Element not found
}
int main() {
std::vector<int> myVector = {10, 50, 30, 40, 20}; // Unsorted initially
std::sort([Link](), [Link]()); // Binary search requires a
sorted array
std::cout << "Sorted array: ";
for (int val : myVector) {
std::cout << val << " ";
}
std::cout << std::endl;
int targetValue = 40;
int result = binarySearch(myVector, targetValue);
if (result != -1) {
std::cout << "Element " << targetValue << " found at index " <<
result << std::endl;
} else {
std::cout << "Element " << targetValue << " not found in the array."
<< std::endl;
}
targetValue = 15;
result = binarySearch(myVector, targetValue);
if (result != -1) {
std::cout << "Element " << targetValue << " found at index " <<
result << std::endl;
} else {
std::cout << "Element " << targetValue << " not found in the array."
<< std::endl;
}
return 0;
}
Complexity Analysis
Time Complexity:
Best Case: O(1) - The target element is the middle element.
Average Case: O(log n) - The search space is halved in each step.
Worst Case: O(log n) - The search space is repeatedly halved until only one
element remains.
Space Complexity: O(1) - Binary search requires a constant amount of extra
space.
Bubble Sort
Algorithm Explanation
Bubble Sort is a simple sorting algorithm that repeatedly steps through the list,
compares adjacent elements, and swaps them if they are in the wrong order. The pass
through the list is repeated until no swaps are needed, which indicates that the list is
sorted. The algorithm gets its name because smaller elements bubble up to the
beginning of the list, while larger elements sink to the end.
Pseudocode
Function BubbleSort(array):
Set n = length(array)
For i from 0 to n-2:
For j from 0 to n-i-2:
If array[j] > array[j+1]:
Swap array[j] and array[j+1]
C++ Implementation
#include <iostream>
#include <vector>
#include <algorithm> // For std::swap
void bubbleSort(std::vector<int>& arr) {
int n = [Link]();
for (int i = 0; i < n - 1; ++i) {
// Last i elements are already in place
for (int j = 0; j < n - i - 1; ++j) {
// Traverse the array from 0 to n-i-1
// Swap if the element found is greater than the next element
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
}
}
}
}
int main() {
std::vector<int> myVector = {64, 34, 25, 12, 22, 11, 90};
std::cout << "Original array: ";
for (int val : myVector) {
std::cout << val << " ";
}
std::cout << std::endl;
bubbleSort(myVector);
std::cout << "Sorted array: ";
for (int val : myVector) {
std::cout << val << " ";
}
std::cout << std::endl;
return 0;
}
Complexity Analysis
Time Complexity:
Best Case: O(n) - The array is already sorted. The algorithm still makes one
pass to confirm no swaps are needed.
Average Case: O(n^2) - The elements are in a random order.
Worst Case: O(n^2) - The array is sorted in reverse order. The algorithm
performs the maximum number of comparisons and swaps.
Space Complexity: O(1) - Bubble Sort requires a constant amount of extra space
for temporary variables.
Conclusion
This assignment has provided a foundational understanding of three essential
algorithms: Linear Search, Binary Search, and Bubble Sort. We have seen that while
Linear Search is simple, its efficiency is limited, especially for large datasets. Binary
Search offers significantly better performance for sorted data due to its divide-and-
conquer approach. Bubble Sort, though easy to understand and implement, is
generally inefficient for practical sorting tasks due to its quadratic time complexity.
The choice of algorithm depends heavily on the characteristics of the data and the
specific requirements of the application, highlighting the importance of complexity
analysis in algorithm selection.
References
1. GeeksforGeeks - Linear Search
2. GeeksforGeeks - Binary Search
3. GeeksforGeeks - Bubble Sort