Sort an array of 0s, 1s and 2s
Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.
Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}
Solution:
static
void
sort(
int
a[],
int
arr_size)
{
int
lo =
0
;
int
hi = arr_size -
1
;
int
mid =
0
,temp=
0
;
while
(mid <= hi)
{
switch
(a[mid])
{
case
0
:
{
temp = a[lo];
a[lo] = a[mid];
a[mid] = temp;
lo++; //increase low index
mid++; //increase high index
break
;
}
case
1
:
mid++;
//increase only middle index
break
;
case
2
:
{
temp = a[mid];
a[mid] = a[hi];
a[hi] = temp;
hi--;
//decrease high index
break
;
}
}
}
}
No comments:
Post a Comment