When the Array is sorted in ascending order, it will arrange 0's first followed by 1's. To have 1's preceding 0's, the Array should be sorted in descending order.
Here is a code snippet that demonstrates the selection sort algorithm:
#include<stdio.h>
int main()
{
int n, i, temp;
printf("Enter the size of the array: ");
scanf("%d", &n);
int arr[n];
printf("Enter the elements: ");
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
int j = 0;
for(i = 0; i < n - 1; i++)
{
int min = arr[i];
for(j = i + 1; j < n; j++)
{
if(arr[j] < min)
{
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
Output:
Enter the size of the Array: 6
Enter the elements: 0 1 1 1 0 0
0 0 0 1 1 1
We have employed a pair of loops in this scenario - one for choosing an element from the Array and the other for identifying the minimum element within the Array. Consequently, the time complexity is O(N^2).
Method 2: Traversing the Array two times: Counting
In this technique, we will iterate through the Array twice to minimize the time complexity. The initial pass is utilized to calculate the quantity of 0's in the Array. Subtracting this count from the Array's size reveals the quantity of 1's present. Subsequently, the second iteration is employed to populate the Array with 0's first, succeeded by 1's.
Sample code:
#include<stdio.h>
int main()
{
int n, i, count;
printf("Enter the size of the array: ");
scanf("%d", &n);
int arr[n];
printf("Enter the elements: ");
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
for(i = 0; i < n; i++)
{
if(arr[i] == 0)
{
count++;
}
}
for(i = 0; i < count; i++)
{
arr[i] = 0;
}
for(i = count; i < n; i++)
{
arr[i] = 1;
}
printf("The resultant array: ");
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
Output:
Enter the size of the Array: 6
Enter the elements: 0 1 1 0 1 1
The resultant Array: 0 0 1 1 1 1
Method 3: Traversing the Array only once: Two pointers/ variables
In this method, a pair of variables or pointers is employed: one positioned at the start and the other at the end of the Array. In the scenario where we are organizing 0's before 1's, a continuous examination is conducted to detect any 0's to the right and 1's to the left. These two variables are then utilized to facilitate the exchange of these elements.
#include<stdio.h>
int main()
{
int n, i, count, temp;
printf("Enter the size of the array: ");
scanf("%d", &n);
int arr[n];
printf("Enter the elements: ");
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
int a = 0, b = n - 1;
while(a < b)
{
if(arr[a] == 1 && arr[b] == 0)
{
temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
else if(arr[a] == 1)
{
b--;
}
else
{
a++;
}
}
printf("The resultant array: ");
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
Output:
Enter the size of the Array: 6
Enter the elements: 1 1 1 0 0 0
The resultant Array: 0 0 0 1 1 1
Understanding:
In the given code snippet, we are presented with a pair of variables, namely a and b, which are referencing the start and conclusion of the Array correspondingly.
The logic here is,
- If we find a 0 on the right side and 1 on the left side of the Array, we'll swap the elements.
- If we find a 0 on the right side and another 0 on the left side, we can't swap them as a 0 on the left side shouldn't be disturbed. Hence, we'll increment the beginning variable to the next position till we find a 1 to swap with the 0 on the right side.
- It is the same mechanism for 1 on the left side of the Array with no 0 on the right side. We'll decrement the right variable to the preceding position to find a 0 to swap with the 1 on the left side.
Method 4: Traversing the Array only once: Partition method
In this method, we employ a pair of variables as mentioned in the previous technique, both initialized at the start of the Array. One variable (i) is responsible for iterating through the Array to locate 0's, while the other variable (j) indicates the starting point of the Array. Whenever a 0 is encountered at index i, the elements at i and j will be interchanged, followed by an increment of j. Essentially, j signifies the position where we aim to place 0's.
Sample code:
#include<stdio.h>
int main()
{
int n, i, temp;
printf("Enter the size of the array: ");
scanf("%d", &n);
int arr[n];
printf("Enter the elements: ");
for(i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
int j = 0;
for(i = 0; i < n; i++)
{
if(arr[i] == 0)
{
if(i != j)
{
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
j++;
}
}
}
printf("The resultant array: ");
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
Output:
Enter the size of the Array: 6
Enter the elements: 1 1 0 0 1 1
The resultant Array: 0 0 1 1 1 1
Understanding:
In the provided code snippet, we initialized a variable j to 0, positioning arr[j] at the Array's start. Our subsequent actions involve iterating through the Array using i. During each iteration, we evaluate whether arr[i] equals 0. Should arr[i] equal 0, we interchange its position with arr[j] to relocate it to the Array's beginning. Following this, we increase the value of j and proceed with the process.
For example:
First iteration -> j = 0, i = 0 -> arr[0] is 1
For the second iteration, with j = 0 and i = 1, the value of arr[1] is 0 and i is not equal to j.
so swap arr[0] <-> arr[1]
j = j + 1
Third iteration -> j = 1, i = 2 -> arr[2] is 1
In the fourth cycle, with j equal to 1 and i equal to 3, the value at arr[3] is determined to be 0, while ensuring that i does not equal j.
so swap arr[1] <-> arr[3]
In the fifth iteration, when j equals 2 and i equals 4, the value of arr[4] is 0, and i is not equal to j.
so swap arr[2] <-> arr[4]
Sixth cycle -> index j is 3, index i is 5 -> the value at arr[5] is 0 and since i is not equal to j, we exchange the values at arr[3] and arr[5].
The time complexity is O(n) where n represents the size of the array.