1.
Advanced Sorting Algorithm
Application of Data Structure and Algorithm used to sort data in order it’s better than simple
sorting and efficient for big data
1.1 shell sort
Advanced sorting algorithm that sort data by comparing elements with specific gap between
them until the gap become smaller and smaller until it reaches (1)which make the sorting more
faster and efficient than simple sorting
Advantages
● Used in small or medium conputer programs to sort student scores
● Faster than Bubble Sort and Insertion Sort
● Easy to use and implement
● Use less memory
Typical Use Cases
● Medium size data
● Computers with small memory
● When we need simple and faster sorting algorithm
1.2Quick sort
Quick Sort works by choosing one element called pivot from the array Then the algorithm
compares all elements with the pivot The smaller elements move to the left side and the bigger
elements move to the right side After that the pivot goes to the correct position in the array Then
the algorithm repeats the same process again for the left side and the right side until all elements
become sorted in order. Quick Sort is fast because it divides the data into smaller parts and sorts
them step by step
Advantages
● Very fast sorting algorithm
● Efficient for large data
● Uses less memory
Typical Uses
● Sort the price of the product in online shopping application
● Database systems
● Large datasets
● Applications that need fast sorting
1.3Heap sort
First it changes the data into a Max Heap that is a tree where the biggest number is always at the
top after building the Max Heap the algorithm takes the biggest element from the top and swaps
it with the last element in the array This moves the biggest value to the end of the array and this
element is already sorted so the algorithm does not use it again then the heap size becomes
smaller because one element is already sorted then the algorithm rebuilds the Max Heap again
for the remaining unsorted elements this help the new biggest element move to the top again
Advantages
● Good for large data
● Fast sorting algorithm
● Performance is more stable
Typical Uses
● Large datasets
● Priority queue systems
● Applications that need efficient sorting
Implementation
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);
}
}
1.4 Merge Sort
Merge Sort works by dividing the data into smaller parts based on the middle position of the
array The array is split into two halves left and right each half is divided again and again until
each part has only one element and we know that one element is already considered sorted After
dividing the data into small parts each containing one element the algorithm starts the merge
process It takes two small sorted parts and compares their elements one by one and the smaller
element is placed first into a new array then it compares the next elements again and keeps
putting the smaller element first into the new array.
It continues until all elements from both parts are combined into one sorted part Then the
algorithm repeats the same merge process with larger parts until all the data becomes one
completely sorted array in order
Advantages
● Fast for sorting data
● Good for large data
● Keeps data in correct order when values are same
Typical Uses
● Database applications
● Large data sorting
● Systems that need fast and stable sorting
Implementation
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];
int i = 0, j = 0, k = left;
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 left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
[Link] Searching Algorithm
Application of data structure and algorithms
used to find data quickly and efficiently in a collection of data and they are faster and better
than simple searching methods especially for large data it is used in databases, search engines,
computer systems, and applications that need fast data searching
2.1 Hashing
Hashing works by giving every data a unique number called hash value and computer can know
where it is stored using this unique number andWhen we want to find this data again the
computer uses the same hash function to get the same [Link] helps the computer to go
directly to the data location very quickly instead of searching all data one by one.
Advantages
● Fast to find data
● Good for large data
● Makes searching easier and faster
Typical Uses
● Social media applications when users enter password to log in
● Database systems to find information quickly
● Password systems to store passwords safely
● Search engines to search data fast
● Computer networks to manage data
Implementation
int hashFn(int key) {
return key % SIZE;
}
void insert(int key, int value) {
int index = hashFn(key);
Node* newNode = new Node{key, value, hashTable[index]};
hashTable[index] = newNode;
}
int search(int key) {
int search(int key) {
int index = hashFn(key);
Node* curr = hashTable[index];
while (curr != nullptr) {
if (curr->key == key) return curr->value;
curr = curr->next;
}
return -1;
}
void remove(int key) {
int index = hashFn(key);
Node* curr = hashTable[index];
Node* prev = nullptr;
while (curr != nullptr) {
if (curr->key == key) {
if (prev) prev->next = curr->next;
else hashTable[index] = curr->next;
delete curr;
return;
}
prev = curr;
curr = curr->next;
}
}