π Day 4 of DSA Journey: Sorting It Out β Bubble, Selection & Insertion Sort
Welcome to Day 4 of our DSA adventure!
Youβve learned how to search β now itβs time to sort.
Sorting is one of the most common interview topics and also a core building block for many algorithms (including Binary Search π).
π¦ What Is Sorting?
Sorting means arranging data in a specific order, usually ascending or descending.
Example:
Unsorted: [5, 1, 4, 2, 8]
Sorted: [1, 2, 4, 5, 8]
1. π«§ Bubble Sort
Compare adjacent elements and swap if they're in the wrong order.
Repeat until the array is sorted.
void bubbleSort(int arr[], int n) {
for(int i = 0; i < n-1; i )
for(int j = 0; j < n-i-1; j )
if(arr[j] > arr[j 1])
swap(arr[j], arr[j 1]);
}
Time: O(nΒ²)
Space: O(1)
β
Easy to understand
β Not efficient for large arrays
2. π¨ Selection Sort
Find the minimum element and place it at the beginning.
void selectionSort(int arr[], int n) {
for(int i = 0; i < n-1; i ) {
int minIdx = i;
for(int j = i 1; j < n; j )
if(arr[j] < arr[minIdx])
minIdx = j;
swap(arr[i], arr[minIdx]);
}
}
Time: O(nΒ²)
Space: O(1)
β
Good when memory writes are costly
β Still slow for big inputs
3. ποΈ Insertion Sort
Pick an element and insert it into its correct position in the sorted part.
void insertionSort(int arr[], int n) {
for(int i = 1; i < n; i ) {
int key = arr[i];
int j = i - 1;
while(j >= 0 && arr[j] > key) {
arr[j 1] = arr[j];
j--;
}
arr[j 1] = key;
}
}
Time: O(nΒ²) but O(n) for nearly sorted
Space: O(1)
β
Great for small or partially sorted arrays
π§© Challenge of the Day:
> βοΈ Write all 3 sorting algorithms from scratch and sort this array:
[64, 25, 12, 22, 11]
Tomorrow, weβll explore the efficient sorts β Merge Sort & Quick Sort β and understand why they're used in real-life systems.
Keep coding,
Smit π¨βπ»