dutch national flag problem
Initially all array values are treated as unpartitioned:
[unpartitioned values]
Array split into four parts as the iteration proceeds:
[ values < mid | values = mid | unpartitioned values | values > mid ]
procedure three-way-partition(A : array of values, mid : value):
i ← 0
j ← 0
k ← size of A - 1
while j <= k:
if A[j] < mid:
swap A[i] and A[j]
i ← i + 1
j ← j + 1
else if A[j] > mid:
swap A[j] and A[k]
k ← k - 1
else:
j ← j + 1
3.88
8
Approach: Count the number of 0s, 1s and 2s in the given array.
Then store all the 0s in the beginning followed by all the 1s then
all the 2s.
Algorithm:
1)Keep three counter c0 to count 0s, c1 to count 1s and c2 to count 2s
2)Traverse through the array and increase the count of c0 is the
element is 0,increase the count of c1 if the element is 1 and
increase the count of c2 if the element is 2
3)Now again traverse the array and replace first c0 elements with 0,
next c1 elements with 1 and next c2 elements with 2.
//GfG PseudoCode
Thank you!
8
0
4
9
#include <bits/stdc++.h>
using namespace std;
void dutch(int arr[],int n)
{
int low=0;
int mid=0;
int high=n-1;
while(mid<=high)
{
switch(arr[mid])
{
case 0:
{
swap(arr[low++],arr[mid++]);
break;
}
case 1:
{
mid++;
break;
}
case 2:
{
swap(arr[high--],arr[mid]);
break;
}
}
}
}
int main()
{
int n;
cout<<"Enter the size of the array:"<<endl;
cin>>n;
int arr[n];
cout<<"Enter the elements of the array:"<<endl;
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
dutch(arr,n);
cout<<"our sorted array is:"<<endl;
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
return 0;
}
Thank you!
9
0
Are there any code examples left?
New code examples in category Other
-
Other 2023-03-27 22:50:10 how to select the whole line in vscode with keyboard shortcut
-
Other 2022-03-27 22:45:24 income of a web developer
-
Other 2022-03-27 22:35:01 \pyrcc_main.py: File does not exist 'resources.qrc'
-
Other 2022-03-27 22:30:45 rick roll embed code
-
Other 2022-03-27 22:20:08 Circuit_04_Potentiometer
-
Other 2022-03-27 22:20:05 iterative power
-
Other 2022-03-27 22:15:11 flutter run all
-
Other 2022-03-27 22:10:05 when is karlson release
-
Other 2022-03-27 22:10:02 wp .htaccess example
-
Other 2022-03-27 22:00:08 bash pause in file read line by line