Table of contents
- Q1. Implement Merge Sort and analyze its time complexity.
- Q2. Implement Quick Sort and analyze its time complexity.
- Q3. Solve the "find kth smallest/largest element in an array" problem using Quick Select.
- Q4. Solve the "sort characters by frequency" problem.
- Q5. Solve the "minimum number of swaps required to sort an array" problem.
Today’s practice focused on diving into more advanced sorting algorithms. I implemented Merge Sort and Quick Sort, analyzing their time complexities in the process. Additionally, I worked on solving problems like finding the kth smallest/largest element using Quick Select, sorting characters by frequency, and calculating the minimum number of swaps needed to sort an array. These exercises helped deepen my understanding of divide-and-conquer algorithms and their practical applications.
Check out my progress in my GitHub repository: github.com/AayJayTee/100-Days-DSA.
Q1. Implement Merge Sort and analyze its time complexity.
#include <iostream>
using namespace std;
void merge(int arr[], int beg, int mid, int end) {
int n1 = mid - beg + 1; // Size of the left subarray
int n2 = end - mid; // Size of the right subarray
// Create temporary arrays
int left[n1], right[n2];
// Copy data to temporary arrays
for (int i = 0; i < n1; i++)
left[i] = arr[beg + i];
for (int j = 0; j < n2; j++)
right[j] = arr[mid + 1 + j];
// Merge the two subarrays
int i = 0, j = 0, k = beg; // Initial indexes of left, right, and merged subarrays
while (i < n1 && j < n2) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
}
else{
arr[k] = right[j];
j++;
}
k++;
}
// Copy any remaining elements of left subarray
while (i < n1) {
arr[k] = left[i];
i++;
k++;
}
// Copy any remaining elements of right subarray
while (j < n2) {
arr[k] = right[j];
j++;
k++;
}
}
void mergeSort(int arr[],int beg,int end){
if(beg<end){
int mid=(beg+end)/2;
mergeSort(arr,beg,mid);
mergeSort(arr,mid+1,end);
merge(arr,beg,mid,end);
}
}
int main(){
int n;
cout<<"Enter length of the array: ";
cin>>n;
int arr[n];
cout<<"Enter the elements of the array: ";
for(int i=0;i<n;i++){
cin>>arr[i];
}
mergeSort(arr,0,n-1);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
The Merge Sort algorithm is a divide-and-conquer sorting technique. The algorithm divides the input array into two halves, recursively sorts each half, and then merges the sorted halves back together. The merge function is responsible for combining two sorted subarrays into a single sorted array. It compares elements from two temporary arrays (left and right) and merges them in a sorted manner. The mergeSort function is the recursive function that divides the array until it reaches individual elements, then calls the merge function to combine them back into sorted order. The time complexity of Merge Sort is O(n log n), where n is the number of elements in the array, because the array is divided into two halves (log n divisions) and each element is processed (n comparisons and merges). Merge Sort has a space complexity of O(n) due to the auxiliary arrays used for merging.
Q2. Implement Quick Sort and analyze its time complexity.
#include <iostream>
using namespace std;
int Partition(int arr[], int lb, int ub) {
int pivot = arr[lb]; // Choosing the first element as the pivot
int start = lb;
int end = ub;
while (start < end) {
// Increment start index until we find an element greater than pivot
while (arr[start] <= pivot && start < ub) {
start++;
}
// Decrement end index until we find an element smaller than pivot
while (arr[end] > pivot) {
end--;
}
if (start < end) {
swap(arr[start], arr[end]); // Swap the elements
}
}
// Place pivot at the correct position
swap(arr[lb], arr[end]);
return end; // Return the pivot index
}
void quickSort(int arr[], int lb, int ub) {
if (lb < ub) { // Base case: when the subarray has one or zero elements
int loc = Partition(arr, lb, ub); // Partition the array
quickSort(arr, lb, loc - 1); // Recursively sort the left part
quickSort(arr, loc + 1, ub); // Recursively sort the right part
}
}
int main() {
int n;
cout << "Enter length of the array: ";
cin >> n;
int arr[n];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
quickSort(arr, 0, n - 1);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
This code implements the Quick Sort algorithm, a divide-and-conquer sorting technique. The quickSort function recursively divides the array into smaller subarrays by selecting a "pivot" element. The Partition function rearranges the array so that elements smaller than the pivot come before it, and elements greater than the pivot come after it. After partitioning, the algorithm recursively sorts the left and right subarrays. The time complexity of Quick Sort is O(n log n) in the best and average cases, where n is the number of elements, but it can degrade to O(n^2) in the worst case when the pivot is poorly chosen. The space complexity is O(log n) due to the recursion stack, making Quick Sort efficient in practice, especially for large datasets, though it can become less efficient with unbalanced partitions.
Q3. Solve the "find kth smallest/largest element in an array" problem using Quick Select.
#include <iostream>
using namespace std;
int Partition(int arr[], int lb, int ub) {
int pivot = arr[ub]; // Use the last element as the pivot
int i = lb - 1;
for (int j = lb; j < ub; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[ub]);
return i + 1;
}
int quickSelect(int arr[], int lb, int ub, int k) {
if (lb <= ub) {
int pivotIndex = Partition(arr, lb, ub);
if (pivotIndex == k) {
return arr[pivotIndex]; // Found the k-th smallest element
} else if (pivotIndex > k) {
return quickSelect(arr, lb, pivotIndex - 1, k); // Search left
} else {
return quickSelect(arr, pivotIndex + 1, ub, k); // Search right
}
}
return -1; // Error case (not expected for valid input)
}
int main() {
int n, k, c;
cout << "Enter length of the array: ";
cin >> n;
int arr[n];
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "Do you want to find k-th smallest or largest? (1-smallest, 2-largest): ";
cin >> c;
cout << "What is the value of k?: ";
cin >> k;
if (c == 1) {
cout << "The " << k << "th smallest element is: "
<< quickSelect(arr, 0, n - 1, k - 1) << endl;
}
else if (c == 2) {
cout << "The " << k << "th largest element is: "
<< quickSelect(arr, 0, n - 1, n - k) << endl;
}
else {
cout << "Invalid choice" << endl;
}
return 0;
}
This code implements the Quick Select algorithm to find the k-th smallest or largest element in an array. The quickSelect function uses a partitioning approach similar to Quick Sort. It selects a pivot, rearranges the array such that elements less than the pivot are on the left and those greater are on the right, and then recursively narrows the search based on the position of the pivot. If the pivot's index matches k, it returns the element at that position. For finding the k-th largest element, the position is adjusted by using n-k. The time complexity of Quick Select is O(n) on average but can degrade to O(n^2) in the worst case if poor pivots are selected. This makes it more efficient than fully sorting the array, which has a time complexity of O(n log n).
Q4. Solve the "sort characters by frequency" problem.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
string sortCharactersByFrequency(string s) {
// Create a frequency array for uppercase and lowercase English letters
vector<int> freq(52, 0);
// Count frequencies of characters (map a-z to 0-25 and A-Z to 26-51)
for (char ch : s) {
if ('a' <= ch && ch <= 'z') {
freq[ch - 'a']++; // Lowercase letters
} else if ('A' <= ch && ch <= 'Z') {
freq[ch - 'A' + 26]++; // Uppercase letters
}
}
// Create a vector of pairs (frequency, character)
vector<pair<int, char>> charFreq;
for (int i = 0; i < 52; i++) {
if (freq[i] > 0) {
char ch = (i < 26) ? 'a' + i : 'A' + (i - 26);
charFreq.push_back({freq[i], ch});
}
}
// Sort the vector by frequency in descending order
sort(charFreq.begin(), charFreq.end(), [](pair<int, char>& a, pair<int, char>& b) {
return a.first > b.first;
});
// Build the result string
string result = "";
for (auto& p : charFreq) {
result += string(p.first, p.second); // Append the character 'frequency' times
}
return result;
}
int main() {
string input;
cout << "Enter the string: ";
cin >> input;
string result = sortCharactersByFrequency(input);
cout << "Sorted by frequency: " << result << endl;
return 0;
}
This code solves the "sort characters by frequency" problem by first counting the frequency of each character in the input string. It uses a vector of size 52 to track the frequency of each character, where the first 26 indices represent lowercase letters ('a' to 'z') and the last 26 represent uppercase letters ('A' to 'Z'). After counting, it stores each character and its frequency as a pair in a vector. This vector is then sorted in descending order based on the frequency of characters. Finally, the program constructs the result string by repeating each character according to its frequency. The time complexity of this approach is O(n + k log k), where n is the length of the input string and k is the number of distinct characters, which is constant (52 for English letters), so the overall time complexity is effectively O(n).
Q5. Solve the "minimum number of swaps required to sort an array" problem.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void countSwaps(vector<int>& arr) {
int n = arr.size();
vector<pair<int, int>> v;
// Create pairs of element and its index
for (int i = 0; i < n; i++) {
v.push_back({arr[i], i});
}
// Sort the array
sort(v.begin(), v.end());
vector<bool> visited(n, false);
int noofSwaps = 0;
// Find cycles and count swaps
for (int i = 0; i < n; i++) {
// Skip already visited elements or already in correct position
if (visited[i] || v[i].second == i) {
continue;
}
// Calculate the size of the cycle
int cycleSize = 0;
int j = i;
while (!visited[j]) {
visited[j] = true;
j = v[j].second; // Move to the next index in the cycle
cycleSize++;
}
// If cycle size is n, then (n-1) swaps are required
if (cycleSize > 1) {
noofSwaps += (cycleSize - 1);
}
}
cout << "No of swaps to sort the array are: " << noofSwaps << endl;
}
int main() {
int n;
cout << "Enter length of the array: ";
cin >> n;
vector<int> arr(n);
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
countSwaps(arr);
return 0;
}
This code implements a function to count the minimum number of swaps required to sort an array using the concept of cycle decomposition. It first creates a vector of pairs where each pair contains an element from the array and its original index. The array is then sorted, and a boolean vector is used to track visited elements. The algorithm iterates through the array, and for each unvisited element, it traces the cycle of elements that would result from sorting. For each cycle of size n, it requires n-1 swaps to place all elements in their correct positions. The total number of swaps is calculated by summing the swaps needed for each cycle. The time complexity is O(n log n) due to the sorting step.
Today's exercises strengthened my knowledge of advanced sorting algorithms and their real-world use cases. From mastering Merge and Quick Sort to solving problems involving selection and frequency analysis, I’m more confident in applying these techniques efficiently. Looking forward to tackling even more challenging topics in the upcoming days!