Sometimes
you may need to sort an array consisting only two
numbers. Let say ones and zeros. Here I am going to explain an
algorithm, to
solve such problem using one traverse, without using an additional
array, and what really happen is, that it segregates ones and zeros
in the array. You may see that this method is efficient than a usual
sorting algorithm.
Let’s take the following array as an example.
array = {0, 1, 1, 0, 0, 1,
1}
Here I use two variables named left and right.
- left – keep the array index when it is moved from left to right (left++)
- right - keep the array index when it is moved from right to left (right--)
The variable left increases until array[left] equals to 0 and similarly variable right decreases until array[right] equals to 1. If the left is less than right then 0 and 1 get interchanged and similar process happens until left is less than right.
- {0, 1, 1, 0, 0, 1, 1} left = 0, right = 6;
- {0, 1, 1, 0, 0, 1, 1} left = 1, right = 6;
- {0, 1, 1, 0, 0, 1, 1} left = 1, right = 5;
- {0, 1, 1, 0, 0, 1, 1} left = 1, right = 4;
- {0, 0, 1, 0, 1, 1, 1} left = 1, right = 4;
- {0, 0, 1, 0, 1, 1, 1} left = 2, right = 4;
- {0, 0, 1, 0, 1, 1, 1} left = 2, right = 3;
- {0, 0, 0, 1, 1, 1, 1} left = 2, right = 3;
- {0, 0, 0, 1, 1, 1, 1} left = 3, right = 3;
- {0, 0, 0, 1, 1, 1, 1} left = 3, right = 2;
void sort_zeros_ones(int array[], int size)
{
int left = 0, right = size-1;
while(left < right)
{
while(array[left] == 0 && left < right)
left++;
while(array[right] == 1 && left < right)
right--;
if(left < right)
{
array[left] = 0;
array[right] = 1;
left++;
right--;
}
}
}
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.