Sorting:-
Bubble sort:-
Algorithm steps:
1. Start with the first element of the array.
2. Compare the current element with the next element.
3. If the current element is greater than the next element, swap them.
4. Move to the next element and repeat steps 2-3 until the end of the array.
5. Repeat steps 1-4 for each element in the array.
6. If no swaps occurred in a full pass, the array is sorted, and the algorithm can
terminate.
Code:-
#include <iostream>
#include <vector>
void bubbleSort(std::vector<int>& arr) {
int n = [Link]();
bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap elements
std::swap(arr[j], arr[j + 1]);
swapped = true;
// If no swapping occurred, array is already sorted
if (!swapped) {
break;
// Function to print the array
void printArray(const std::vector<int>& arr) {
for (int num : arr) {
std::cout << num << " ";
std::cout << std::endl;
int main() {
std::vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
std::cout << "Original array: ";
printArray(arr);
bubbleSort(arr);
std::cout << "Sorted array: ";
printArray(arr);
return 0;
Explanation:-
1. Including Necessary Libraries
#include <iostream>: This is required for input and output operations (std::cout,
std::endl).
#include <vector>: This includes the std::vector container from the C++ Standard
Library.
2. bubbleSort Function
Parameters: std::vector<int>& arr – a reference to a vector of integers.
Outer loop (for (int i = 0; i < n - 1; i++)):
● This loop runs from the beginning to n-1 because we need n-1 passes to
guarantee sorting.
Inner loop (for (int j = 0; j < n - i - 1; j++)):
● The inner loop compares adjacent elements, and if the current element (arr[j]) is
greater than the next (arr[j+1]), it swaps them.
● The range of the inner loop decreases with each outer loop pass, as the largest
elements are pushed to the end and are already in the correct position.
swapped flag:
● This is used to detect if any swapping occurred during the inner loop. If no swaps
are made in a pass, the array is already sorted, and the algorithm breaks out of the
loop early, improving efficiency.
3. printArray Function
Parameter: A constant reference to the vector arr.
This function iterates over the vector using a range-based for loop (for (int num :
arr)) and prints each element.
4. main Function
arr: A vector initialized with some integers.
The printArray function is called twice—first to display the original array and then to
display the sorted array after the bubbleSort function is called.
Merge Sort:-
#include <iostream>
#include <vector>
// Function to merge two subarrays
void merge(std::vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1; // Size of left subarray
int n2 = right - mid; // Size of right subarray
// Create temporary arrays
std::vector<int> leftArr(n1);
std::vector<int> rightArr(n2);
// Copy data to temporary arrays
for (int i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (int i = 0; i < n2; i++)
rightArr[i] = arr[mid + 1 + i];
// Merge the two subarrays back into arr
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
k++;
// Copy any remaining elements of leftArr
while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
// Copy any remaining elements of rightArr
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
// Recursive function to implement merge sort
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2; // Avoids overflow
// Sort first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
// Function to print the array
void printArray(const std::vector<int>& arr) {
for (int num : arr)
std::cout << num << " ";
std::cout << std::endl;
int main() {
std::vector<int> arr = {12, 11, 13, 5, 6, 7};
std::cout << "Original array: ";
printArray(arr);
mergeSort(arr, 0, [Link]() - 1);
std::cout << "Sorted array: ";
printArray(arr);
return 0;
}
Explanation:
1. Merge Function:
○ Parameters: The function takes the vector arr, the indices left, mid, and
right which define the two subarrays to be merged.
○ Temporary Arrays: Two temporary arrays (leftArr and rightArr) are
created to hold the elements of the left and right subarrays.
○ Merging: The function merges the two arrays by comparing elements from
each and placing the smaller element back into the original array.
○ Remaining Elements: After merging, any remaining elements from either
subarray are copied back into the original array.
2. Merge Sort Function (Recursive):
○ Base Case: If the subarray has one element or no elements (left >=
right), it is already sorted.
○ Recursive Case: The array is divided into two halves:
■ Recursively sort the left half.
■ Recursively sort the right half.
○ Merge: After sorting both halves, they are merged using the merge
function.
3. Print Function:
○ Prints the elements of the array.
4. Main Function:
○ Defines the vector arr, calls mergeSort to sort the array, and then prints
both the original and sorted arrays.
Merge Sort Algorithm:
1. Divide:
○ If the array has more than one element, divide it into two subarrays:
■ One subarray will contain elements from the first half.
■ The other subarray will contain elements from the second half.
2. Conquer:
○ Recursively apply Merge Sort to each subarray.
○ Continue dividing until each subarray contains a single element (a single
element is considered sorted).
3. Merge:
○ Merge the two sorted subarrays by comparing the elements from each and
placing them into a new array in sorted order.
4. Base Case:
○ If the subarray has one element, it’s already sorted, and the recursion
stops.
Algorithm steps:-
We define a CaesarCipher class that encapsulates the encryption and decryption logic.
The constructor takes a shift value, which determines how many positions each letter in
the alphabet should be moved.
The encrypt method:
● It iterates through each character in the input string.
● For each alphabetic character, it applies the shift:
○ It determines the base ('A' for uppercase, 'a' for lowercase).
○ It applies the formula (c - base + shift + 26) % 26 + base to shift
the character.
● Non-alphabetic characters are left unchanged.
The decrypt method works similarly, but reverses the shift:
● It uses the formula (c - base - shift + 26) % 26 + base.
In the main function:
● We prompt the user for a shift value and a message.
● We create a CaesarCipher object with the given shift.
● We encrypt the message, then decrypt it to demonstrate the process.
Code:-
#include <iostream>
#include <string>
class CaesarCipher {
private:
int shift;
public:
CaesarCipher(int s) : shift(s % 26) {}
std::string encrypt(const std::string& plaintext) {
std::string ciphertext = plaintext;
for (char& c : ciphertext) {
if (isalpha(c)) {
char base = isupper(c) ? 'A' : 'a';
c = (c - base + shift + 26) % 26 + base;
return ciphertext;
std::string decrypt(const std::string& ciphertext) {
std::string plaintext = ciphertext;
for (char& c : plaintext) {
if (isalpha(c)) {
char base = isupper(c) ? 'A' : 'a';
c = (c - base - shift + 26) % 26 + base;
return plaintext;
}
};
int main() {
int shift;
std::string message;
std::cout << "Enter the shift value (1-25): ";
std::cin >> shift;
std::[Link](); // Clear the newline from the buffer
std::cout << "Enter the message to encrypt: ";
std::getline(std::cin, message);
CaesarCipher cipher(shift);
std::string encrypted = [Link](message);
std::string decrypted = [Link](encrypted);
std::cout << "Original message: " << message << std::endl;
std::cout << "Encrypted message: " << encrypted << std::endl;
std::cout << "Decrypted message: " << decrypted << std::endl;
return 0;
Explanation:-
Components of the Program
1. Class Definition:
○ CaesarCipher Class:
■ Private Member:
■ int shift: This variable stores the shift value for the cipher.
■ Constructor:
■ CaesarCipher(int s): Initializes the shift value, ensuring
it's within the range of 0-25 using s % 26.
■ Public Methods:
■ std::string encrypt(const std::string&
plaintext): Encrypts the given plaintext.
■ std::string decrypt(const std::string&
ciphertext): Decrypts the given ciphertext.
2. Encrypt Method:
○ Iterates over each character of the input string (plaintext).
○ Checks if the character is an alphabet letter using isalpha(c).
○ If it is a letter, it determines the base character (A for uppercase and a for
lowercase) to ensure correct wrapping.
It applies the shift using the formula:
cpp
Copy code
c = (c - base + shift + 26) % 26 + base;
○
○ This formula ensures that if the shifted character goes past 'Z' or 'z', it
wraps around to the beginning of the alphabet.
3. Decrypt Method:
Similar to the encrypt method, but it subtracts the shift to reverse the encryption:
cpp
Copy code
c = (c - base - shift + 26) % 26 + base;
○
4. Main Function:
○ Prompts the user to enter a shift value and a message to encrypt.
○ Uses std::[Link]() to clear the input buffer after reading the shift
value.
○ An instance of the CaesarCipher class is created with the user-defined
shift.
○ The message is encrypted and then decrypted to verify that the process
works correctly.
○ Finally, it prints the original message, encrypted message, and decrypted
message.
○
Queue:-
Algorithm:-
1. The Queue class is templated, allowing it to work with any data type.
2. We use a std::vector as the underlying data structure to store the queue
elements.
3. The frontIndex keeps track of the front of the queue.
4. Key methods:
○ enqueue: Adds an item to the back of the queue using
vector::push_back.
○ dequeue: Removes and returns the front item. It increments frontIndex
instead of actually removing the item from the vector.
○ front: Returns a reference to the front item without removing it.
○ isEmpty: Checks if the queue is empty by comparing frontIndex with the
vector size.
○ size: Returns the number of elements in the queue.
5. The dequeue method includes an optimization: when frontIndex becomes larger
than half the vector size, it erases the unused elements at the front of the vector to
save memory.
6. Exception handling is implemented for trying to access elements from an empty
queue.
7. The main function demonstrates the usage of the queue, including enqueuing,
dequeuing, checking the front element, and handling exceptions.
Code:-
#include <iostream>
#include <vector>
#include <stdexcept>
template <typename T>
class Queue {
private:
std::vector<T> data;
size_t frontIndex;
public:
Queue() : frontIndex(0) {}
void enqueue(const T& item) {
data.push_back(item);
T dequeue() {
if (isEmpty()) {
throw std::out_of_range("Queue is empty");
T item = data[frontIndex];
frontIndex++;
// Resizing the vector if too many empty spots at the front
if (frontIndex > [Link]() / 2) {
[Link]([Link](), [Link]() + frontIndex);
frontIndex = 0;
return item;
T& front() {
if (isEmpty()) {
throw std::out_of_range("Queue is empty");
return data[frontIndex];
bool isEmpty() const {
return frontIndex >= [Link]();
size_t size() const {
return [Link]() - frontIndex;
};
int main() {
Queue<int> q;
// Enqueue some elements
[Link](1);
[Link](2);
[Link](3);
std::cout << "Queue size: " << [Link]() << std::endl;
std::cout << "Front element: " << [Link]() << std::endl;
// Dequeue and print elements
while (![Link]()) {
std::cout << "Dequeued: " << [Link]() << std::endl;
try {
[Link](); // This should throw an exception
} catch (const std::out_of_range& e) {
std::cout << "Exception: " << [Link]() << std::endl;
return 0;
}#include <iostream>
#include <vector>
#include <stdexcept>
template <typename T>
class Queue {
private:
std::vector<T> data;
size_t frontIndex;
public:
Queue() : frontIndex(0) {}
void enqueue(const T& item) {
data.push_back(item);
T dequeue() {
if (isEmpty()) {
throw std::out_of_range("Queue is empty");
T item = data[frontIndex];
frontIndex++;
// Resizing the vector if too many empty spots at the front
if (frontIndex > [Link]() / 2) {
[Link]([Link](), [Link]() + frontIndex);
frontIndex = 0;
return item;
T& front() {
if (isEmpty()) {
throw std::out_of_range("Queue is empty");
return data[frontIndex];
bool isEmpty() const {
return frontIndex >= [Link]();
size_t size() const {
return [Link]() - frontIndex;
}
};
int main() {
Queue<int> q;
// Enqueue some elements
[Link](1);
[Link](2);
[Link](3);
std::cout << "Queue size: " << [Link]() << std::endl;
std::cout << "Front element: " << [Link]() << std::endl;
// Dequeue and print elements
while (![Link]()) {
std::cout << "Dequeued: " << [Link]() << std::endl;
try {
[Link](); // This should throw an exception
} catch (const std::out_of_range& e) {
std::cout << "Exception: " << [Link]() << std::endl;
}
return 0;
Explanation:-
Components of the Program
1. Template Class Definition:
○ The Queue class is defined as a template, allowing it to hold elements of
any data type (T).
2. Private Members:
○ std::vector<T> data: A dynamic array that holds the queue elements.
○ size_t frontIndex: An index that tracks the position of the front element
in the queue.
3. Constructor:
○ Queue(): Initializes frontIndex to 0, indicating that no elements have
been dequeued yet.
4. Public Methods:
○ void enqueue(const T& item):
■ Adds an item to the back of the queue by pushing it to the data
vector.
○ T dequeue():
■ Removes and returns the front element of the queue.
■ Throws an exception if the queue is empty.
■ Increments frontIndex after removing the element.
■ If too many empty spots are left at the front (more than half of the
vector's size), it resizes the vector to reclaim memory by erasing
elements up to frontIndex and resets frontIndex to 0.
○ T& front():
■ Returns a reference to the front element of the queue without
removing it.
■ Throws an exception if the queue is empty.
○ bool isEmpty() const:
■ Returns true if frontIndex is greater than or equal to the size of
the data vector, indicating that the queue is empty.
○ size_t size() const:
■ Returns the number of elements currently in the queue, calculated
as the difference between the size of the vector and frontIndex.
Binary Tree:-
Algorithm:-
TreeNode class:
● Represents a node in the binary tree.
● Contains the data and pointers to left and right child nodes.
BinaryTree class:
● Manages the binary tree structure.
● Contains a pointer to the root node.
Key methods:
● insert: Inserts a new value into the tree. It uses a recursive helper function
insertRecursive.
● inorderTraversal: Performs an inorder traversal of the tree (left subtree, root,
right subtree).
● search: Searches for a value in the tree. It uses a recursive helper function
searchRecursive.
● levelOrderTraversal: Performs a level-order traversal of the tree using a
queue.
The insertion method ensures that the tree maintains the binary search tree property: all
nodes in the left subtree have values less than the current node, and all nodes in the
right subtree have values greater than the current node.
Code:-
#include <iostream>
#include <queue>
class TreeNode {
public:
int data;
TreeNode* left;
TreeNode* right;
TreeNode(int value) : data(value), left(nullptr), right(nullptr) {}
};
class BinaryTree {
private:
TreeNode* root;
TreeNode* insertRecursive(TreeNode* node, int value) {
if (node == nullptr) {
return new TreeNode(value);
if (value < node->data) {
node->left = insertRecursive(node->left, value);
} else if (value > node->data) {
node->right = insertRecursive(node->right, value);
}
return node;
void inorderTraversalRecursive(TreeNode* node) {
if (node != nullptr) {
inorderTraversalRecursive(node->left);
std::cout << node->data << " ";
inorderTraversalRecursive(node->right);
TreeNode* searchRecursive(TreeNode* node, int value) {
if (node == nullptr || node->data == value) {
return node;
if (value < node->data) {
return searchRecursive(node->left, value);
return searchRecursive(node->right, value);
public:
BinaryTree() : root(nullptr) {}
void insert(int value) {
root = insertRecursive(root, value);
void inorderTraversal() {
inorderTraversalRecursive(root);
std::cout << std::endl;
bool search(int value) {
return searchRecursive(root, value) != nullptr;
void levelOrderTraversal() {
if (root == nullptr) return;
std::queue<TreeNode*> q;
[Link](root);
while (![Link]()) {
int levelSize = [Link]();
for (int i = 0; i < levelSize; i++) {
TreeNode* node = [Link]();
[Link]();
std::cout << node->data << " ";
if (node->left) [Link](node->left);
if (node->right) [Link](node->right);
std::cout << std::endl;
};
int main() {
BinaryTree tree;
// Insert some values
[Link](5);
[Link](3);
[Link](7);
[Link](1);
[Link](9);
std::cout << "Inorder traversal: ";
[Link]();
std::cout << "Level order traversal:" << std::endl;
[Link]();
int searchValue = 7;
std::cout << "Searching for " << searchValue << ": "
<< ([Link](searchValue) ? "Found" : "Not Found") <<
std::endl;
searchValue = 4;
std::cout << "Searching for " << searchValue << ": "
<< ([Link](searchValue) ? "Found" : "Not Found") <<
std::endl;
return 0;
Explanation:-
Components of the Program
1. TreeNode Class:
○ Represents a node in the binary tree.
○ Members:
■ int data: Stores the value of the node.
■ TreeNode* left: Pointer to the left child.
■ TreeNode* right: Pointer to the right child.
○ Constructor:
■ Initializes data with the provided value and sets both child pointers
to nullptr.
2. BinaryTree Class:
○ Represents the binary search tree itself.
○ Private Members:
■ TreeNode* root: Pointer to the root node of the tree.
○ Private Methods:
■ TreeNode* insertRecursive(TreeNode* node, int value):
■ Inserts a new value into the tree recursively.
■ If the current node is nullptr, a new TreeNode is created.
■ If the value is less than the current node's data, it recurses to
the left child; if greater, it goes to the right.
■ Returns the node to maintain the tree structure.
■ void inorderTraversalRecursive(TreeNode* node):
■ Performs an in-order traversal (left, root, right) recursively
and prints the node values.
■ TreeNode* searchRecursive(TreeNode* node, int value):
■ Searches for a value in the tree recursively.
■ Returns the node if found; otherwise, it continues searching
in the left or right subtree based on the value.
○ Public Methods:
■ BinaryTree():
■ Constructor initializes the root to nullptr.
■ void insert(int value):
■ Public method to insert a value into the tree, calling the
recursive insertion method.
■ void inorderTraversal():
■ Public method to initiate in-order traversal.
■ bool search(int value):
■ Public method to search for a value in the tree, returning true
if found.
■ void levelOrderTraversal():
■ Performs a level-order traversal (breadth-first) using a queue.
■ Prints each level of the tree before moving to the next level.
3. Main Function:
○ An instance of BinaryTree is created.
○ Several integer values are inserted into the tree.
○ The program performs and prints the results of:
■ In-order traversal, which prints the values in sorted order.
■ Level-order traversal, which prints the values level by level.
○ The program then searches for two values (7 and 4) in the tree and prints
whether each was found.