Daily Dose of DSA - Day 10
Sort colors using simple sort (TC O(nlogn) & SC O(1)) and using Dutch National Flag Algorithm(TC O(n) & SC O(1))
/*In this approach, we will be using 3 pointers named low, mid, and high. We will be using these 3 pointers to move around the values. The primary goal here is to move 0s to the left and 2s to the right of the array and at the same time all the 1s shall be in the middle region of the array and hence the array will be sorted. */
class Solution {
public:
void sortColors(vector<int>& nums) //By switch-case
{
int low=0;
int high=nums.size()-1;
int mid=0;
while(mid<=high)
{
switch(nums[mid])
{
case 0:
swap(nums[low++],nums[mid++]);
break;
case 1:
mid++;
break;
case 2:
swap(nums[mid],nums[high--]);
break;
}
}
}
};
class Solution {
public:
void sortColors(vector<int>& nums) //By if else
{
int low=0;
int high=nums.size()-1;
int mid=0;
while(mid<=high)
{
if(nums[mid]==0)
{
swap(nums[low++],nums[mid++]);
}
else if(nums[mid]==1)
{
mid++;
}
else if (nums[mid]==2)
{
swap(nums[mid],nums[high--]);
}
}
}
};
class Solution {
public:
void sortColors(vector<int>& nums)
{
sort(nums.begin(),nums.end());
}
};