Dsa - Arrays
Hey devs hope you all are doing well!
Today we are going to learn an array based algorithm called dutch flag algorithm A.K.A 3 way parition algorithm.
Before going through this article make sure you are good with array basics.
Arrays basics : https://www.cs.fsu.edu/~myers/c++/notes/arrays.html#:~:text=An%20array%20is%20an%20indexed,therefore%2C%20the%20same%20size).
Where is the Algorithm used ?
The idea behind the algorithm is to partition an array into 3 parts using 3 pointers and can be used to sort arrays having 3 values (which can be repeated any no. of times) Ex: [0,2,1,2,0,2,2].(Sort array with 0s,1s and 2s).
Procedure :
Take an unsorted array with 0s,1s and 2s.(Or any 3 numbers).
Initialize 3 variables low , mid , high with the below values :
- low : 0
- mid : 0
- high: n-1 (Where n is the no. of array entries).
3.When the algorithm is completed elements from :
- index 0 -> low will have 0s.
- index low -> mid will have 1s.
- index mid -> high will have (0s/1s/2s).
- index high -> n will have 2s.
4.There are 3 cases in this algorithm as mid moves along the array until it crosses high.
5.IF list[mid] == 0 (list is our array)
- Swap the values of list[mid] and list[low].
- Increment low and mid by one unit.
- We do this to ensure all 0s are put to the front.
6.IF list[mid] == 1
- No swap is needed
- Increment only mid by one unit.
7.IF list[mid] == 2
- Swap list[mid] and list[high]
- Increment mid and decrement high.
- We do this to ensure all 2s are put to the end.
8.When mid crosses high the algorithm ends and we get a sorted array.
Time Complexity : O(n)
Space Complexity : O(1)
Try out yourself
https://leetcode.com/problems/sort-colors/
Source Code
class Solution
{
public void sortColors(int[] nums)
{
int mid = 0 , high = nums.length - 1 ,low = 0;
while(mid <= high)
{
int value = nums[mid];
if(value == 0)
{
int swapvalue = nums[mid];
nums[mid] = nums[low];
nums[low] = swapvalue;
mid++;
low++;
}
else if(value == 1)
mid++;
else if(value == 2)
{
int swap = nums[mid];
nums[mid] = nums[high];
nums[high] = swap;
high--;
}
}
}
}
Top comments (0)