Advanced sorting algorithms like Merge Sort and Quick Sort play a pivotal role in efficiently managing large datasets, offering optimal solutions in terms of time complexity. On Day 12, the focus was on implementing these techniques, exploring their variations, and solving problems that emphasize their practical applications.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let’s dive into today’s challenges and unravel the power of these sorting methods! 🚀
1. Merge Sort
This program implements Merge Sort, a divide-and-conquer algorithm. The array is recursively divided into two halves until each segment contains a single element. The merge function then combines these sorted segments back into a larger sorted array. The process continues until the entire array is sorted. The time complexity of Merge Sort is O(n log n), as dividing takes O(log n) steps and merging takes O(n) for each level of recursion.
Code:
#include <iostream>
using namespace std;
// Function to merge two sorted subarrays
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1; // Size of the first subarray
int n2 = right - mid; // Size of the second subarray
// Create temporary arrays
int left_arr[n1], right_arr[n2];
// Copy data to temporary arrays
for (int i = 0; i < n1; i++)
left_arr[i] = arr[left + i];
for (int j = 0; j < n2; j++)
right_arr[j] = arr[mid + 1 + j];
// Merge the temporary arrays back into arr[]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (left_arr[i] <= right_arr[j]) {
arr[k] = left_arr[i];
i++;
} else {
arr[k] = right_arr[j];
j++;
}
k++;
}
// Copy remaining elements of leftArr[], if any
while (i < n1) {
arr[k] = left_arr[i];
i++;
k++;
}
// Copy remaining elements of rightArr[], if any
while (j < n2) {
arr[k] = right_arr[j];
j++;
k++;
}
}
// Function to implement Merge Sort
void merge_sort(int arr[], int left, int right) {
if (left < right) {
// Find the middle point
int mid = left + (right - left) / 2;
// Sort the first and second halves
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
void print_array(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
print_array(arr, n);
merge_sort(arr, 0, n - 1);
cout << "Sorted array: ";
print_array(arr, n);
return 0;
}
Output:
2. Quick Sort
This porgram implements Quick Sort, a divide-and-conquer algorithm. The partition function selects the first element as the pivot and rearranges the array such that elements smaller than the pivot are on its left and larger ones on its right. The quick_sort function recursively applies this partitioning process to the left and right subarrays, sorting them independently. The array is sorted in place without additional storage. The time complexity is O(n log n) on average but can degrade to O(n²) in the worst case when the pivot results in highly unbalanced partitions.
Code:
#include <iostream>
using namespace std;
// Function to partition the array around the pivot
int partition(int arr[], int low, int high) {
int pivot = arr[low]; // Choose the first element as pivot
int i = low + 1; // Index for smaller elements
int j = high; // Index for larger elements
while (true) {
// Find elements greater than or equal to pivot
while (i <= j && arr[i] <= pivot) {
i++;
}
// Find elements less than or equal to pivot
while (i <= j && arr[j] > pivot) {
j--;
}
if (i >= j) {
break; // Pointers crossed; partition is complete
}
// Swap arr[i] and arr[j]
swap(arr[i], arr[j]);
}
// Swap pivot with the element at j (correct position)
swap(arr[low], arr[j]);
return j; // Return pivot's final position
}
// Function to perform Quick Sort
void quick_sort(int arr[], int low, int high) {
if (low < high) {
// Partition the array
int pivot_index = partition(arr, low, high);
// Recursively sort elements before and after the pivot
quick_sort(arr, low, pivot_index - 1);
quick_sort(arr, pivot_index + 1, high);
}
}
// Function to print an array
void print_array(int arr[], int size) {
for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
print_array(arr, n);
quick_sort(arr, 0, n - 1);
cout << "Sorted array: ";
print_array(arr, n);
return 0;
}
Output:
3. Find Kth Smallest/Largest Element Using Quick Select
This program implements Quick Select to find the kth smallest or largest element in an array. It uses the partition method to rearrange elements around a pivot, such that smaller elements are on the left and larger ones on the right. The algorithm recursively focuses on the partition containing the kth element, skipping unnecessary parts of the array. For the kth largest element, it converts the problem to finding the (n-k)th smallest. The process works in-place, minimizing memory usage.
Code:
#include <iostream>
using namespace std;
// Partition function for Quick Select
int partition(int arr[], int low, int high) {
int pivot = arr[low]; // Choose the first element as the pivot
int i = low + 1; // Pointer for smaller elements
int j = high; // Pointer for larger elements
while (true) {
// Move i to the right for elements less than or equal to pivot
while (i <= j && arr[i] <= pivot) {
i++;
}
// Move j to the left for elements greater than pivot
while (i <= j && arr[j] > pivot) {
j--;
}
// If pointers cross, break the loop
if (i >= j) {
break;
}
// Swap arr[i] and arr[j]
swap(arr[i], arr[j]);
}
// Place the pivot in its correct position
swap(arr[low], arr[j]);
return j; // Return the pivot's index
}
// Quick Select function
int quick_select(int arr[], int low, int high, int k) {
if (low <= high) {
// Partition the array
int pivot_index = partition(arr, low, high);
// Check if pivot is the kth element
if (pivot_index == k) {
return arr[pivot_index];
} else if (pivot_index > k) {
// If kth element is in the left subarray
return quick_select(arr, low, pivot_index - 1, k);
} else {
// If kth element is in the right subarray
return quick_select(arr, pivot_index + 1, high, k);
}
}
return -1; // Return -1 if k is invalid
}
// Helper function to find kth smallest or largest element
void find_kth_element(int arr[], int n, int k, bool is_smallest) {
if (k < 1 || k > n) {
cout << "Invalid value of k!" << endl;
return;
}
// If kth smallest is required
if (is_smallest) {
cout << "The " << k << "th smallest element is: " << quick_select(arr, 0, n - 1, k - 1) << endl;
} else {
// For kth largest, convert it to the kth smallest problem
cout << "The " << k << "th largest element is: " << quick_select(arr, 0, n - 1, n - k) << endl;
}
}
int main() {
int arr[] = {7, 10, 4, 3, 20, 15};
int n = sizeof(arr) / sizeof(arr[0]);
int k;
cout << "Array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl << "Enter the value of k: ";
cin >> k;
// Find kth smallest element
find_kth_element(arr, n, k, true);
// Find kth largest element
find_kth_element(arr, n, k, false);
return 0;
}
Output:
4. Sort Characters by Frequency
This program sorts characters in a string by their frequency. It first builds a frequency table using an array for ASCII characters, tracking how often each character appears. Then, it sorts the characters by descending frequency, using a custom sorting logic. Finally, it constructs the result string by appending each character based on its frequency.
Code:
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// Helper function to build the frequency table
void build_freq_table(const string &s, int freq[], char chars[]) {
for (int i = 0; i < s.length(); ++i) {
int index = s[i];
if (freq[index] == 0) {
chars[index] = s[i];
}
freq[index]++;
}
}
// Custom comparator to sort by frequency and character order
void sort_by_freq(char chars[], int freq[], int size) {
for (int i = 0; i < size - 1; ++i) {
for (int j = i + 1; j < size; ++j) {
if (freq[chars[j]] > freq[chars[i]] ||
(freq[chars[j]] == freq[chars[i]] && chars[j] < chars[i])) {
swap(chars[i], chars[j]);
}
}
}
}
// Function to generate the sorted string by frequency
string freq_sort(const string &s) {
const int CHAR_COUNT = 256; // Support for all ASCII characters
int freq[CHAR_COUNT] = {0};
char chars[CHAR_COUNT] = {0};
// Build frequency table
build_freq_table(s, freq, chars);
// Sort characters by frequency
sort_by_freq(chars, freq, CHAR_COUNT);
// Build result string
string result;
for (int i = 0; i < CHAR_COUNT; ++i) {
if (freq[chars[i]] > 0) {
result.append(freq[chars[i]], chars[i]);
}
}
return result;
}
int main() {
string s = "seventeen";
cout << "Original string: " << s << endl;
string sortedString = freq_sort(s);
cout << "String sorted by frequency: " << sortedString << endl;
return 0;
}
Output:
5. Minimum Number of Swaps Required to Sort an Array
This program solves the problem of finding the minimum number of swaps required to sort an array by detecting cycles in the array. It first creates an array of pairs, each containing an element and its original index, then sorts the array based on the element values. The algorithm then tracks each cycle of misplaced elements and counts the swaps required to fix each cycle. The total number of swaps is the sum of the swaps needed for all cycles, which is computed by visiting each element and tracing the cycle it belongs to.
Code:
#include <iostream>
#include <algorithm>
using namespace std;
// Function to find the minimum number of swaps required to sort the array
int min_swaps(int arr[], int n) {
// Create an array of pairs where each pair consists of (array element, original index)
pair<int, int> arr_pos[n];
for (int i = 0; i < n; ++i) {
arr_pos[i].first = arr[i];
arr_pos[i].second = i;
}
// Sort the array of pairs based on the element values
sort(arr_pos, arr_pos + n);
// To track visited elements
bool visited[n] = {false};
int swaps = 0;
// Iterate through the elements
for (int i = 0; i < n; ++i) {
// If the element is already visited or is already in the correct position
if (visited[i] || arr_pos[i].second == i) {
continue;
}
// Calculate the size of the cycle
int cycle_size = 0;
int j = i;
while (!visited[j]) {
visited[j] = true;
j = arr_pos[j].second; // Move to the index where the element should be
cycle_size++;
}
// If there is a cycle of 'n' elements, it will take (n-1) swaps to arrange them
if (cycle_size > 1) {
swaps += (cycle_size - 1);
}
}
return swaps;
}
int main() {
int arr[] = {5, 4, 3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
int result = min_swaps(arr, n);
cout << "Minimum swaps required to sort the array: " << result << endl;
return 0;
}
Output:
Day 12 focused on advanced sorting techniques and their real-world applications. By diving into problems that required efficient algorithmic design and exploring divide-and-conquer strategies, I gained a deeper understanding of the power of algorithms like Merge Sort and Quick Sort. The challenges, such as sorting characters by frequency and minimizing swaps, highlighted the versatility and efficiency these methods offer. Excited to continue solving more complex problems tomorrow! 🚀
That's all for today! Wishing you a productive day ahead! 😊 See you tomorrow!