Sorting: What Is It?
Sorting is the process of placing data according to one or more criteria in a certain order, usually either descending (biggest → smallest) or ascending (smallest → largest).
Why Does Sorting Matter in Practical Uses?
In computer science, sorting algorithms are vital because they help with effective data organization. Sorting is used behind the scenes everywhere, from refining social media feeds to powering search engines.
- Faster Searching: Binary Search and other effective searches are made possible by sorted data.
- Improved User Experience: Products are shown in e-commerce apps according to factors like price and rating.
- Effective Processing: Sorted data is necessary for many algorithms to function better.
- Clear Visualization: Charts and trends are easier to comprehend when data is sorted.
- Real-World Use Cases: Healthcare (organized appointments), Banking (organized transactions), etc.
The table below shows the time complexity, stability, and other properties of popular sorting algorithms. It helps to quickly compare which algorithm to use based on the problem requirements.
Introduction to Bubble Sort
Bubble Sort is one of the simplest and easiest-to-understand sorting algorithms. It is usually the first algorithm taught to beginners due to its clear logic and step-by-step process.
How it works:
- Compare adjacent elements.
- If the current element is greater than the next, swap them.
- After each pass, the largest element “bubbles up” to its correct position at the end.
- Repeat until no swaps are needed (array is sorted).
Bubble Sort Example – Step-by-Step Dry Run
👉 Input Array: [64, 34, 25, 12, 22, 11, 90]
Pass 1 (i = 0)
Largest element 90 is placed at the end.
Pass 2 (i = 1)
Now last element (90) is already sorted, so we check till n-2.
Second largest element 64 is now in place.
Pass 3 (i = 2)
Check till n-3 (last 2 sorted).
Third largest element 34 is fixed.
Pass 4 (i = 3)
Check till n-4.
25 is in position.
Pass 5 (i = 4)
Check till n-5.
22 is placed.
Pass 6 (i = 5)
Check till n-6.
Compare 11 & 12 → no swap.
Already sorted → algorithm stops.
Final Sorted Array:
[11, 12, 22, 25, 34, 64, 90]
Bubble Sort in C++
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
bool swapped = false; // Optimization: check if swap happens
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
// If no swaps in this pass, array is already sorted
if (!swapped)
break;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
printArray(arr, n);
bubbleSort(arr, n);
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
Time and Space Complexity
- Best Case (Already Sorted): O(n)
- Worst Case: O(n²)
- Average Case: O(n²)
- Space Complexity: O(1) (in-place)
- Stability: ✅ Yes (does not change relative order of equal elements)
Top comments (0)