Table of contents
- 1. Implement Merge Sort and analyze its time complexity.
- 2. Implement Quick Sort and analyze its time complexity.
- 3. Solve the "find kth smallest/largest element in an array" problem using Quick Select.
- 4. Solve the "sort characters by frequency" problem.
- 5. Solve the "minimum number of swaps required to sort an array" problem.
Hey y’all! Today on the twelfth day of this challenge I’ll be solving five problems related to advanced sorting techniques. You can checkout my github repository, I upload the solutions there as well. Let’s begin solving today’s questions :)
1. Implement Merge Sort and analyze its time complexity.
Merge Sort is a divide-and-conquer algorithm that recursively divides the array into two halves, sorts each half, and then merges them. The merging step ensures the sorted order is maintained.
Time Complexity:
Best, Worst, and Average: O(nlogn), where nnn is the number of elements.
Space Complexity: O(n) due to the auxiliary array used during merging.
// To implement merge sort and analyze its time complexity
#include<iostream>
using namespace std;
void merge(int arr[],int low,int mid,int high){
int n1=mid-low+1;
int n2=high-mid;
int L[n1],R[n2];
for(int i=0;i<n1;i++){
L[i]=arr[low+i];
}
for(int j=0;j<n2;j++){
R[j]=arr[mid+1+j];
}
int i=0,j=0,k=low;
while(i<n1 && j<n2){
if(L[i]<=R[j]){
arr[k]=L[i];
i++;
}
else{
arr[k]=R[j];
j++;
}
k++;
}
while(i<n1){
arr[k]=L[i];
i++;
k++;
}
while(j<n2){
arr[k]=R[j];
j++;
k++;
}
}
void mergeSort(int arr[],int low,int high){
if(low<high){
int mid=(low+high)/2;
mergeSort(arr,low,mid);
mergeSort(arr,mid+1,high);
merge(arr,low,mid,high);
}
}
int main(){
int arr[]={12,11,13,5,6,7};
int n=sizeof(arr)/sizeof(arr[0]);
cout<<"Given array is: ";
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
cout<<"Sorted array is: ";
mergeSort(arr,0,n-1);
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
return 0;
}
Output:
2. Implement Quick Sort and analyze its time complexity.
Quick Sort partitions the array around a pivot such that elements smaller than the pivot go to its left, and larger ones to its right. It then recursively sorts the partitions. The choice of pivot impacts performance.
Time Complexity:
Best and Average: O(nlogn)
Worst: O(n2) (when the pivot is poorly chosen, e.g., smallest or largest element).
Space Complexity: O(logn) due to recursion stack.
Code:
// Implement Quick Sort and analyze its time complexity.
#include<iostream>
using namespace std;
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 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;
}
int main(){
int arr[]={12,11,13,5,6,7};
int n=sizeof(arr)/sizeof(arr[0]);
cout<<"Given array is: ";
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
cout<<"Sorted array is: ";
quickSort(arr,0,n-1);
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
cout<<endl;
return 0;
}
Output:
3. Solve the "find kth smallest/largest element in an array" problem using Quick Select.
Quick Select is a variant of Quick Sort that focuses only on one partition based on the pivot. It recursively narrows the search to find the kth smallest/largest element, skipping sorting of unnecessary parts.
Time Complexity:
Average: O(n)
Worst: O(n^2), when the pivot is poorly chosen.
Space Complexity: O(logn).
Code:
// Solve the "find kth smallest/largest element in an array" problem using Quick Select.
#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;
}
int quickSelect(int arr[], int low, int high, int k) {
if (low < high) {
int pi = partition(arr, low, high);
if (pi == k) {
return arr[pi];
} else if (pi < k) {
return quickSelect(arr, pi + 1, high, k);
} else {
return quickSelect(arr, low, pi - 1, k);
}
}
return arr[low];
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Given array is: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
int k = 3;
cout << "The " << k << "th smallest element is: " << quickSelect(arr, 0, n - 1, k - 1) << endl;
return 0;
}
Output:
4. Solve the "sort characters by frequency" problem.
Use a frequency dictionary to count occurrences of each character, then sort the characters based on their frequencies in descending order. Construct the result by repeating characters as per their frequencies.
Time Complexity:O(nlogn) for sorting.
Space Complexity: O(n) for the frequency map.
Code:
// Solve the "sort characters by frequency" problem.
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
string frequencySort(string s) {
unordered_map<char, int> freq;
for (char c : s) {
freq[c]++;
}
vector<string> bucket(s.size() + 1, "");
for (auto& it : freq) {
char c = it.first;
int n = it.second;
bucket[n].append(n, c);
}
string res;
for (int i = s.size(); i > 0; i--) {
if (!bucket[i].empty()) {
res.append(bucket[i]);
}
}
return res;
}
int main() {
string s = "tree";
cout << "The sorted characters by frequency are: " << frequencySort(s) << endl;
return 0;
}
Output:
5. Solve the "minimum number of swaps required to sort an array" problem.
Map each element to its position in the sorted array. Use cycle detection in the permutation formed by these mappings to calculate the number of swaps needed to sort the array.
Time Complexity: O(n), as each element is visited once.
Space Complexity: O(n), for storing element positions.
Code:
// Solve the "minimum number of swaps required to sort an array" problem.
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
int minSwaps(vector<int>& arr) {
int n = arr.size();
vector<int> temp(n);
for (int i = 0; i < n; i++) {
temp[i] = arr[i];
}
sort(temp.begin(), temp.end());
unordered_map<int, int> mp;
for (int i = 0; i < n; i++) {
mp[temp[i]] = i;
}
int swaps = 0;
for (int i = 0; i < n; i++) {
if (arr[i] != temp[i]) {
swaps++;
int x = arr[i];
swap(arr[i], arr[mp[arr[i]]]);
mp[x] = mp[arr[i]];
mp[arr[i]] = i;
}
}
return swaps;
}
int main() {
vector<int> arr = {7, 1, 3, 2, 4, 5, 6};
cout << "The minimum number of swaps required to sort the array is: " << minSwaps(arr) << endl;
return 0;
}
Output:
That’s all for today! Wishing you a great day! 😊 Catch you tomorrow. 🚀