Searching and Sorting Algorithms
Hey! Welcome back. Today, we’re diving into the absolute bread-and-butter of computer science: Searching and Sorting Algorithms.
Whether you’re searching for a contact on your phone or sorting high scores in a game, these algorithms are what make systems run fast. We’ll learn how to find elements in a list, swap items to arrange them, and break arrays down recursively to sort them in record time.
Searching Algorithms
Searching is all about finding the index of a target value inside a collection. If the target isn’t there, we return -1.
1. Linear Search (Sequential Scan)
Imagine looking for a specific book on a disorganized bookshelf. You start at one end and check each book one-by-one until you find it. That’s Linear Search.
- How It Works: Start at index
0and traverse sequentially. Ifarr[i] == target, returni. If you hit the end, return-1. - Pros: Super simple; works on unsorted lists.
- Cons: Inefficient for large datasets (Time Complexity: $O(N)$).
Example:
#include <iostream>
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; ++i) {
if (arr[i] == target) {
return i; // Target found, return index
}
}
return -1; // Target not found
}
int main() {
int arr[] = {5, 3, 7, 1, 9};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 7;
int result = linearSearch(arr, size, target);
if (result != -1) {
std::cout << "Target " << target << " found at index: " << result << std::endl;
} else {
std::cout << "Target " << target << " not found!" << std::endl;
}
return 0;
}
Output:
Target 7 found at index: 2
2. Binary Search (Divide and Conquer)
Now, imagine your bookshelf is perfectly sorted alphabetically. Instead of scanning one-by-one, you open it right to the middle. If your book comes alphabetically before the middle book, you throw away the right half and search the left half. You repeat this until you find it. That’s Binary Search.
- How It Works:
- Compare target with the middle element.
- If they match, return index.
- If target is smaller, repeat search on left half.
- If target is larger, repeat search on right half.
- Pros: Extremely fast for large datasets (Time Complexity: $O(\log N)$).
- Cons: Requires the array to be sorted beforehand.
graph TD
subgraph Binary Search: Finding 7 in [1, 3, 5, 7, 9]
direction TB
step1[Range: Low=0, High=4 <br/> Mid = 2, Value = 5]
step1 -->|7 > 5: Search Right Half| step2[Range: Low=3, High=4 <br/> Mid = 3, Value = 7]
step2 -->|7 == 7: Found!| match[Return Index: 3]
end
Example:
#include <iostream>
int binarySearch(int arr[], int size, int target) {
int low = 0;
int high = size - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // Avoids potential overflow compared to (low+high)/2
if (arr[mid] == target) {
return mid; // Found!
}
if (arr[mid] < target) {
low = mid + 1; // Discard left half
} else {
high = mid - 1; // Discard right half
}
}
return -1; // Not found
}
int main() {
int arr[] = {1, 3, 5, 7, 9}; // Must be sorted!
int size = sizeof(arr) / sizeof(arr[0]);
int target = 7;
int result = binarySearch(arr, size, target);
if (result != -1) {
std::cout << "Target " << target << " found at index: " << result << std::endl;
} else {
std::cout << "Target " << target << " not found!" << std::endl;
}
return 0;
}
Output:
Target 7 found at index: 3
Sorting Algorithms
Sorting is about organizing unordered collections into a specific order (ascending or descending).
1. Bubble Sort (Adjacent Swaps)
Bubble Sort is a simple algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The largest elements “bubble” up to the end of the array.
graph LR
subgraph Bubble Sort: Swapping Adjacent Elements
direction LR
compare[Compare 5 and 3] -->|5 > 3| swap[Swap: 3, 5]
no_swap[Compare 5 and 7] -->|5 < 7| keep[Keep: 5, 7]
end
Trace of Bubble Sort on [5, 3, 7, 1, 9]:
| Phase | Array State | Description |
|---|---|---|
| Start | [5, 3, 7, 1, 9] | Initial unsorted array. |
| Pass 1 | [3, 5, 1, 7, 9] | Swap 5 and 3, swap 5 and 7 (no), swap 7 and 1. Max element 9 is placed at the end. |
| Pass 2 | [3, 1, 5, 7, 9] | Swap 3 and 5 (no), swap 5 and 1. Second largest element 7 is placed. |
| Pass 3 | [1, 3, 5, 7, 9] | Swap 3 and 1. Array is now sorted! |
Example:
#include <iostream>
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; ++i) {
bool swapped = false;
// Last i elements are already in place
for (int j = 0; j < size - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
// Swap adjacent elements
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// Optimization: If no elements were swapped, array is already sorted
if (!swapped) break;
}
}
int main() {
int arr[] = {5, 3, 7, 1, 9};
int size = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, size);
std::cout << "Sorted Array (Bubble Sort): ";
for (int i = 0; i < size; ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
Output:
Sorted Array (Bubble Sort): 1 3 5 7 9
2. Selection Sort (Minimum Selection)
Selection Sort splits the array into a sorted part and an unsorted part. In each round, it finds the smallest (minimum) element in the unsorted part and swaps it with the first element of the unsorted part.
Trace of Selection Sort on [5, 3, 7, 1, 9]:
| Pass | Unsorted Subarray | Min Found | Swap Target | Resulting Array |
|---|---|---|---|---|
| 1 | [5, 3, 7, 1, 9] | 1 | 5 | [1, 3, 7, 5, 9] |
| 2 | [3, 7, 5, 9] | 3 | 3 (no-op) | [1, 3, 7, 5, 9] |
| 3 | [7, 5, 9] | 5 | 7 | [1, 3, 5, 7, 9] |
| 4 | [7, 9] | 7 | 7 (no-op) | [1, 3, 5, 7, 9] |
Example:
#include <iostream>
void selectionSort(int arr[], int size) {
for (int i = 0; i < size - 1; ++i) {
int minIndex = i;
// Find minimum element in unsorted range
for (int j = i + 1; j < size; ++j) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap minimum with first element of unsorted range
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
int main() {
int arr[] = {5, 3, 7, 1, 9};
int size = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, size);
std::cout << "Sorted Array (Selection Sort): ";
for (int i = 0; i < size; ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
Output:
Sorted Array (Selection Sort): 1 3 5 7 9
3. Merge Sort (Divide and Conquer)
Both Bubble Sort and Selection Sort have $O(N^2)$ complexity, making them sluggish for large arrays. Merge Sort is a far more efficient algorithm that uses the Divide and Conquer paradigm.
It recursively splits the array in half until we get subarrays of size 1 (which are already sorted), and then merges those sorted halves back together.
graph TD
subgraph Merge Sort Tree
direction TB
root["[5, 3, 7, 1, 9]"]
split1_l["[5, 3, 7]"]
split1_r["[1, 9]"]
root --> split1_l
root --> split1_r
split2_l1["[5, 3]"]
split2_l2["[7]"]
split1_l --> split2_l1
split1_l --> split2_l2
split3_l1["[5]"]
split3_l2["[3]"]
split2_l1 --> split3_l1
split2_l1 --> split3_l2
split2_r1["[1]"]
split2_r2["[9]"]
split1_r --> split2_r1
split1_r --> split2_r2
merge1["Merge [5] & [3] -> [3, 5]"]
merge2["Merge [3, 5] & [7] -> [3, 5, 7]"]
merge3["Merge [1] & [9] -> [1, 9]"]
merge4["Final Merge -> [1, 3, 5, 7, 9]"]
end
Example:
#include <iostream>
// Merge helper function
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays
int* L = new int[n1];
int* R = new int[n2];
// Copy data to temp arrays
for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];
// Merge temp arrays back into arr[left..right]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy remaining elements of L[]
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// Copy remaining elements of R[]
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
// Free temp arrays
delete[] L;
delete[] R;
}
// Main Merge Sort recursive function
void mergeSort(int arr[], int left, int right) {
if (left >= right) return; // Base case: 1 element
int mid = left + (right - left) / 2;
// Sort left and right halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge sorted halves
merge(arr, left, mid, right);
}
int main() {
int arr[] = {5, 3, 7, 1, 9};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
std::cout << "Sorted Array (Merge Sort): ";
for (int i = 0; i < size; ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
Output:
Sorted Array (Merge Sort): 1 3 5 7 9
Comparing Searching and Sorting Algorithms
| Algorithm | Type | Best Case Time | Average Case Time | Worst Case Time | Space Complexity |
|---|---|---|---|---|---|
| Linear Search | Search | $O(1)$ | $O(N)$ | $O(N)$ | $O(1)$ |
| Binary Search | Search | $O(1)$ | $O(\log N)$ | $O(\log N)$ | $O(1)$ |
| Bubble Sort | Sort | $O(N)$ | $O(N^2)$ | $O(N^2)$ | $O(1)$ |
| Selection Sort | Sort | $O(N^2)$ | $O(N^2)$ | $O(N^2)$ | $O(1)$ |
| Merge Sort | Sort | $O(N \log N)$ | $O(N \log N)$ | $O(N \log N)$ | $O(N)$ |
Level Up: Extra Practice & Interview Questions
Q1. Write a C++ function that performs a binary search on a sorted array and returns the index of the target value if found, otherwise returns -1.
This reinforces basic recursive or iterative binary lookup implementations.
Code:
#include <iostream>
int searchTarget(const int arr[], int size, int target) {
int l = 0, h = size - 1;
while (l <= h) {
int m = l + (h - l) / 2;
if (arr[m] == target) return m;
if (arr[m] < target) l = m + 1;
else h = m - 1;
}
return -1;
}
int main() {
int arr[] = {2, 4, 6, 8, 10};
std::cout << "Index of 8: " << searchTarget(arr, 5, 8) << std::endl;
std::cout << "Index of 5: " << searchTarget(arr, 5, 5) << std::endl;
return 0;
}
Output:
Index of 8: 3
Index of 5: -1
Q2. Write a C++ function that sorts an array using the selection sort algorithm.
This practices locating structural minimum indexes and swapping.
Code:
#include <iostream>
void doSelectionSort(int arr[], int size) {
for (int i = 0; i < size - 1; ++i) {
int minIdx = i;
for (int j = i + 1; j < size; ++j) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
if (minIdx != i) {
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
doSelectionSort(arr, 5);
std::cout << "Selection Sorted: ";
for (int i = 0; i < 5; ++i) std::cout << arr[i] << " ";
std::cout << std::endl;
return 0;
}
Output:
Selection Sorted: 11 12 22 25 64
Q3. Write a C++ function that sorts an array using the bubble sort algorithm.
This practices implementing the adjacent bubble-swapper with an early exit boolean check.
Code:
#include <iostream>
void doBubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; ++i) {
bool swapped = false;
for (int j = 0; j < size - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}
int main() {
int arr[] = {3, 9, 2, 8, 1};
doBubbleSort(arr, 5);
std::cout << "Bubble Sorted: ";
for (int i = 0; i < 5; ++i) std::cout << arr[i] << " ";
std::cout << std::endl;
return 0;
}
Output:
Bubble Sorted: 1 2 3 8 9
quiz Test Your Understanding
What is the average time complexity of Merge Sort?
Merge Sort is a divide-and-conquer sorting algorithm with a consistent O(n log n) time complexity in best, average, and worst cases.