Below are the detailed explanations and C++ implementations of the requested topics.

---

(a) Advanced Sorting

Advanced sorting algorithms are used for efficient sorting, especially on large datasets. Examples
include:

Merge Sort

Quick Sort

Heap Sort

Shell Sort

These algorithms provide better time complexity than simple ones like Bubble Sort or Insertion Sort.
Each is explained below.

---

(b) Shell Sort

Code in C++:

#include <iostream>

using namespace std;

void shellSort(int arr[], int n) {

for (int gap = n / 2; gap > 0; gap /= 2) {

for (int i = gap; i < n; i++) {

int temp = arr[i];

int j;

for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {

arr[j] = arr[j - gap];

arr[j] = temp;

int main() {

int arr[] = {12, 34, 54, 2, 3};

int n = sizeof(arr) / sizeof(arr[0]);

shellSort(arr, n);
 cout << "Sorted array: ";

for (int i = 0; i < n; i++)

cout << arr[i] << " ";

return 0;

Explanation:

1. The array is divided into subarrays based on a gap.

2. Each subarray is sorted using insertion sort.

3. The gap is reduced iteratively until it becomes 1.

---

(c) Quick Sort

Quick Sort uses the divide-and-conquer technique. It partitions the array around a pivot and recursively
sorts the subarrays.
Code in C++:

#include <iostream>

using namespace std;

int partition(int arr[], int low, int high) {

int pivot = arr[high];

int i = low - 1;

for (int j = low; j < high; j++) {

if (arr[j] < pivot) {

i++;

swap(arr[i], arr[j]);

swap(arr[i + 1], arr[high]);

return i + 1;

void quickSort(int arr[], int low, int high) {

if (low < high) {

int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);

}
}

int main() {

int arr[] = {10, 7, 8, 9, 1, 5};

int n = sizeof(arr) / sizeof(arr[0]);

quickSort(arr, 0, n - 1);

cout << "Sorted array: ";

for (int i = 0; i < n; i++)

cout << arr[i] << " ";

return 0;

Explanation:

1. The array is partitioned using a pivot element.

2. Elements smaller than the pivot are moved to the left, and larger ones to the right.

3. The process is recursively applied to the subarrays.

(d) Heap Sort

Heap Sort builds a max heap and repeatedly extracts the maximum element, placing it at the end of the
array.

Code in C++:

#include <iostream>

using namespace std;

void heapify(int arr[], int n, int i) {

int largest = i;

int left = 2 * i + 1;

int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;

if (largest != i) {

swap(arr[i], arr[largest]);

heapify(arr, n, largest);
 }

void heapSort(int arr[], int n) {

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);

for (int i = n - 1; i > 0; i--) {

swap(arr[0], arr[i]);

heapify(arr, i, 0);

int main() {

int arr[] = {12, 11, 13, 5, 6, 7};

int n = sizeof(arr) / sizeof(arr[0]);

heapSort(arr, n);

cout << "Sorted array: ";

for (int i = 0; i < n; i++)

cout << arr[i] << " ";

return 0;

Explanation:
1. A max heap is created from the array.

2. The largest element is swapped with the last element, and the heap size is reduced.

3. The heapify operation ensures the remaining array is a valid heap.

---

(e) Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the array, sorts the subarrays, and merges
them.

Code in C++:

#include <iostream>

using namespace std;

void merge(int arr[], int l, int m, int r) {

int n1 = m - l + 1;

int n2 = r - m;
 int L[n1], R[n2];

for (int i = 0; i < n1; i++)

L[i] = arr[l + i];

for (int i = 0; i < n2; i++)

R[i] = arr[m + 1 + i];

int i = 0, j = 0, k = l;

while (i < n1 && j < n2) {

if (L[i] <= R[j])

arr[k++] = L[i++];

else

arr[k++] = R[j++];

while (i < n1)

arr[k++] = L[i++];

while (j < n2)

arr[k++] = R[j++];

void mergeSort(int arr[], int l, int r) {

if (l < r) {

int m = l + (r - l) / 2;

mergeSort(arr, l, m);
 mergeSort(arr, m + 1, r);

merge(arr, l, m, r);

int main() {

int arr[] = {38, 27, 43, 3, 9, 82, 10};

int n = sizeof(arr) / sizeof(arr[0]);

mergeSort(arr, 0, n - 1);

cout << "Sorted array: ";

for (int i = 0; i < n; i++)

cout << arr[i] << " ";

return 0;

Explanation:

1. The array is divided into two halves recursively.

2. The halves are sorted and merged into a single sorted array.
---

(f) Advanced Searching

Examples of advanced searching include Binary Search, Search Trees, and Hashing.

Binary Search Code in C++:

#include <iostream>

using namespace std;

int binarySearch(int arr[], int n, int target) {

int low = 0, high = n - 1;

while (low <= high) {

int mid = low + (high - low) / 2;

if (arr[mid] == target)

return mid;

else if (arr[mid] < target)

low = mid + 1;

else

high = mid - 1;

return -1;
}

int main() {

int arr[] = {1, 3, 5, 7, 9};

int n = sizeof(arr) / sizeof(arr[0]);

int target = 5;

int index = binarySearch(arr, n, target);

if (index != -1)

cout << "Element found at index " << index;

else

cout << "Element not found";

return 0;

Explanation:

1. The array is divided into halves.

2. The middle element is compared to the target.

3. The search continues in one half based on the comparison.

(g) Hashing

Hashing maps keys to values using a hash function for fast retrieval.

Hash Table Implementation in C++:

#include <iostream>

#include <list>

using namespace std;

class HashTable {

int size;

list<pair<string, int>> *table;

public:

HashTable(int s) {

size = s;

table = new list<pair<string, int>>[size];

int hashFunction(string key) {

for (char c : key)

hash += c;

return hash % size;

void insert(string key, int value) {

int index = hashFunction(key);

for (auto &p : table[index]) {

if (p.first == key) {

p.second = value;

return;

table[index].emplace_back(key, value);

int search(string key) {

int index = hashFunction(key);

for (auto &p : table[index]) {

if (p.first == key)

return p.second;