Bubble Sort
Bubble Sort is one of the simplest ways to arrange (sort) numbers in
ascending or descending order. Think of it as making bubbles in water
where the heavier (or bigger) bubbles slowly rise to the top. In Bubble
Sort, we compare two numbers, swap them if they are in the wrong
order, and keep repeating this process until everything is sorted.
How It Works (Step by Step)
1. Start with the first two numbers.
2. Compare them:
o If the first number is bigger, swap them so the bigger
number moves to the right.
o If the first number is smaller, do nothing.
3. Move to the next pair of numbers and repeat Step 2.
4. After one complete pass (going through all the numbers), the
biggest number will be in the correct place (end of the list).
5. Repeat the same process for the remaining unsorted numbers until
the whole list is sorted.
Example
Suppose we want to sort the numbers [5, 3, 8, 2] in ascending order:
1. Compare 5 and 3 → Swap → [3, 5, 8, 2]
2. Compare 5 and 8 → Do nothing → [3, 5, 8, 2]
3. Compare 8 and 2 → Swap → [3, 5, 2, 8]
Now, the largest number (8) is in the correct place. Repeat the process
for the remaining list.
Second pass:
1. Compare 3 and 5 → Do nothing → [3, 5, 2, 8]
2. Compare 5 and 2 → Swap → [3, 2, 5, 8]
Third pass:
1. Compare 3 and 2 → Swap → [2, 3, 5, 8]
Now the list is fully sorted.
C++ Code for Bubble Sort
cpp
Copy code
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) { // Outer loop for
passes
for (int j = 0; j < n - i - 1; j++) { // Inner loop for
comparisons
if (arr[j] > arr[j + 1]) { // Compare
adjacent elements
swap(arr[j], arr[j + 1]); // Swap if in
wrong order
}
}
}
}
int main() {
int arr[] = {5, 3, 8, 2};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Diagram for Bubble Sort
Initial Array:
csharp
Copy code
[5, 3, 8, 2]
First Pass:
1. Compare 5 and 3 → Swap → [3, 5, 8, 2]
2. Compare 5 and 8 → No Swap → [3, 5, 8, 2]
3. Compare 8 and 2 → Swap → [3, 5, 2, 8]
Second Pass:
1. Compare 3 and 5 → No Swap → [3, 5, 2, 8]
2. Compare 5 and 2 → Swap → [3, 2, 5, 8]
Third Pass:
1. Compare 3 and 2 → Swap → [2, 3, 5, 8]
Final Sorted Array:
csharp
Copy code
[2, 3, 5, 8]
Selection Sort
Selection Sort works by finding the smallest number in the list and
moving it to its correct position. After placing the smallest number, the
process continues with the next smallest number.
How It Works
1. Find the smallest number in the list and swap it with the first
number.
2. Move to the next position and find the next smallest number.
3. Repeat until the whole list is sorted.
Example
Sort [5, 3, 8, 2]:
1. Find the smallest number (2) → Swap with the first → [2, 3, 8, 5]
2. Find the next smallest number (3) → Already in place → [2, 3, 8,
5]
3. Find the next smallest number (5) → Swap with 8 → [2, 3, 5, 8]
Final Array: [2, 3, 5, 8]
C++ Code for Selection Sort
cpp
Copy code
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // Find the index of the smallest
element
}
}
swap(arr[i], arr[minIndex]); // Swap smallest element
with current position
}
}
int main() {
int arr[] = {5, 3, 8, 2};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
Binary Search
Binary Search is a way to quickly find a value in a sorted list by
dividing the search space in half repeatedly.
How It Works
1. Start with the middle number.
2. If the middle number is the target, stop.
3. If the target is smaller than the middle, search the left half.
4. If the target is larger, search the right half.
5. Repeat until the target is found or the list is empty.
Example
Find 5 in the sorted array [2, 3, 5, 8]:
1. Middle number is 3 → 5 is larger → Search right half → [5, 8]
2. Middle number is 5 → Found the target!
C++ Code for Binary Search
cpp
Copy code
#include <iostream>
using namespace std;
int binarySearch(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid; // Target found
else if (arr[mid] < target) left = mid + 1; // Search
right half
else right = mid - 1; // Search left half
}
return -1; // Target not found
}
int main() {
int arr[] = {2, 3, 5, 8};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 5;
int result = binarySearch(arr, n, target);
if (result != -1)
cout << "Target found at index: " << result << endl;
else
cout << "Target not found." << endl;
return 0;
}
Comparison of Algorithms
Algorithm Best for Time Complexity
Bubble Sort Simple sorting O(n²)
Selection Sort Simple sorting O(n²)
Binary Search Fast searching (sorted) O(log n)
Each algorithm has its unique purpose, with Binary Search being the
fastest when the data is sorted.
Messages beyond this point are only visible to you
