Bubble Sort
#include <bits/stdc++.h>
using namespace std;
// Bubble Sort function
void bubble(auto& arr){
int n = arr.size();
// Outer loop runs n times
for(int i = 0 ; i < n ; i++){
bool swaped = false; // to check if swapping happened
// Inner loop compares adjacent elements
for(int j = 0 ; j < n - i - 1 ; j++){
// if left element is bigger than right element → swap
if(arr[j] > arr[j+1]){
swap(arr[j], arr[j+1]);
swaped = true;
// If no swapping → array already sorted → stop early
if(!swaped)
break;
int main() {
vector<int> arr = {5,1,2,4,9,11};
// Call bubble sort
bubble(arr);
// Print sorted array
for(auto& vec : arr)
cout << vec << " ";
Time Complexity
Best:- O(n), Average:- O(n^2), Worst:- O(n^2)
Practice Problem:- https://www.geeksforgeeks.org/problems/bubble-sort/1
Selection Sort
#include <bits/stdc++.h>
using namespace std;
// Selection Sort function
void selection_sort(vector<int>& arr){
int n = arr.size();
// Move boundary of unsorted array
for(int i = 0 ; i < n ; i++){
int min_val = i; // assume first element is minimum
// Find the actual minimum element
for(int j = i + 1 ; j < n ; j++){
if(arr[j] < arr[min_val])
min_val = j;
}
// Swap minimum with first element
swap(arr[i], arr[min_val]);
int main() {
vector<int> arr = {5,3,1,7,9,10};
// Call selection sort
selection_sort(arr);
// Print sorted array
for(auto& vec : arr)
cout << vec << " ";
}
Best:- O(n^2), Average:- O(n^2), Worst:- O(n^2)
Practice Problem:- https://www.geeksforgeeks.org/problems/selection-sort/1
Insertion Sort
#include <bits/stdc++.h>
using namespace std;
// Insertion Sort function
void insertion_sort(auto& arr){
for(int i = 0 ; i < arr.size() ; i++){
int key = arr[i]; // pick current element
int j = i - 1;
// Shift elements that are greater than key
while(j >= 0 && arr[j] > key){
arr[j+1] = arr[j];
j = j - 1;
// Place key at correct position
arr[j+1] = key;
int main() {
vector<int> arr = {4,1,2,6,7,3};
// Call insertion sort
insertion_sort(arr);
// Print sorted array
for(auto& vec : arr)
cout << vec << " ";
Best:- O(n), Average:- O(n^2), Worst:- O(n^2)
Practice Problem:- https://www.geeksforgeeks.org/problems/insertion-sort/1
Counting Sort
#include <bits/stdc++.h>
using namespace std;
// Counting Sort function
void counting_sort(auto& arr){
unordered_map<int,int> mp;
// Find maximum & minimum element
int maxE = *max_element(arr.begin(), arr.end());
int minE = *min_element(arr.begin(), arr.end());
// Count frequency of each number
for(auto& vec : arr)
mp[vec]++;
int j = 0;
// Place elements back in sorted order
for(int i = minE ; i <= maxE; i++){
while(mp[i] > 0){
arr[j] = i;
mp[i]--;
j++;
}
}
int main() {
vector<int> arr = {9,4,2,10,11,3};
// Call counting sort
counting_sort(arr);
// Print sorted array
for(auto& vec : arr)
cout << vec << " ";
}
Best:- O(n+k), Average:- O(n+k), Worst:- O(n+k)
Practice Problem:- https://leetcode.com/problems/sort-an-array/
75. Sort Colors
class Solution {
public:
void sortColors(vector<int>& nums) {
int i = 0;
int j = 0;
int k = nums.size()-1;
while(i<=k){
if(nums[i]==1)
i++;
else if(nums[i]==2){
swap(nums[i],nums[k]);
k--;
}else{
swap(nums[i],nums[j]);
i++;
j++;
};
T.C :- O(n)
242. Valid Anagram
Bruteforce T.C O( (m+n)log(m+n))
class Solution {
public:
bool isAnagram(string s, string t) {
sort(s.begin(),s.end());
sort(t.begin(),t.end());
if(s==t)
return true;
else
return false;
};
Optimized T.C : - O(N)
class Solution {
public:
bool isAnagram(string s, string t) {
int freq[256] = {0};
for(int i = 0 ; i < s.size() ;i++)
freq[s[i]]++;
for(int i = 0 ; i < t.size() ; i++)
freq[t[i]]--;
for(int i = 0 ; i < 256 ; i++)
if(freq[i]!=0)
return false;
return true;
};
