ASSIGNMENT 1

Implementation of Insertion, Selection and Bubble sort

Given a string s, sort it in decreasing order based on the frequency of the characters .The
frequency of a character is the number of times it appears in the string. Return the sorted string
. If there are multiple answers, return any of them.

Code:-
Explanation:-
This problem requires sorting the characters of a string in descending order based on how
frequently each character appears. Characters with higher frequencies should come first, and if
multiple characters have the same frequency, their order relative to each other does not matter.
The solution involves counting character frequencies, sorting them, and constructing the result
string accordingly.

//Bubble Sort
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

string frequencySortBubble(string s) {
unordered_map<char, int> freq_map;
for (char c : s) {
freq_map[c]++;
}

int n = s.size();
for (int i = 0; i < n; i++) {
bool swapped = false;
for (int j = 0 ; j < n - i – 1 ; j++) {
if (freq_map[s[j]] < freq_map[s[j + 1]]) {
swap(s[j], s[j + 1]);
swapped = true;

VANDNA KAUR(24124119) 1
 }
}
if (!swapped) break;
}
return s;
}

Dry Run:-
Initial array: ['t', 'r', 'e', 'e']
Compare based on frequencies: 1, 1, 2, 2
Pass 1:
 Compare index 0 ('t':1) and 1 ('r':1) → No swap (1 == 1)
 Compare index 1 ('r':1) and 2 ('e':2) → Swap (1 < 2)
Array: ['t', 'e', 'r', 'e']
 Compare index 2 ('r':1) and 3 ('e':2) → Swap (1 < 2)
Array: ['t', 'e', 'e', 'r']
Pass 2:
 Compare index 0 ('t':1) and 1 ('e':2) → Swap (1 < 2)
Array: ['e', 't', 'e', 'r']
 Compare index 1 ('t':1) and 2 ('e':2) → Swap (1 < 2)
Array: ['e', 'e', 't', 'r']
 Compare index 2 ('t':1) and 3 ('r':1) → No swap (1 == 1)
Final Result: "eetr"

//selection sort
string frequencySortSelection(string s) {
unordered_map<char, int> freq_map;
for (char c : s) {
freq_map[c]++;
}

int n = s.size();

VANDNA KAUR(24124119) 2
 for (int i = 0; i < n; i++) {
int max_idx = i;
for (int j = i + 1; j < n; j++) {
if (freq_map[s[j]] > freq_map[s[max_idx]]) {
max_idx = j;
}
}
swap(s[i], s[max_idx]);
}
return s;
}

Dry Run:-
Initial array: ['t', 'r', 'e', 'e']
Find max frequency element in unsorted portion
Iteration 1 (i=0):
 Unsorted: [0:3] → ['t','r','e','e']
 Max frequency: 'e' (freq=2) at index 2
 Swap index 0 ('t') with index 2 ('e')
Array: ['e', 'r', 't', 'e']
Iteration 2 (i=1):
 Unsorted: [1:3] → ['r','t','e']
 Max frequency: 'e' (freq=2) at index 3
 Swap index 1 ('r') with index 3 ('e')
Array: ['e', 'e', 't', 'r']
Iteration 3 (i=2):
 Unsorted: [2:3] → ['t','r']
 Both have frequency=1, no swap needed
Final Result: "eetr"

VANDNA KAUR(24124119) 3
//insertion sort
string frequencySortInsertion(string s) {
unordered_map<char, int> freq_map;
for (char c : s) {
freq_map[c]++;
}

int n = s.size();
for (int i = 1; i < n; i++) {
char key = s[i];
int key_freq = freq_map[key];
int j = i - 1;

while (j >= 0 && freq_map[s[j]] < key_freq) {

s[j + 1] = s[j];
j--;
}
s[j + 1] = key;
}
return s;
}

Dry Run:-
Initial array: ['t', 'r', 'e', 'e']
Insert elements one by into sorted portion
Iteration 1 (i=1):
 Key = 'r' (freq=1)
 Compare with 't' (freq=1) → equal, insert after
Array: ['t', 'r', 'e', 'e']
Iteration 2 (i=2):

VANDNA KAUR(24124119) 4
  Key = 'e' (freq=2)
 Compare with 'r' (freq=1) → 2 > 1, shift right
Array: ['t', 'r', 'r', 'e'] (temporary shift)
 Compare with 't' (freq=1) → 2 > 1, shift right
Array: ['t', 't', 'r', 'e'] (temporary shift)
 Insert 'e' at index 0
Array: ['e', 't', 'r', 'e']
Iteration 3 (i=3):
 Key = 'e' (freq=2)
 Compare with 'r' (freq=1) → 2 > 1, shift right
Array: ['e', 't', 'r', 'r'] (temporary shift)
 Compare with 't' (freq=1) → 2 > 1, shift right
Array: ['e', 't', 't', 'r'] (temporary shift)
 Compare with 'e' (freq=2) → 2 == 2, stop
 Insert 'e' at index 1
Array: ['e', 'e', 't', 'r']
Final Result: "eetr"

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
int main() {
string s = "tree";
cout << "Original string: " << s << endl;
cout << "Bubble Sort: " << frequencySortBubble(s) << endl;
cout << "Selection Sort: " << frequencySortSelection(s) << endl;
cout << "Insertion Sort: " << frequencySortInsertion(s) << endl;
return 0;
}

VANDNA KAUR(24124119) 5
 Original string: tree
Bubble Sort: eetr
Selection Sort: eetr
Insertion Sort:eetr

Time Complexity:
 Bubble Sort: O(n²) worst-case and average-case
 Selection Sort: O(n²) worst-case and average-case
 Insertion Sort: O(n²) worst-case, but O(n) best-case (when nearly sorted)

Space Complexity:
All three algorithms use O(n) auxiliary space for the frequency map

Optimal solution: Insertion sort

It has the best practical performance among the three due to its adaptive nature - it handles
partially sorted data efficiently and typically makes fewer comparisons than Bubble Sort in
average cases.

VANDNA KAUR(24124119) 6