For example, if we're given an Array:
The resulting Array may be:
- Moving negative values to the start of the Array:
- Shifting negative values to the end of the Array:
Note: The order must not be considered. The deal is to have all the negative numbers on one side.
The initial method that one might consider when faced with this question is the straightforward approach of sorting the array.
When the Array is sorted in ascending order, the negative elements accumulate at the start of the Array, and when sorted in descending order, all elements gather at the conclusion.
We have the flexibility to employ any sorting algorithm for the sorting process. In this case, we will opt for the selection sort algorithm:
When implementing the selection sort algorithm, the process involves locating the smallest element in the sub-array starting from element i + 1 for each element i in the array. Subsequently, a swap operation is performed between the two elements to effectively arrange the array in ascending order.
Code:
#include <stdio.h>
void selectionsort(int arr[], int n);
void swap(int *, int *);
int main()
{
int n, i;
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]);
}
selectionsort(arr, n);
printf("The final Array: ");
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
void selectionsort(int arr[], int n)
{
int i, j, min_in;
for(i = 0; i < n - 1; i++)
{
min_in = i;
for(j = i + 1; j < n; j++)
{
if(arr[j] < arr[min_in])
{
min_in = j;
}
}
swap(&arr[min_in], &arr[i]);
}
}
void swap(int *x, int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
Output:
Enter the size of the Array: 5
Enter the elements: 5 -8 3 -9 2
The final Array: -9 -8 2 3 5
If we adhere to this method, the time complexity amounts to O(n squared), with n representing the length of the Array.
Now, let's focus on the effective strategies:
We employed nested for loops in the previous method, leading to an escalation in the time complexity. It is imperative to find a solution that enables us to accomplish the task within a single traversal of the Array.
1. Using the partition approach
When following this method, we iterate through the Array, and upon encountering a negative element, we relocate it to either the start or the end of the Array.
Code:
#include <stdio.h>
int main()
{
//partition
int n, i, j;
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]);
}
j = 0;
for(i = 0; i < n; i++)
{
if(arr[i] < 0)
{
if(i != j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = 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-3 2 -5 -6 -1
The resultant Array: -3 -5 -6 -1 2 1
Understanding:
In the provided code snippet, we initialized a variable j to 0 as the starting point within the Array. Subsequently, we proceeded to traverse through the Array using the variable i, inspecting each element to determine if it is negative. Whenever a negative value is encountered at index i, we exchange it with the element at index j to relocate it to the initial segment of the Array. Following this operation, we increment the value of j and proceed with the iteration process.
For example:
Suppose the given Array is
During the initial iteration when the variables are set as j = 0 and i = 0, it indicates that the value at index 0 in the array (arr[0]) is positive.
For the second iteration -> when j = 0 and i = 1 -> the element at index 1 in the array is negative, and i is not equal to j.
so swap arr[0] <-> arr[1]
On the third loop, with j set to 1 and i to 2, it is determined that the element at index 2 in the array is positive.
In the fourth iteration with j equal to 1 and i equal to 3, the element at index 3 in the array is negative, and the indices i and j are not equal.
so swap arr[1] <-> arr[3]
On the fifth cycle, when j equals 2 and i equals 4, it is observed that the value at index 4 in the array is negative and i is not equal to j.
so swap arr[2] <-> arr[4]
Sixth round -> when j = 3 and i = 5 -> the element at index 5 in the array is negative and since i is not equal to j, perform a swap between arr[3] and arr[5].
Time complexity is denoted as O(n), where 'n' represents the size of the array being analyzed.
2. Using pointers/ variables
In this method, we employ a pair of pointers, or variables, denoted as a positioned at the start and b at the conclusion of the Array. Our process involves continuously inspecting the elements within the Array by advancing a and retracting b.
To shift all negative numbers to the start and positive numbers to the end of the Array:
Algorithm:
- If both a and b refer to a negative number, increment a.
- If a refers to a positive number and b to negative, swap the values at a and b.
- If both a and b are referring to a positive number, decrement b
- If a refers to a negative number and b to positive, increment a and decrement b.
Code:
#include <stdio.h>
void swap(int*, int*);
int main()
{
int n, i, l, r;
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]);
}
l = 0;
r = n - 1;
while(l <= r)
{
if(arr[l] < 0 && arr[r] < 0)
{
l += 1;
}
else if(arr[l] > 0 && arr[r] > 0)
{
r -= 1;
}
else if(arr[l] > 0 && arr[r] < 0)
{
swap(&arr[l], &arr[r]);
l += 1;
r -= 1;
}
else
{
l += 1;
r -= 1;
}
}
printf("The resultant Array: ");
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
void swap(int *a, int *b)
{
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}
Output:
Enter the size of the Array: 6
Enter the elements: 1 -3 4 -2 4 -3
The resultant Array: -3 -3 -2 4 4 1
3. Dutch Flag Algorithm
Proposed by Dijkstra, in a scenario where there are n red, white, and blue balls positioned randomly, the objective is to organize them such that all balls of identical colors are grouped together. The sequence should maintain the original order, ensuring white balls are placed before blue balls following the red ones.
We reduce the size of the Array by trimming from both ends, following a similar method as described above. This code serves as a streamlined version of the previous approach:
Code:
#include <stdio.h>
void swap(int*, int*);
int main()
{
int n, i, l, h;
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]);
}
l = 0;
h = n - 1;
while(l < h)
{
if(arr[l] < 0)
{
l++;
}
else if(arr[h] > 0)
{
h--;
}
else
{
swap(&arr[l], &arr[h]);
}
}
printf("The resultant Array: ");
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
void swap(int *a, int *b)
{
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;
}
Output:
Enter the size of the Array: 6
Enter the elements: 4 -2 4 -1 -2 -5
The resultant Array: -5 -2 -2 -1 4 4
Understanding:
Notice that in the code snippet above, we applied identical conditions as the previous method but streamlined it for greater simplicity.